문제 www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 풀이 n번 마을을 우수 마을로 선정하면 인접한 마을은 모두 우수 마을로 선정할 수 없다. 또한, n번 마을을 우수 마을로 선정하지 않은 상태에서 인접한 마을을 모두 우수 마을로 선정하는 것이 최적해를 보장하지는 않는다. 이 문제는 서브트리의 가중치의 합을 구하는 문제이다. 이를 dfs와 동적계획법으로 풀 수 있다. dp[n][1]은 n번 마을을 우수마을로 선정했을 경우에 우수 마을의 주민 ..
문제 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..
