https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS로 풀이했다. 나 근데 가로 세로가 아직 헷갈린다;; 아이디어는 다음과 같다. n = 7, m = 5 사이즈의 2차원 배열 (= 그래프) 가 있다고 생각하면, 각 칸을 모두 0으로 초기화 시킨다 입력되는 직사각형 부분에 해당하는 칸들은 2차원 배열에서 1로 표시한다. 1은 이미 방문된 노드라는 의미이다. 그후 전체 2차원 배열을 이중 for문으로 하나씩 칸의 값을 체크하면..
Algorithm (PS)
https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 제한시간이 6초길래 시간 넉넉한줄 알았는데 시간 초과가 난 문제 ㅋㅋㅋ from collections import deque def D(n): tmp = n*2 if tmp > 9999: tmp %= 10000 return tmp def S(n): tmp = n if tmp == 0: return 9999 tmp -= 1 return tmp def L(n): front = n%1000..
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net steps 는 나이트가 이동할 수 있는 경우의 수를 배열로 표현했다. 핵심은 나이트가 이동할 때마다 그래프 상에서 이번 이동하면 몇번째인지 기록해두는 것이다 바로바로 이렇게 ! graph[nx][ny] = graph[x][y] + 1 graph[x][y]에는 x,y 위치로 오기까지의 step 횟수가 저장되어 있을것이므로 이 값에 1을 더한것이 새로운 위치인 nx, ny 까지 이동하는데 걸린 횟수이다..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net dfs/bfs로 풀 수 있는 문제인데 특이점은 대각선 방향도 고려해주어야 하는 것이다. 상하좌우 + 대각선 방향 = 총 8가지의 경로를 확인하면 된다. 1) dfs 풀이 import sys sys.setrecursionlimit(10000) def dfs(x, y): dx = [-1, 1, 0, 0, -1, -1, 1, 1] dy = [0, 0, -1, 1, -1, 1, -1, 1] # 8개..
array = [5,3,2,1,4] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] print(array) 선택 정렬의 원리: 가장 작은 데이터를 선택하여 앞에 있는 데이터를 바꿔치기 하는 것을 (n-1)번 반복한다. 다음과 같은 배열이 있다고 하자. 현재 맨 앞의 데이터와 배열에서 가장 작은 원소인 1을 교환한다. 1은 이미 정렬된 인덱스 이므로 제외한다.두번째 인덱스 3과 나머지 원소들 중 가장 작은 원소인 ..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉽지않은 계단수 문제였따 .. 여기서 (0-9)는 맨 끝자리수이고 N은 문제에서와 같이 자리수를 뜻한다. 규칙은 이렇게 각 끝자리수의 개수를 대각선 방향 왼쪽 위 + 대각선 방향 오른쪽 위 를 더하면 구할 수 있다. 즉, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라는 식이 나온다 !!! 끝자리 수가 0, 9일때는 각각 한쪽방향의 대각선에서만 존재하니까 그 수를 그대로 옮겨오면 된다. 위의 그림에서는 파란 선을 참고! 자리수가 1일때 (한자리수)일 때는 직접 초기화를 해주어야 한다. ..
다이나믹 프로그래밍은 전형적으로 보텀업 방식 형태를 보인다. 그렇지만 탑다운 방식과 보텀업 방식의 차이를 알아볼 필요가 있다. 상향식, 하향식에 따라 재귀호출인지 반복호출인지의 차이도 보여지기 때문이다. 1. 탑다운 방식 (Top-down) 재귀 함수를 이용하여 DP를 작성하는 방법. 큰 문제를 해결하기 위해 작은 문제를 호출한다. d = [0] * 100 def fibo(x): print('f(' + str(x) + ')', end=' ') if x == 1 or x == 2: return 1 if d[x] != 0: # 이미 계산한 적 있으면 그대로 값을 반환한다. return d[x] d[x] = fibo(x-1) + fibo(x-2) return d[x] * 실행 결과 f(10)을 구하기 위해서 ..
https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 간단한 구현문제 ! 초기값을 1 1 1 이라고 가정하고 우리가 구하고자 하는 준규네 나라의 날짜와 같은 e s m이 나올때 까지 하나씩 더해가면서 값을 비교한다 e, s, m = map(int, input().split()) a, b, c = 1, 1, 1 # 초기값 count = 1 while True: if a == e and b == s and c == m: print(count) break if..
