동적 계획법 1 설명

1. 동적 계획법(DP)이란 ?

DP¹란, 문제를 재귀구조를 가지는 부분 문제들로 분할한 뒤, 작은 문제들부터 해결하고 그 답으로 더 큰 부분 문제들을 해결해나가며 최종 답을 구해내는 알고리즘이다. 이 때, 더 이상 분할할 수 없는 문제를 기저 사례라고 하며, 각 부분 문제와 그것들을 모아서 해결 할 수 있는 상하방 부분 문제들 간의 관계식을 점화식이라고 한다. 부분 문제들의 답들을 계산할 때 마다 저장해두고 같은 문제를 계산할 때, 미리 저장해둔 답을 불러와 중복 계산을 회피할 수 있다. 이를 메모이제이션 기법 이라고 한다. 이 메모이제이션 기법 덕분에 주어진 부분 문제들이 중복되는 경우, 이미 배웠던 백트래킹/완전탐색 류 알고리즘들에 비해 DP는 훨씬 빠르게 답을 구할 수 있다.

또한 부분 문제들을 구분하기 위한 수단으로 인자라는 단어를 사용한다. 부분 문제의 정답에 직접 영향을 끼치는 요인들을 인자라고 묶어 부른다. 같은 인자를 가진 부분 문제는 반드시 같은 답을 도출해야 한다. 예를들어 피보나치 수열에서는 인덱스가 인자가 된다. 만약 같은 인자를 가진 부분 문제에서 다른 답이 도출될 경우, 인자를 잘못 설정한 것이다. 문제에 따라 인자는 하나일 수도, 여러 개 일 수도 있다. DP 문제를 해결할 때 인자를 정확하게 파악하는 것이 가장 중요하다.

정리하면 DP는

1. 주어진 문제를 적절한 인자를 기준으로 재귀 구조를 가지는 부분 문제들로 분할
2. 기저 사례 확인
3. 점화식 수립
4. 기저 사례로부터 점화식을 통해 더 큰 부분 문제 해결 → 이 때 부분 문제 중복 소거
5. 최종 답 계산 이라는 공식을 가진 알고리즘이다.

알고리즘의 개념이 단순한만큼 문제의 바리에이션이 매우 다양하며, 난이도 또한 천차만별이고, Well-Known 알고리즘도 많은 카테고리이다. 그리고 여러 알고리즘과 섞기 쉬워서 별의 별 문제에 태그로 붙어있다.

아직 이 재귀 구조의 부분 문제를 합쳐가며 문제를 해결한다는 말이 직관적으로 와닿지는 않을테니 간단하게 피보나치 수열을 구현하며 DP에 대해 더 알아보자.

2. 피보나치 수열의 3가지 구현

피보나치 수열은 $n_i=n_{i-1}+n_{i-2}$의 점화식을 가지는 유명한 수열이다. 여기서 인덱스 $i$가 위에서 설명한 ==인자==가 된다. 수열은 $1,1,2,3,5,8,13,21,\mathrm{34...}$ 식으로 진행된다. 피보나치 수열은 이전 항들의 합, 즉 부분 문제의 조합으로 다음 항을 구할 수 있기 때문에 DP로 해결할 수 있는 대표적인 문제이다. 피보나치 수열의 $n$번째 항을 구하는 프로그램을 작성해보자.

1. 점화식을 활용한 피보나치 수열 구현

