문제 www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 풀이 간단하게 딕셔너리 형태로 트리를 구현했다. 예제 입력으로 생성된 트리는 다음의 형태를 보인다. tree = {'A' : ['B', 'C'], 'B' : ['D', '.'], 'C' : ['E', 'F'], 'E' : ['.', '.'], 'F' : ['.', 'G'], 'D' : ['.', '.'], 'G' : ['.', '.']} 순회는 모두 재귀 형식으로 구현했으며, print문의 위치에 주..
문제 www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n의 범위가 크므로(최대 100,000) O(n)시간 안에 문제를 해결하는 것이 중요하다. 따라서 동적계획법을 적용하여 풀 수 있다. 최적해는 아래의 두 가지 상황을 고려하여 구할 수 있다. 1) 계속해서 더해간다: 이전 연속합에서 현재 정수를 더한다. 2) 초기화한다: 현재 정수부터 연속합을 다시 구한다. 점화식은 dp[n] = max(dp[n-1]+dp[n], dp[n])이 된다. 그림으로 표현하면 다음과 ..
문제 www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 정점을 탐색하는 건 어렵지 않지만, 경로를 기록하는 것이 까다롭다. 이차원 리스트에 경로를 저장하면 수월하게 해결할 수 있다. DFS/BFS 탐색 시 탐색을 시작하는 정점(start)을 매개변수로 넘겨주고 방문하는 정점마다 경로에 추가하면 된다. 즉, 현재 정점(cur)을 방문하면 path[start][cur] = 1이 된다. 이때 탐색하는 과정에서 사이클이 존재하는지 여부를 확인해줘야 한다. 코드 import sys sys.setrecurs..
문제 www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이 아래의 그림을 통해 점화식을 간단하게 표현할 수 있다. f(n)은 n만큼의 너비를 지니는 타일을 채우는 경우의 수이며 g(n)은 f(n)에서 1x1만큼의 타일을 빼고 채우는 경우의 수다. f(n)는 n이 홀수일 때 f(n) = 0이 되고, g(n)은 n이 짝수일 때 g(n) = 0이 된다. 이를 고려하여 base case를 처리한다. 코드 def solve(n): if n % 2 != 0: return 0 for i in range(2, n+1, 2): f[i] = f[i-2] + 2*g[i-1] for j i..
문제 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 최단 거리와 관련된 그래프 탐색 문제는 너비 우선 탐색(BFS)를 통해 해결한다. 큐에 좌표(y,x)와 함께 이동횟수(cnt)를 함께 삽입하여 탐색시 1씩 증가하게 한다. 만약 이동하려는 칸의 좌표에 도달하면 이동횟수를 출력하고 탐색을 종료한다. 코드 import sys, collections dx = [-2, -2, -1, -1, 1, 1, 2, 2] dy = [1, -1, 2, -2, 2, -2, ..
