설계 기법 문제
개념마다 확인(뜻을 맞게 알았나) → 추적(손으로 한 단계씩) → 응용(처음 보는 상황) 순서로 푼다. 풀이 보기를 누르기 전에 종이에 먼저 적어 보자.
분할 정복
확인
배열의 최댓값을 분할 정복으로 구한다. 반으로 나눠 양쪽의 최댓값을 구하고, 둘 중 큰 값을 고른다(비교 1번). 점화식은 T(n) = 2T(n/2) + 1이다. 아래 표는 n = 16일 때 깊이마다 하는 일의 합이다. 전체 시간은 O(무엇)인가? 이진 탐색(T(n) = T(n/2) + 1)과 무엇이 다른가?
풀이 보기
O(n)이다. 줄마다 일이 두 배로 늘어 맨 아래 잎(16개)이 전체를 정하고, 합은 1 + 2 + 4 + 8 + 16 = 31 = 2n - 1이다. 이진 탐색은 한쪽만 내려가 줄마다 일이 1로 같고 줄이 log₂ n + 1개라 O(log n)이다.
마스터 정리의 세 경우 중 "줄마다 일이 늘어나는" 경우다. 잎의 수 n^(log_b a) = n^(log₂ 2) = n이 답이다. 최댓값은 어차피 모든 값을 한 번씩 봐야 하니 나눠도 앞에서부터 훑는 O(n)보다 빨라지지 않는다. 나누기가 이득인 것은 합치는 일이 나누기 덕분에 줄어들 때다.
추적
카라츠바 곱셈으로 1234 × 5678을 계산한다. 두 수를 두 자리씩 x = 12·100 + 34, y = 56·100 + 78로 나눌 때, 맨 위 단계에서 하는 곱셈 세 개의 값과 z1(가운데 자리 계수)을 구하고 최종 곱을 확인하라.
풀이 보기
세 곱셈은 12 × 56 = 672, 34 × 78 = 2652, 46 × 134 = 6164이고, z1 = 6164 - 672 - 2652 = 2840이다. 합치면 672·10⁴ + 2840·10² + 2652 = 7006652로 1234 × 5678과 같다.
(12 + 34)(56 + 78) = 12·56 + 12·78 + 34·56 + 34·78이므로 양 끝 두 항(z2, z0)을 빼면 가운데 두 항의 합만 남는다. 곱셈 네 번(12·56, 12·78, 34·56, 34·78)이 세 번으로 줄었고, 이것을 재귀로 되풀이하면 T(n) = 3T(n/2) + n, 곧 O(n^1.585)가 된다.
응용
세 점화식 ① T(n) = 4T(n/2) + n, ② T(n) = 2T(n/4) + n, ③ T(n) = 3T(n/3) + n의 깊이별 일을 아래에 적었다. 각각의 전체 시간을 O로 답하라.
풀이 보기
① O(n²), ② O(n), ③ O(n log n)이다.
- ① 줄마다 일이 두 배로 는다. 잎이 전체를 정하고, 잎의 수는 n^(log₂ 4) = n²이다(n = 16이면 256).
- ② 줄마다 일이 절반으로 준다. 맨 위 한 번의 n이 전체를 정하고, 아래는 다 합쳐도 그보다 작다(16 + 8 + 4 = 28 < 2·16).
- ③ 줄마다 일이 n으로 같다. 줄이 log₃ n + 1개라 n log n이다. 병합 정렬과 같은 경우이고 로그의 밑은 O에서 상관없다.
판단 기준은 a와 b^c의 크기 비교다. ①은 4 > 2¹, ②는 2 < 4¹, ③은 3 = 3¹이다. 한 줄 내려갈 때 일이 a / b^c배가 되기 때문이다.
동적 계획법
확인
f(n) = f(n-1) + f(n-2)(f(0) = 0, f(1) = 1)를 메모 없이 재귀로 짜서 f(6)을 부르면 함수 호출이 모두 몇 번 일어나는가? 계산한 답을 표에 적어 두는 메모이제이션을 쓰면 몇 번으로 주는가?
풀이 보기
메모 없이 25번, 메모하면 11번이다. 메모하면 서로 다른 인자 0~6 일곱 개를 한 번씩 계산하고, f(1)~f(4)를 두 번째로 부르는 네 번은 표에서 바로 꺼낸다.
불린 횟수 자체가 피보나치 수처럼 자란다. f(n)의 호출 수는 2·f(n+1) - 1이라 f(6)이면 2·13 - 1 = 25다. n이 하나 늘 때마다 약 1.6배씩 늘어나 지수 시간이고, 메모하면 2n - 1번으로 선형이 된다.
추적
무게 한도 5인 배낭에 아래 네 물건 중 일부를 넣는다. 0/1 배낭 표를 채워 최대 가치와 고른 물건을 구하라.
풀이 보기
최대 가치는 7이고, 물건 1과 2(무게 2 + 3 = 5, 가치 3 + 4 = 7)를 고른다.
물건을 하나도 안 쓰거나 무게 한도가 0이면 가치는 0이다. 첫 줄과 첫 칸을 0으로 채운다.
되짚을 때 4행 5열(7)은 위 칸과 같아 물건 4를 빼고, 3행도 같아 물건 3을 뺀다. 2행 5열의 7은 위 칸(3)과 달라 물건 2를 넣었고, 한도를 3만큼 줄여 1행 2열(3)로 간다. 이 값은 위 칸(0)과 달라 물건 1도 넣었다. 가치가 가장 큰 물건 4(가치 6)만 넣는 것보다 작은 둘을 함께 넣는 쪽이 낫다.
추적
동전 1·3·4원으로 금액을 만드는 최소 동전 수를 표로 구한다. best[0] = 0이고 best[v] = 1 + min(best[v-1], best[v-3], best[v-4])(뺄 수 있는 것만)다. best[1]~best[6]을 채워 보라.
풀이 보기
best[0..6] = [0, 1, 2, 1, 1, 2, 2]이다. 6원은 동전 2개(3 + 3)면 된다.
6원 칸은 best[5] = 2, best[3] = 1, best[2] = 2를 비교해 가장 작은 best[3]에 1을 더한다. 탐욕은 가장 큰 4원을 먼저 집어 best[2] 쪽으로 가는 바람에 3개가 된다. 표는 모든 마지막 동전을 다 따져 보니 틀리지 않는다. 금액 V, 동전 k종이면 O(Vk)다.
응용
배낭 표를 한 줄(best[w])로 줄여 메모리를 아끼려 한다. 무게 2·가치 3인 물건 하나, 한도 4에서 best[w] = max(best[w], best[w-2] + 3)을 w = 2, 3, 4 순서(오름차순)로 갱신하면 best[4]는 얼마인가? 맞는 답은 무엇이고, 어떻게 고쳐야 하는가?
풀이 보기
오름차순이면 best[4] = 6이 나오지만 물건이 하나뿐이니 맞는 답은 3이다. w를 큰 쪽부터(내림차순) 갱신하면 된다.
2차원 표에서 best[i][w]는 윗줄 best[i-1][w-2]를 본다. 한 줄로 줄이면 왼쪽 칸이 아직 윗줄 값이어야 하는데, 오름차순으로 돌면 best[2]가 먼저 이번 물건을 넣은 값 3으로 바뀌고 best[4]가 그것을 다시 쓴다. 내림차순이면 왼쪽 칸이 아직 바뀌기 전이라 윗줄 값 그대로다. 거꾸로, 같은 물건을 몇 번이든 넣어도 되는 배낭(개수 제한 없는 배낭)에서는 오름차순이 맞는 답이다.
탐욕법
확인
14원을 탐욕으로(낼 수 있는 가장 큰 동전부터) 거슬러 준다. 동전이 10·5·1원인 나라와 10·7·1원인 나라에서 각각 탐욕의 답이 동전 수가 가장 적은 답인가?
풀이 보기
10·5·1원은 최소(동전 5개)이고, 10·7·1원은 아니다. 10·7·1원에서 탐욕은 10 + 1 + 1 + 1 + 1로 5개를 내지만 7 + 7이면 2개다.
거슬러 줄 돈: 14원. 매번 낼 수 있는 가장 큰 동전을 고른다.
10·5·1원에서 10원 대신 작은 동전을 쓰면 5 + 5처럼 같은 금액에 동전이 더 든다. 큰 동전이 작은 동전 몇 개를 언제나 손해 없이 대신하니 탐욕이 맞는다. 7원은 10원의 약수가 아니라서 "지금 10원을 고른 것"이 나중에 7원 두 개의 기회를 막는다. 이런 체계는 동적 계획법 문제의 표로 푼다.
추적
회의실 하나에 아래 여덟 회의 중 겹치지 않게 가장 많이 넣으려 한다(한 회의가 끝난 시각에 다음 회의를 시작할 수 있다). "끝나는 시간이 가장 이른 회의부터, 앞서 고른 회의와 겹치지 않으면 고른다"로 고른 회의를 적어 보라. "시작이 가장 이른 회의부터"로 고르면 몇 개인가?
풀이 보기
A(1~4), D(5~7), G(8~11)로 3개다. 시작이 이른 순으로 고르면 C(0~6), F(6~10)로 2개뿐이다.
끝이 가장 이른 A를 고르면 남은 시간이 가장 넓게 남는다. 바꿔치기 논법으로 보면, 어떤 최적해의 첫 회의를 A로 바꿔도 A가 더 일찍(또는 같이) 끝나니 뒤의 회의와 겹치지 않는다. 그래서 A를 포함하는 최적해가 늘 있고, A 뒤의 남은 시간에서 같은 논리를 되풀이하면 된다. 시작이 이른 C는 길어서 다른 회의를 많이 가린다.
응용
무게 한도 50인 배낭에 물건 셋 (무게 10, 가치 60), (20, 100), (30, 120)을 넣는다. "무게당 가치가 큰 것부터 들어가는 만큼 넣는다"는 탐욕의 답은 얼마이고, 최적은 얼마인가? 물건을 잘라 넣을 수 있다면 어떻게 되는가?
풀이 보기
탐욕은 160, 최적은 220이다. 탐욕은 첫째(10)와 둘째(20)를 넣고 남은 20에 셋째(30)가 들어가지 않아 멈춘다. 최적은 둘째와 셋째(무게 50, 가치 220)다. 잘라 넣을 수 있으면 탐욕이 최적이고, 셋째의 2/3를 더해 240이다.
0/1 배낭은 물건을 통째로만 넣으니 효율이 좋은 물건이 공간을 어중간하게 남겨 손해를 볼 수 있다. 탐욕 선택 속성이 깨진 것이다. 잘라 넣을 수 있으면 남는 공간이 생기지 않아 무게당 가치 순서가 언제나 옳다. 0/1 배낭은 동적 계획법 문제의 표로 푼다.
백트래킹
확인
4×4 판의 1행 2열과 2행 4열에 퀸이 있다. 3행에서 퀸을 놓을 수 있는 열은 어디인가?
풀이 보기
1열 하나뿐이다. 2열은 1행의 퀸과 같은 열, 4열은 2행의 퀸과 같은 열, 3열은 2행 4열의 퀸과 대각선이다.
두 칸 (r1, c1), (r2, c2)가 대각선이면 |r1 - r2| = |c1 - c2|다. 3행 3열과 2행 4열은 행 차이 1, 열 차이 1이라 대각선이다. 3행 1열에 놓고 4행으로 가면 3열이 남아 해 (2, 4, 1, 3)열이 된다. 노트의 단계 그림이 끝에 찾는 바로 그 해다.
추적
5×5 판에서 노트와 같은 백트래킹(한 행씩, 왼쪽 열부터)으로 첫 해를 찾는다. 첫 해의 배치를 적고, 부딪쳐 건너뛴 시도와 퀸을 거두고 되돌아간 횟수를 세어 보라.
풀이 보기
첫 해는 1, 3, 5, 2, 4열(1행부터)이다. 부딪친 시도는 10번, 되돌아가기는 0번이다.
5×5 판에 서로 공격하지 않게 퀸 5개를 놓는다. 한 행에 하나씩, 위에서부터.
4×4에서는 첫 해까지 퀸을 여러 번 거두고 되돌아가야 했는데, 5×5는 운 좋게 첫 시도들이 모두 해로 이어진다. 판이 크다고 늘 더 어려운 것은 아니고, 백트래킹이 얼마나 걸릴지는 입력에 따라 크게 다르다. 최악은 여전히 지수 시간이다.
응용
[2, 3, 5, 7]에서 몇 개를 골라 합이 10이 되는 조합을 모두 찾는다. 다음 수를 하나씩 더해 보는 백트래킹에서, 수가 오름차순이니 "합이 10을 넘으면 그 수와 뒤의 수는 시도하지 않는다"로 자른다. 호출(트리의 칸)은 몇 번인가? 자르지 않으면 몇 번인가?
풀이 보기
해는 {2, 3, 5}와 {3, 7}이고, 자르면 호출이 11번, 자르지 않으면 모든 부분집합 2⁴ = 16번이다.
합 7(2 + 5)에서 7을 더하면 14라 자르는데, 정렬돼 있으니 뒤에 올 수도 모두 7 이상이라 볼 필요가 없다. 이렇게 "이 갈래에서는 해가 나올 수 없다"를 일찍 아는 조건이 강할수록 가지치기가 많이 자른다. 수가 많아지면 16과 11의 차이가 수천 배로 벌어진다.
두 포인터·슬라이딩 윈도
확인
정렬된 [2, 5, 8, 12, 15]에서 합이 20인 두 칸을 찾는다. 첫 비교 2 + 15 = 17은 20보다 작다. L과 R 중 어느 쪽을 옮겨야 하고, 그렇게 해도 답을 놓치지 않는 이유는 무엇인가?
풀이 보기
L을 오른쪽으로 옮긴다. 2와 짝지을 수 있는 가장 큰 값이 15인데도 20에 못 미치니, 2는 어떤 칸과도 답이 될 수 없다. 2를 버리고 다음 비교 5 + 15 = 20에서 찾는다.
R을 옮기면 오히려 더 작은 값과 짝지어 합이 줄어들 뿐이다. 비교 한 번마다 칸 하나를 확실히 버리니 많아야 n - 1번 비교하면 끝난다.
추적
정렬된 [1, 3, 6, 8, 11, 14, 16]에서 합이 20인 두 칸을 두 포인터로 찾는다. 합을 몇 번 계산하고, 어느 두 값을 찾는가?
풀이 보기
합을 4번 계산해 6 + 14를 찾는다. 17(작다, L 이동), 19(작다, L 이동), 22(크다, R 이동), 20(찾음) 순서다.
정렬된 배열에서 합이 20인 두 칸을 찾는다. 양 끝에서 시작한다.
모든 쌍을 보면 7×6/2 = 21쌍이다. 두 포인터는 포인터가 한 번 움직일 때마다 칸 하나를 후보에서 지우니 많아야 6번이고, 여기서는 4번에 끝났다.
추적
양수 배열 [2, 1, 3, 1, 1, 4, 2, 1]에서 합이 6 이하인 가장 긴 연속 구간을 슬라이딩 윈도로 찾는다. 가장 긴 구간과 그 길이를 구하라.
풀이 보기
가장 긴 구간은 1~4번 칸 [1, 3, 1, 1](합 6)이고 길이는 4다.
합이 6 이하인 가장 긴 연속 구간을 찾는다. 창을 오른쪽으로 넓혀 간다.
3번 칸의 1이 들어와 [2, 1, 3, 1]의 합이 7이 되면 2를 빼고, 다음 1을 더한 [1, 3, 1, 1]이 길이 4가 된다. 그 뒤로 4, 2가 들어오면 창이 크게 줄어 더 긴 구간은 나오지 않는다. 왼쪽 끝과 오른쪽 끝이 모두 앞으로만 움직이니 여덟 칸 각각이 창에 한 번 들어오고 많아야 한 번 나간다.
응용
음수가 섞인 [3, 4, -5, 2, 1]에서 합이 5 이하인 가장 긴 연속 구간을 같은 슬라이딩 윈도로 찾으면 길이 4([4, -5, 2, 1])를 답한다. 맞는 답은 무엇이고, 슬라이딩 윈도는 어디서 틀렸는가?
풀이 보기
맞는 답은 배열 전체, 길이 5(3 + 4 - 5 + 2 + 1 = 5)다. 슬라이딩 윈도는 4를 넣어 합이 7이 된 순간 3을 버렸는데, 뒤에 -5가 와서 3을 다시 담을 수 있게 된다는 것을 모른다.
슬라이딩 윈도는 "창을 줄이면 합이 줄고, 늘리면 합이 는다"는 단조성에 기대 왼쪽 끝을 되돌리지 않는다. 음수가 있으면 늘려도 합이 줄 수 있어 버린 칸이 다시 답이 될 수 있다. 이럴 때는 누적합 prefix[i]를 두고 prefix[j] - prefix[i] ≤ 5인 가장 먼 i를 찾는 다른 방법을 쓴다.