#include <iostream>
#include <vector>
usingnamespace std;
int main() {
	int n; cin >> n; vector<int> arr(n + 1);
	arr[1] = 1; arr[2] = 1;
	for(int i=3;i<=n;i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	cout << arr[n];
	return 0;
}

피보나치 수열의 점화식을 그대로 구현한 코드다. 논리적으로 보면 귀납보단 연역에 가까운 로직이다. 계산 횟수는 $N-2$로 꽤 빠른 시간 복잡도를 가진다.

2. 재귀를 활용한 피보나치 수열 구현

이미 재귀 호출 단원에서 작성했던 코드를 살펴보며 복습해보자.

#include <iostream>
using namespace std;
int r(int n) {
	if(n == 1 || n == 2) return 1;
	return r(n - 1) + r(n - 2);
}
int main() {
	int n; cin >> n;
	cout << r(n);
	return 0;
}

이 코드에는 문제가 한가지 있다. 바로 중복 계산을 너무 많이 한다는 것이다. 점화식으로 $i$번째 항을 계산할 때는 $i-2$번의 계산만 했다. ( 1, 2 항 제외 ) 하지만 이 코드는 다르다. 위 예제에 7을 입력했을 때의 실행 과정을 직접 확인해보자.

flowchart TD
1((7)) --> 2((6))
1((7)) --> 3((5))
2((6)) -. "8" .-> 1((7))
3((5)) -. "5" .-> 1((7))
2((6)) --> 4((5))
2((6)) --> 5((4))
4((5)) -. "5" .-> 2((6))
5((4)) -. "3" .-> 2((6))
3((5)) --> 6((4))
3((5)) --> 7((3))
6((4)) -. "3" .-> 3((5))
7((3)) -. "2" .-> 3((5))
4((5)) --> 8((4))
4((5)) --> 9((3))
8((4)) -. "3" .-> 4((5))
9((3)) -. "2" .->4((5))
5((4)) --> 10((3))
5((4)) --> 11((2))
10((3)) -. "2" .-> 5((4))
11((2)) -. "1" .-> 5((4))
6((4)) --> 12((3))
6((4)) --> 13((2))
12((3)) -. "2" .-> 6((4))
13((2)) -. "1" .-> 6((4))
7((3)) --> 14((2))
7((3)) --> 15((1))
14((2)) -. "1" .-> 7((3))
15((1)) -. "1" .-> 7((3))
8((4)) --> 16((3))
8((4)) --> 17((2))
16((3)) -. "2" .-> 8((4))
17((2)) -. "1" .-> 8((4))
9((3)) --> 18((2))
9((3)) --> 19((1))
18((2)) -. "1" .-> 9((3))
19((1)) -. "1" .-> 9((3))
10((3)) --> 20((2))
10((3)) --> 21((1))
20((2)) -. "1" .-> 10((3))
21((1)) -. "1" .-> 10((3))
12((3)) --> 24((2))
12((3)) --> 25((1))
24((2)) -. "1" .-> 12((3))
25((1)) -. "1" .-> 12((3))
16((3)) --> 32((2))
16((3)) --> 33((1))
32((2)) -. "1" .-> 16((3))
33((1)) -. "1" .-> 16((3))

r(7)의 호출에서 r(int n)함수가 무려 25번이나 호출되었다. 이 실행 트리를 보면 알 수 있는 사실이 하나 있다. 같은 수의 호출이 여러 번 반복된다. r(3)호출만 5번 반복되었고 r(5) 또한 2번 호출되었다. 이것은 이미 r(3)을 호출해서 r(3)의 결과를 알고 있음에도 불구하고 같은 함수의 호출을 5번이나 반복했다는 의미이다. 특히 5처럼 큰 수가 반복 호출될 경우, 그 아래 과정들도 모두 똑같이 반복해 호출하게 되므로 비용이 더 커진다. 각각의 함수가 2번씩 재귀하므로 최초 호출되는 n의 크기가 커질수록 이 반복 호출 횟수는 $2^n$에 비례해 커진다. 이건 정말 어마어마한 비용이다. 이러한 부분 문제의 중복 계산을 회피하기 위해 ==이미 계산해둔 부분 문제의 계산 결과를 저장하고 재사용하는 것을 메모이제이션(memoization) 기법==이라고 하며, DP의 핵심이다.

3. 재귀 함수 최적화

메모이제이션 기법을 적용해 재귀 피보나치 함수를 최적화 해보자. 각각의 n들을 계산했을 때 그 결과를 저장해뒀다가 이미 저장된 n을 다시 탐색하려할 때 탐색을 멈추고 저장된 결과를 리턴하는 식으로 최적화 할 수 있다.

#include <iostream>
using namespace std;
vector<int> cache;
int r(int n) {
	if(cache[n] != -1) return cache[n]; // 이미 계산했던 n이라면 저장된 계산 결과 리턴
	if(n == 1 || n == 2) return cache[n] = 1; // 계산 결과 저장
	return cache[n] = r(n - 1) + r(n - 2); // 계산 결과 저장
}
int main() {
	int n; cin >> n; cache = vector<int>(n + 1, -1);
	cout << r(n);
	return 0;
}

이제 우리는 같은 r(n)를 반복 계산할 일이 없다. 다시 한번 r(7)에 대한 실행 트리를 살펴보며 계산 횟수가 얼마나 줄어들었는지 확인해보자.

flowchart TD
1((7)) --> 2((6))
1((7)) --> 3((5))
2((6)) -. "8" .-> 1((7))
3((5)) -. "cache[5] = 5" .-> 1((7))
2((6)) --> 4((5))
2((6)) --> 5((4))
4((5)) -. "5" .-> 2((6))
5((4)) -. "cache[4] = 3" .-> 2((6))
4((5)) --> 8((4))
4((5)) --> 9((3))
8((4)) -. "3" .-> 4((5))
9((3)) -. "cache[3] = 2" .->4((5))
8((4)) --> 16((3))
8((4)) --> 17((2))
16((3)) -. "2" .-> 8((4))
17((2)) -. "cache[2] = 1" .-> 8((4))
16((3)) --> 32((2))
16((3)) --> 33((1))
32((2)) -. "1" .-> 16((3))
33((1)) -. "1" .-> 16((3))

25번에서 11번으로 호출 횟수를 줄이는데 성공했다. DP의 개념을 적용하면 이렇게 중복 계산하는 비용을 줄여 시간 소요를 줄일 수 있다. 단원의 첫 문제를 풀어보며 n이 커졌을 때 단순 재귀호출과 DP의 차이가 얼마나 크게 벌어지는지 직접 확인해보자. 그리고 다른 알고리즘들과는 다르게 DP 는 반드시 모든 문제를 정주행할 것을 추천한다. 알고리즘 특성 상 응용의 폭이 넓기 때문에 Well-Known 알고리즘들이 많은 편이기 때문에 공부할 양이 많다.

3. 문제 풀이

1. 알고리즘 수업 - 피보나치 수 1
   • 재귀 구조에서 중복 계산이 발생할 경우 나타나는 끔찍한 일에 대해 알아봅시다.
2. 신나는 함수 실행
   • 메모이제이션을 직접 적용해봅시다.
   • 인자가 많을 때도 메모이제이션을 적용할 수 있습니다.
3. 01타일
   • Top-down 방식과 Bottom-up 방식 구현에 대해 알아봅시다.
   • 점화식을 구하고 코드를 작성해봅시다.
4. 파도반 수열
   • 같은 문제에도 점화식이 여러가지가 있을 수 있습니다.
5. 연속합
   • 문제를 Bottom-Up 방식으로 단계적으로 나눠 생각해봅시다.
6. RGB거리
   • 문제가 설정한 인자를 파악해봅시다.
7. 정수 삼각형
   • 문제가 2차원으로 나올 수도 있습니다.
8. 계단 오르기
   • 점화식이 슬슬 어려워지죠? 두 가지 풀이의 발상을 모두 알아야 합니다.
9. 1로 만들기
   • 경로를 탐색해봅시다.
10. 쉬운 계단 수
    • 숨겨진 인자를 찾아봅시다. 어떤 걸 인자로 추가해야 문제를 쉽게 풀 수 있을까요 ?
11. 포도주 시식 *숨겨진 인자를 찾아봅시다. 어떤 걸 인자로 추가해야 문제를 쉽게 풀 수 있을까요 ?
12. 가장 긴 증가하는 부분 수열
    • DP Well-Known LIS 문제를 배워봅시다.
13. 가장 긴 바이토닉 부분 수열
    • LIS 응용문제 1
    • DP 배열에 저장하는 값이 무슨 값인지 정확하게 인지해봅시다.
14. 전깃줄
    • LIS 응용문제 2
    • 주어진 명제를 분석해봅시다.
15. LCS
    • DP Well-Known LCS 문제를 배워봅시다.
16. 평범한 배낭
    • DP Well-Known Knapsack 문제를 배워봅시다.

---

Footnotes

1. Dynamic Programming 의 약자로 동적계획법을 의미한다. ↩