yeolyi.com성열의 컴퓨터공학

동적 계획법 문제들

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

동적 계획법 글의 거스름돈 문제에서는 더 적은 금액이 곧 작은 문제였습니다. 하지만 무엇을 작은 문제로 삼을지 바로 보이지 않는 문제도 많습니다. 표의 칸 하나에 무엇을 적을지 정하는 법을 세 문제로 연습해 봅시다.

가장 긴 증가하는 부분 수열

수열에서 순서를 지키며 몇 개를 골라낸 것을 부분 수열이라 합니다. 5, 2, 8, 6, 3, 7, 9, 4에서 2, 3, 7, 9는 계속 커지는 부분 수열입니다. 이런 것 중 가장 긴 것을 가장 긴 증가하는 부분 수열(longest increasing subsequence, LIS)이라 합니다.

부분 수열은 수마다 고르거나 말거나라 2ⁿ가지입니다. 대신 칸 i에 i번 수로 끝나는 가장 긴 증가 부분 수열의 길이를 적어 봅시다. 끝이 정해지면 바로 앞에 올 수는 앞쪽의 더 작은 수 중 하나이니, 그중 칸 값이 가장 큰 것 뒤에 붙이면 됩니다.

수열52863794표

표의 칸에는 그 수로 끝나는 가장 긴 증가 부분 수열의 길이를 적습니다.

진한 칸은 지금 수보다 앞에 있는 더 작은 수의 칸이고, 바탕이 칠해진 칸이 그중 가장 긴 것입니다.

칸 n개를 채우며 칸마다 앞 칸을 모두 보니 O(n²)입니다. 답은 표에서 가장 큰 값입니다.

0-1 배낭

무게를 7까지 담는 가방에 물건을 골라 넣어 가치의 합을 가장 크게 하려 합니다. 물건마다 넣거나 말거나 둘 중 하나라 0-1 배낭 문제(0-1 knapsack problem)라 합니다. 물건 A, B, C, D의 무게는 1, 3, 4, 5이고 가치는 1, 4, 5, 7입니다. 무게당 가치가 큰 것부터 넣는 그리디는 D와 A를 넣어 8에 그치지만, B와 C를 넣으면 9입니다.

이번 표는 두 방향입니다. 칸 (i, w)에는 앞의 물건 i개만 써서 무게 한도 w 안에서 낼 수 있는 가장 큰 가치를 적습니다. i번째 물건을 안 넣으면 바로 위 칸 값이고, 넣으면 그 무게만큼 한도를 줄인 위 줄 칸 값에 가치를 더한 값입니다. 둘 중 큰 쪽을 적습니다.

A 무게 1 · 가치 1B 무게 3 · 가치 4C 무게 4 · 가치 5D 무게 5 · 가치 7

한도01234567
없음00000000
A0
B0
C0
D0

칸에는 그 줄까지의 물건으로, 그 한도 안에서 낼 수 있는 가장 큰 가치를 적습니다.

굵은 테두리는 지금 칸을 채우며 읽는 칸, 바탕이 칠해진 칸이 그중 고른 쪽입니다.

물건이 n개, 한도가 W면 칸 n × W개를 두 칸씩 보며 채우니 O(n × W)입니다.

가장 긴 공통 부분 수열

두 문자열에 함께 들어 있는 부분 수열 중 가장 긴 것은 가장 긴 공통 부분 수열(longest common subsequence, LCS)입니다. ACDBE와 ABCDE라면 ACDE입니다. 두 파일에서 바뀐 줄을 보여 주는 diff도 줄을 글자처럼 보고 LCS를 구합니다.

표는 배낭처럼 두 방향입니다. 칸 (i, j)에는 앞 문자열의 앞 i글자와 뒤 문자열의 앞 j글자 사이의 답을 적습니다. 두 앞부분의 마지막 글자가 같으면 그 글자를 답 끝에 붙일 수 있으니 왼쪽 위 칸에 1을 더합니다. 다르면 두 글자 중 하나는 답에 쓰이지 않으니, 그 글자를 뗀 위 칸과 왼쪽 칸 중 큰 값을 적습니다.

1#include <stdio.h>
2#include <string.h>
3
4char a[] = "ACDBE";
5char b[] = "ABCDE";
6// table[i][j]: a의 앞 i글자와
7// b의 앞 j글자 사이의 답
8int table[6][6];
9
10int max(int x, int y) {
11 if (x > y) {
12 return x;
13 }
14 return y;
15}
16
17int main(void) {
18 int n = strlen(a);
19 int m = strlen(b);
20 for (int i = 1; i <= n; i++) {
21 for (int j = 1; j <= m; j++) {
22 // 마지막 글자가 같으면
23 if (a[i - 1] == b[j - 1]) {
24 table[i][j] =
25 table[i - 1][j - 1] + 1;
26 } else {
27 table[i][j] = max(
28 table[i - 1][j],
29 table[i][j - 1]);
30 }
31 }
32 }
33 printf("%d\n", table[n][m]);
34 return 0;
35}

변수 없음
출력 없음

재생하며 table이 한 줄씩 채워지는 모습을 봅시다. 맨 오른쪽 아래 칸이 답입니다.

마무리

이번 파트에서는 매 순간 가장 좋아 보이는 것을 고르는 그리디 알고리즘과, 겹치는 작은 문제의 답을 표에 적어 두고 다시 쓰는 동적 계획법으로 큰 답을 쌓았습니다. 지하철에서 가장 빨리 가는 길도 이 두 방법으로 찾지만, 먼저 역과 역 사이의 얽힌 연결을 담아야 합니다. 그래서 다음 파트에서는 이어진 것들 사이에서 길을 찾는 그래프를 다룹니다. 첫 글은 그래프입니다.

도전 문제

서로 다른 정수 여러 개를 한 줄로 늘어놓습니다. 증가하는 부분 수열도, 계속 작아지는 감소 부분 수열도 길이가 3을 넘지 않게 하려면 많아야 몇 개까지 늘어놓을 수 있을까요? 숫자로 답하세요.