Browsed by
태그: 백준

다이나믹 프로그래밍 정리

다이나믹 프로그래밍 정리

다이나믹 프로그래밍 (DP)는 한 마디로 정의하기 어렵다. DP라고 알려져있는 대표 문제들도 뜯어보면 풀이가 다 달라서 초보 입장에서는 DP라는걸 곧바로 떠올리기가 쉽지 않다. 내가 내린 결론은 다이나믹 프로그래밍은 “문제를 푸는 방법”에 대한 정의라기 보다는 “문제 자체에 대한 정의”에 가깝다. 그러니까 “이 문제는 DP를 사용해서 푸는 것이다”가 아니라 “이 문제는 DP 문제이다”가 더 적절한 판단인 것이다.

최근에 DP문제들을 한 30문제 정도 풀면서 DP문제란 무엇인가에 대한생각을 정리해 보았다.

다이나믹 프로그래밍의 정의

이름만 보면 이 단어의 감을 잡기가 쉽지 않다. 유래를 보면 이 모호함이 사실은 의도된 것임을 알 수 있다. 이 단어를 처음 쓴 수학자 리처드 밸만은 남들이 모르게끔 지었다고 회상한다(출처 : 위키백과).

나는 RAND 코퍼레이션에서 1950년의 가을을 보냈다. 여기에서 내게 주어진 첫 과제는 다단계(multistage) 의사 결정 프로세스에 대해 적절한 용어를 명명하는 것이었다. ‘동적 계획법’이라는 이름이 어디에서 왔는지 궁금하지 않은가? 1950년대는 내가 수학에 대해 연구하기에는 좋지 못한 시기였다. 우리는 그 때 워싱턴에서 윌슨이라는 사람과 함께 일하고 있었다. 윌슨은 연구라는 것에 대해 굉장히 병적인 공포를 가지고 있었다. 사람들이 그 앞에서 연구에 대해 이야기를 꺼내면 그는 완전히 미치다시피 했다. 그러나 불행히도 RAND는 공군 소속의 회사였고, 윌슨은 그 공군의 간부인 국방 위원장이었다. 그래서 내가 RAND 안에 있었을 때 윌슨을 비롯한 공군들이 내가 수학에 대해 연구하는 것을 보이지 않게 막는다는 것을 알 수 있었다. 처음 올 때는 나는 위의 문제에 대해 ‘의사 결정 프로세스’라는 이름을 사용했지만, 여기에서 ‘프로세스(Process)’라는 단어를 사용하는데 여러가지 차질이 생겨버리고 만 것이다. 그래서 나는 사람들이 알지 못하게 ‘계획법(Programming)’이라는 단어를 붙였다.

또한 나는 이 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, ‘동적(Dynamic)’이다라는 개념(idea)이 전달되길 원했다. 이 단어야말로 내가 연구하는 알고리즘의 성질을 정확하게 짚어내었고, 게다가 윌슨에게도 피해를 입히지 않으며 공군도 이 단어에선 꼬투리를 잡지 못했으니 그야말로 일석이조의 효과를 누린 것이다.

리처드 밸만은 “의사 결정 프로세스”에 대한 연구를 하고 싶었던 모양이지만, 내가 문제를 풀면서 또 여기저기 강의나 블로그 글을 찾아보면서 알아낸 DP의 정의는 “문제 푸는 법”이라기 보다는 “문제의 특성”자체였다. 내가 생각한 DP 문제란:

  1. 해당 문제는 모든 경우의 수를 탐색해야 풀리는 문제다. (브루트 포스나 그리디 알고리즘과 같다)
  2. 작은 문제의 정답들을 활용해서 큰 문제를 풀 수 있다. (재귀적으로 풀 수 있다)
  3. “큰 문제의 정답”이 “작은 문제의 정답”에 영향을 미치지 않는다 (Directed acyclic graph)

그리고 DP문제를 푸는데에 쓰이는 방법은:

  1. 기본적으로 모든 경우의 수를 탐색한다.
  2. 모든 경우의 수를 탐색할 때, 작은 문제들의 정답을 이용해서 큰 문제의 정답을 탐색한다.
  3. 한 번 계산한 문제의 답은 변하지 않으니까, 계산한 후에는 저장해두고 필요할 때마다 꺼내쓴다. (메모이제이션)

아래부터는 대표 DP 문제들로 위의 특성들을 어떻게 가지고 있는지 확인한다.

대표 문제 1 : 피보나치 수열

DP의 대표적인 문제는 피보나치 수열이다. 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다(출처 : 위키백과).

