서론
어쩌다보니 동아리에서 알고리즘을 가르칠 일이 생기기도 했고, 다시 공부해야겠다 마음 먹은 겸 블로그에 정리해보고자 한다.
Dynamic Programming
오늘의 주제인 Dynamic Programming 이다. 주로 dp 라고 많이 줄여부르는 기법이다.
There are two key attributes that a problem must have in order for dynamic programming to be applicable:
optimal substructure and overlapping sub-problems.
-wikipedia
위키피디아에 따르면 2가지 중요한 특성이 있어야만 dp 로 해결할 수 있다고 한다.
optimal substructure, overlapping sub-problem.
Optimal Substructure
한글로 직역한다면 "최적 부분 구조" 정도일 거 같다.
간단히는 현재 문제를 작은(쉬운) 문제로 쪼갤 수 있으며, 이 작은 문제가 원래의 어려운 문제를 푸는데 기여를 할 수 있다는 의미이다.
만약, 기여의 방식이 매 작은 문제를 최적하는 것이 전체 문제를 최적한다는 사실이 입증된다면, 그리디 알고리즘을 통해 해결할 수 있다.
Overlapping sub-problem
역시 직역한다면 "겹치는 부분문제" 정도일 거 같다.
쪼개진 작은 문제가 다른 문제를 푸는데 계속해서 사용되어야한다는 의미이다.
쪼개질 때마다 매번 다른 문제거나, 답이 달라진다면 dp를 활용하기 어려워진다.
dp의 정의를 간단하게 되돌아보았다. 핵심은 작은 문제로 쪼개지며, 해결한 작은 문제가 재활용 되어야 한다는 것이다.
현실적으로는...
대부분의 dp 는 dp 테이블이라는 어떤 배열을 활용한다.
이 dp 테이블을 잘 정의하는 부분이 Optimal Substructure, 즉 작은 문제를 잘 쪼개는 것이며,
배열 안의 원소간의 관계를 잘 정의하는 것이 Overlapping sub-problem 이라고 생각할 수 있다.
보통은 배열 안의 원소간의 관계는 점화식으로 많이 나타내진다.
dp 테이블의 정의 와 점화식 을 구하는 것이 주로 문제가 되며, 이 둘의 어려움을 통해 문제의 난이도가 결정된다.
먼저 간단한 문제로 dp 테이블 이 어떻게 사용되는지, 점화식 이 어떻게 사용되는지 알아보자.
15988 1, 2, 3 더하기 - 3
문제를 간단히 요약하면, 여러 $n$ 에 대해, $\sum a_n = n, \, a_n = 1, 2, 3$ 을 만족하는 수열 $ \{ a_n
\} $ 의 개수를 출력하면 된다.
단 한번의 더하기를 통해 $n$을 만든다고 생각해보자.
임의의 $n$ 에 대해, $n$ 은 $n - 1$, $n - 2$, $n - 3$ 에서 1, 2, 3 을 더해서 만들어지는 경우밖에 없다.
즉, $n$ 을 만드는 방법은 $n - 1$, $n - 2$, $n - 3$ 을 만드는 방법을 모두 합친 것이다.
??? : 저 3가지 방법의 교집합이 정말 없나요?
- {...$n - 1$ 을 만드는 방법}, 1
- {...$n - 2$ 을 만드는 방법}, 2
- {...$n - 3$ 을 만드는 방법}, 3
은 마지막 1, 2, 3 으로 다름이 보장된다.
??? : 왜 한번의 더하기만 써야하나요? +1, +3 해서 두번에 걸쳐서 계산은 고려하지 않나요?
+1 까지 묶게 되면, $n - 3$ 을 만드는 방법에 포함되어, 같은 경우를 2번 고려하게 된다.
즉, $n$ 에 대한 문제는 $n - 1$, $n - 2$, $n - 3$ 에 대한 부분 문제로 쪼개지며(Optical SubStructrue),
그 값은 변하지 않고, $n$ 을 구하는데 기여한다(Overlapping sub-problem).
이 문제를 코드로 구현해보자.
부분문제는 $i <= n$ 인 $i$ 에 대하여, $i$ 를 만들 수 있는 방법의 문제이므로,
dp[i] = i 를 만들 수 있는 방법의 수 로 정의하자.
위의 논의로 점화식은 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 이 된다.
이를 앞에서부터 차례대로 구하면 된다.
1149 RGB거리
문제를 요약하면, 매번 3가지의 색 중 하나를 선택해야한다. 이 때, $i$번째 색은 $i - 1$번째 색과 달라야하며,
모든 색깔에는 비용이 있다. 총 $n$ 까지의 색칠을 해서, 최소 비용을 출력하면 된다.
이 문제도 부분문제로 쪼갤 수 있을까?
가장 먼저 떠올릴 수 있는 생각은 직전 선택까지 최소비용이라면, 그걸로 이번 선택도 최소로 고를 수 있지 않을까?
그러면 dp[i] = i번째까지 집을 골랐을 때 최소비용 으로 정의해보자.
이를 통해 각 부분문제를 연결할 수 있을까? 생각해보면 그렇지 않다.
- i번째에 가능한 선택지를 알아낼 수 없다.
문제 조건에 의해 $i$번째 집은 $i - 1$번째 집과는 색이 달라야한다. 하지만, dp[i - 1] 의 값은 비용만 말할 뿐,
어떤 색인지에 대해서는 아무것도 알려주지 못한다. - 심지어 정답이 아니다.
설령 어떻게든 가능한 선택을 고를 수 있어도, 그 선택이 정답이라는 보장을 할 수 없다.
다음 예시를 살펴보자.
매 순간 가능한 최소비용을 선택할 때, 매 선택을 검은색 점선으로 나타내었다.
마지막 선택에서 100, 1, 1000 에서 1을 고를 수 없기 때문에, 100을 골라야하며,
마지막에 1을 고를 수 있도록 조정한다면, 이 방법보다는 항상 비용이 적어진다.
즉, 매 최선의 선택이 정답이 아닌 것이다.(이러한 방식으로 답을 도출하는 것을 그리디 알고리즘이라고 한다.)
이제 이러한 문제점들을 해결해보자.
1번이 해결되지 않은 이유는 다음 가능한 선택지를 알 수 없었기 때문이다.(서로 다른 색이어야한다는 규칙 때문에)
다음 가능한 선택지를 알아내기 위해, dp 테이블을 다음과 같이 정의해보자.
dp[i][color] = i에서 color 을 골랐을 때, i 에서의 최소비용
이제 2번째 인덱스를 통해 우리는 가능한 선택지를 판별해낼 수 있다.
2번의 경우, 새로 정의된 dp 테이블에 의해 알아서 해결된다.
기존에는 $i$ 에서의 최솟값이 좀 더 세분화하여, 나뉘어졌으며, 이는 직전의 최솟값을 이용해 구할 수 있다.
왜냐하면, dp[i][color] 의 값은 오직 dp[i - 1][c]; c != color 에 의해 결정되기 때문이다.
다시 말하면 $i$ 번째에 R 을 고르는 상황에서의 최솟값은 $i$ 에서 G, B 를 고르고 오는 경우의 수 밖에 없다.
우리는 인덱스를 늘림으로써, 데이터를 좀 더 세분화할 수 있다.
하지만, 데이터가 자세해지는 만큼, 공간, 시간복잡도가 증가할 수 밖에 없다.
최악의 경우는 브루트포스의 모든 경우를 따지는 것과 같아지므로, 적절한 인덱스 설정이 필요하다.
Dynamic Programming 은 부분문제로 쪼개지며, 부분문제의 정답이 활용되며,
이는 dp 테이블이라는 배열의 구조로 많이 활용하게 된다.
dp 의 경우, 개념이 상대적으로 추상적인 알고리즘이다보니, 개념만으로는 적용하기 어려울 수 있으니,
많은 예제를 풀어보자