DP 문제인가?

  1. F(n)을 알기 위해선 F(n-1)과 F(n-2)를 알아야한다. F(n-1)을 알려면 F(n-2)와 F(n-3)을 알아야한다. 이대로 계속 하다보면 F(0)부터 F(n-1)까지의 값을 모두 알아야 F(n)을 풀 수 있다는 것을 알 수 있다.
  2. F(n)을 위해서는 F(n-1)과 F(n-2)가 필요하다. 수식 자체 재귀적이며, 함수 종료 조건은 n== 0 또는 n==1임을 알 수 있다.
  3. F(n)을 알아냈다고 해서 F(n-1)과 F(n-2)값이 바뀌지 않는다. 따라서 이 값들은 영원히 활용할 수 있다.

어떻게 푸는가?

  1. F(n)을 구할 때마다 다른 배열에 저장해둔다(메모이제이션). 그리고 더 큰 피보나치 값을 구할 때마다 꺼내 쓴다.

대표 문제 2 : LIS(백준 링크)

LIS(최장 증가 수열,Longest Increasing Subsequence)는 증가하는 수열 중 가장 긴 수열을 찾는 문제이다. 수열 {10, 20, 10, 30, 20, 50}가 있다면 LIS는 {10, 20, 10, 30, 20, 50}를 골라서 총 길이 4가 된다.

DP문제인가?

  1. 함수를 정의한다. LIS(n)은 n번째 숫자를 포함했을 때의 LIS의 길이를 구하는 함수로써, max(n-1번째 까지의 숫자들 중 n보다 낮은 숫자들로 이뤄진 LIS 중 가장 긴 LIS의 길이 + 1)이다. 예를 들면 LIS(4)는 {10, 20, 10, 30, 20, 50}에서 4번째 30을 까지의 LIS를 구하는 함수로서, LIS(3) = 2에 30을 포함시켜 LIS(4) = LIS(3) +1 ={10,20,30}의 길이 = 3이다. LIS(5)의 경우는 {10,20}이므로 2이다. 현재 LIS의 길이를 알기 위해서는 이전 LIS들의 길이를 알아야 한다. 결국 최종 LIS는 max(LIS(1),…, LIS(n))이다.
  2. LIS(n)을 알기 위해서는 LIS(1)부터 LIS(n-1)까지의 값이 필요하다.
  3. LIS(n)을 알아낸다고 해서 이전 LIS값들이 변하지 않는다.

어떻게 푸는가?

  1. LIS(n)을 구하기 위해서는 LIS(1)부터 LIS(n-1)까지의 값들이 구해져 있어야한다. 이들의 값을 다른 배열에 저장해둔다(메모이제이션).
  2. LIS(1)부터 LIS(n)까지 다 구했다면, max(LIS(1),…, LIS(n))를 하여 최종 값을 구한다. (LIS(n)이 항상 최고로 높은 값이 아니다! 따라서 LIS(1)부터 LIS(n)까지 중 최댓값을 최종적으로 한 번 구해줘야한다.)

DP와 메모이제이션의 관계

이번에 다시 공부하기 전까지 “DP”와 “메모이제이션”의 관계를 제대로 이해하지 못했다. 보통 DP를 하면 당연히 메모이제이션 기법이 사용되기 때문에, DP와 메모이제이션이 동의어가 아닌가? 라고 생각했지만 엄연히 다르다.

DP문제에서 “큰 문제의 답”을 알기 위해서 “작은 문제의 답”을 알아야하는데, 작은 문제들이 한 번만 계산되는 경우는 적다. 완전탐색 문제를 재귀적으로 풀다보면 똑같은 문제를 반복적으로 푸는 일이 종종 발생하고, 이 때문에 문제풀이 시간과 필요한 메모리가 비약적으로 늘어나게 된다. 예를 들면 아래 나올 “피보나치 수열” 문제를 보면, F(n-2)부터 여러 번 계산되는 상황이 발생한다.

  1. F(n)을 구하고 싶다.
  2. 그러기 위해서는 F(n-1)과 F(n-2)를 구해야한다.
  3. F(n-1)을 구하기 위해서는 F(n-2)와 F(n-3) 이 필요하다. 즉 , F(n) = F(n-2)2 + F(n-3)이다.
  4. F(n-2)를 구하기 위해서는 F(n-3)과 F(n-4)가 필요하다. 즉, F(n) = F(n-3)3 + F(n-4)*2이다.

이 때 F(n-2), F(n-3)… 값들을 한 번만 계산한 후, 어디에 적어놓고 꺼내 쓴다면 최초 한 번만 계산하고 그 이후에는 O(1)의 시간에 가져와서 쓸 수 있다. 이렇게 “계산해 둔 값을 저장해두고 꺼내 쓰는 것”을 메모이제이션이다.

즉, DP가 문제 자체에 대한 특성이라면, 메모이제이션은 DP문제 해결에 사용되는 위한 기법이다.