DynamicProgramming기법이 적용될 수 있는 문제는 우선 DivideAndConquer로 풀 수 있어야 한다. 어떤 복잡한 문제를 subproblem으로 나눠서 풀 수 있다는 사실에 더해서, 그 문제의 해가 Optimal Substructure와 Overlapping Subproblem이라는 특징을 가질 때, 그 문제는 DynamicProgramming으로 풀 수 있다.
optimal substructure를 예를 들어서 설명해보면 다음과 같다. 만일 서울에서 대전까지 가는 데 경부고속도로가 최단거리라고 하면, 경부고속도로를 타고 가는 중에 있는 천안이라는 포인트에 대해서, 서울에서 천안까지의 최단거리는 반드시 경부고속도로 이어야 한다. 만일 서울에서 천안까지 최단거리가 중부고속도로라면, 서울에서 대전까지의 최단거리는 경부고속도로인데, 서울-천안(중부)+천안-대전(경부)<-- 요게 더 짧을 수 밖에 없고, 따라서 서울에서 대전까지 최단거리가 경부고속도로라는 사실에 위배된다. 이러한 문제, 즉, 어떤 문제의 해는 subproblem의 해의 조합으로 이루어질 수 밖에 없을 때, 이러한 문제의 구조를 Optimal Substructure라고 한다. 따라서 subproblem을 푸는 것은 곳 전체 문제의 해를 푸는 것이 된다.
Overlapping Subproblem이라는 것은 A문제를 풀기 위해서, a1,a2,a3를 풀어야 하는데, a1을 풀기위해서는 b1,b2,b3를 풀어야 하고, a2를 풀기 위해서는 b2,b3,b4를, a3를 풀기 위해서는 b3,b4,b5를 풀어야 한다. 만일 이러한 문제를 DivideAndConquer로 풀게 되면, b2,b3,b4,b5를 2번씩 풀어야한다. 이것을 Overlapping Subproblem이라고 한다.
둘의 차이를 간단히 말하자면, Optimal Substructure라는 것은 반드 어떤 문제의 subproblem의 해의 조합으로 원래 문제의 해가 된다는 것이고, Overlapping subproblem은 서로 독립적이라고 생각했던 몇 개의 문제에 대해서, 그것을 풀기 위한 subproblem이 중복됨을 의미한다.
Overlapping Subproblem이라는 것은 A문제를 풀기 위해서, a1,a2,a3를 풀어야 하는데, a1을 풀기위해서는 b1,b2,b3를 풀어야 하고, a2를 풀기 위해서는 b2,b3,b4를, a3를 풀기 위해서는 b3,b4,b5를 풀어야 한다. 만일 이러한 문제를 DivideAndConquer로 풀게 되면, b2,b3,b4,b5를 2번씩 풀어야한다. 이것을 Overlapping Subproblem이라고 한다.
둘의 차이를 간단히 말하자면, Optimal Substructure라는 것은 반드 어떤 문제의 subproblem의 해의 조합으로 원래 문제의 해가 된다는 것이고, Overlapping subproblem은 서로 독립적이라고 생각했던 몇 개의 문제에 대해서, 그것을 풀기 위한 subproblem이 중복됨을 의미한다.
이러한 특징을 가지는 문제에 대해서, DynamicProgramming기법이 적용된다. 먼저 문제의 해에 대해서 고민하여, 그것이 Optimal Substructure를 가지는지, Overlapping Subproblem을 가지는지 살핀다. 만일 두 가지 특징이 모두 있다면, 다음과 같은 방법으로 문제를 풀어나간다. 작은 문제부터 큰 문제로 차근차근 풀어나가되, 푼 문제의 해는 반드시 테이블에 기록해둔다. 바로 직전 것만 기록해야할 경우도 있고, 최초의 문제부터 기록해야만 할 때도 있다. 중요한 것은, 이 문제의 해는 Optimal Substructure가 있으므로, 큰 문제는 반드시 작은 문제를 이용해서 풀릴 수 밖에 없고, 작업속도는 최적화 될 수 밖에 없다는 것이다. 이것이 바로 DynamicProgramming이다.
여기서 "Programming"은 컴퓨터 프로그래밍과는 하등의 상관이 없다. 선형 계획법(Linear Programming)에서의 "Programming"과 비슷하게 보면 된다. DP는 제어 이론(control theory)에서 왔는데, 여기서 Programming은 해가 구성되는 테이블(혹은 배열)의 사용을 의미한다.
DivideAndConquer는 보통 TopDown으로 비유되고, DP는 BottomUp이나 "거꾸로 풀기"로 비유된다.
이렇게 알고 있지만, 이것은 전혀 다른 얘기다. DynamicProgramming이 BottomUp이라고 하는 이유는 Overlapping Subproblem을 효과적으로 다루기 위해서 주로 for문을 이용해서 코딩되기 때문일 뿐이다. DynamicProgramming기법이 적용될 수 있는 문제는 DivideAndConquer로도 당연히 풀리는 문제이며(intractible일 수도 있고.. square일수도 있지만..), DynamicProgramming기법으로 푸는 것이 더 속도가 빠를 뿐이다. 둘을 서로 다른 개념으로 생각하면 오해를 불러일으킬 수 있다. --naya
일상 생활에의 적용 ¶
우선 DivideAndConquer의 일상생활 적용을 고려한다. 그리고, 만일 거기에서 어떤 중복된 subproblem이 있다면, 그걸 바보같이 두 번 세번 하지 말고, 한 번만 하고, 어따가 적어뒀다가 다시 써먹는다!
즉, A라는 계산을 하려고 하는데, B라는 계산결과를 필요로 한다. 만일 내가 B라는 계산을 이미 했던 것이어서, 계산 결과를 어딘가에 적어두었다면, 열라 빨리 문제를 풀 수 있을 것이다. B라는 계산을 이미 했었어도, 계산 결과를 적어두지 않았다면 바보스럽게 또 그 계산을 해야한다. 그래서, 그 결과를 적어뒀다가 다시 이용해먹는다!!!
즉, A라는 계산을 하려고 하는데, B라는 계산결과를 필요로 한다. 만일 내가 B라는 계산을 이미 했던 것이어서, 계산 결과를 어딘가에 적어두었다면, 열라 빨리 문제를 풀 수 있을 것이다. B라는 계산을 이미 했었어도, 계산 결과를 적어두지 않았다면 바보스럽게 또 그 계산을 해야한다. 그래서, 그 결과를 적어뒀다가 다시 이용해먹는다!!!
예> 구구단
A : DynamicProgramming에서의 각 state 들은 독립적이지 않습니다. 바로 전 state 가 현재 state 를 결정하기 때문이죠. 따라서, 중복 계산을 하지 않는다는 것도 특징이지만, 그것보다 더 핵심적이고 결정적인 특징은 Recursion 입니다.
음... 근데 질문이 있는데... DynamicProgramming 에서 Recursion 이 없을 수 있나요? 그리고, 또, Recursion 을 사용하면서, 동시에 중복되게 문제를 풀 수 있나요? 그건 무한 loop 로 빠지게 되지 않나요? --지상은
제가 알기로 dynamic programming에서는 중복된 계산을 하지 않는 것이 매우 중요합니다. matrix chain mulplication 문제의 경우 중복 계산을 하는 경우 exponentinal time이 걸리지만 caching을 하면 polinomial time 에 computing가능합니다. (그 밖에 DynamicProgramming으로 풀 수 있는 문제는 모두 그렇지요..) DynamicProgramming으로 문제를 풀려면 overlapping subproblem과 optimal substructure가 나타나야 합니다. 즉 작은 문제로 나눌 수 있어야 하고 작은 문제의 해답이 큰 문제의 해답을 구성해야 한다는 것입니다. 이 상태에서 그냥 subproblem을 중복해서 풀면서 recursive하게 문제를 풀 수도 있고 subproblem을 caching하면서 recursive하게 (혹은 recursive하지 않게..) 문제를 풀 수도 있습니다. Subproblem을 중복해서 푸는 경우는 DynamicProgramming이라 부르지 않는 것으로 압니다. OrICouldBeWrong --지원
Q : 헉! 강하다. 모르는 얘길 이렇게 많이... 음... 근데 질문이 있는데... DynamicProgramming 에서 Recursion 이 없을 수 있나요? 그리고, 또, Recursion 을 사용하면서, 동시에 중복되게 문제를 풀 수 있나요? 그건 무한 loop 로 빠지게 되지 않나요? --지상은A : Recursion 이 없을 수 있습니다. 똑같은 문제를 DynamicProgramming 사용해서 iterative 하게 풀 수도 있고, recursive 하게 풀 수도 있습니다. (맞나.. -_-;;) 또, Recursion 을 사용하면서 중복되게 문제를 풀더라도 boundary condition 이 있기 때문에 무한 loop 로 빠지는 것은 아닙니다. 예를 들어 피보나치의 수열을 구할 때 n = 0 일 때 P(n) = 1 로 정의해놓고 시작하죠. recursion 을 통해 n 이 점점 작아지다가 0 까지 오면 P(0) 은 1 이므로 거기서 recursion 이 종료되고 P(0) 을 호출한 P(1) 이나 P(2) 로 되돌아 가겠죠.
Q : 헉! 헷갈리는군요. 일단 무엇이 중복인지 부터요. Recursion 에서 중복이 발생하려면, P(2) 가 P(2)를 호출해야만 중복이 발생하는 것이 아닌가요? 이렇게 되면 무한 loop 로 빠지는 것이구요. 제가 생각하기에는 이것 말고는 중복이 발생할 수 있는 여지가 없는 것이 아닌가 싶습니다. P(0), P(1), P(2), ... P(n-1), P(n) 이렇게 계산해 나가는 DynamicProgramming 의 recursion 에서는 중복이 발생할 수 없지 않나 싶군요. 상대적으로 DivideAndConquer 에서의 중복은 예를 들어서, P(2)라는 값이 A라는 subproblem 에서도 필요하고, B라는 subproblem 에서도 필요할때, 모든 기능을 완벽하게 OnceAndOnlyOnce 로 독립시킬수 없기 때문에, 필연적으로 양쪽 subproblem 모두에서 중복된 계산을 할 수 밖에 없다는 것으로 이해했는데, 갈수록 잘못 이해한 것 같은 느낌이 드는군요. ^^; --지상은
A : P(2)와 같이 subproblem을 푸는 과정에서 일반적으로 중복된 계산을 하는 것들 때문에 중복이 발생하고, 이를 여러번 계산하지 말고, 전에 계산했던 결과를 이용하자...라는게 DynamicProgramming 입니다. -- kane
A : 피보나치 수열을 계산하는 것을 생각해보세요. 피보나치 수열은 f(n)=f(n-1)+f(n-2)로 정의됩니다. f(10)을 계산한다고 할 때, f(10)=f(9)+f(8)=(f(8)+f(7))+(f(7)+f(6))=... 과 같이 전개될 수 있습니다. 단순한 Recursion만을 사용하면, f(8), f(7)는 반복해서 계산되게 됩니다. 이 값들을 어딘가에 저장시켜두었다가 필요할 때 사용하면, 반복되는 것을 줄일 수 있습니다. 이렇게 하는 방법을 DynamicProgramming이라고 부릅니다. -- 조민규
Q : overlapping subproblem과 optimal substructure가 뭔가요? (이해가 잘 안되서...) -- kane
A : optimal substructure를 예를 들어서 설명해 드리겠습니다. 만일 서울에서 대전까지 가는 데 경부고속도로가 최단거리라고 하면, 경부고속도로를 타고 가는 중에 있는 천안이라는 포인트에 대해서, 서울에서 천안까지의 최단거리는 반드시 경부고속도로 일 겁니다. 만일 서울에서 천안까지 최단거리가 중부고속도로라면, 서울에서 대전까지의 최단거리는 경부고속도로인데, 서울-천안(중부)+천안-대전(경부)<-- 요게 더 짧을 수 밖에 없고, 따라서 서울에서 대전까지 최단거리가 경부고속도로라는 사실에 위배되는 것입니다. 이러한 문제, 즉, 어떤 문제의 해는 subproblem의 해의 조합으로 이루어질 수 밖에 없을 때, 이러한 문제의 구조를 Optimal Substructure라고 합니다. 따라서 subproblem을 푸는 것은 곳 전체 문제의 해를 푸는 것이 됩니다.
Overlapping Subproblem이라는 것은 A문제를 풀기 위해서, a1,a2,a3를 풀어야 하는데, a1을 풀기위해서는 b1,b2,b3를 풀어야 하고, a2를 풀기 위해서는 b2,b3,b4를, a3를 풀기 위해서는 b3,b4,b5를 풀어야 합니다. 만일 이러한 문제를 DivideAndConquer로 풀게 되면, b2,b3,b4,b5를 2번씩 풀어야겠죠? 이것을 Overlapping Subproblem이라고 합니다. 두 가지가 어떤 차이를 가지고 있는지 아시겠지요? Optimal Substructure라는 것은 반드시 어떤 문제의 subproblem의 해의 조합으로 원래 문제의 해가 된다는 것이고, Overlapping subproblem은 서로 독립적이라고 생각했던 몇 개의 문제에 대해서, 그것을 풀기 위한 subproblem이 중복됨을 의미합니다. --naya
Overlapping Subproblem이라는 것은 A문제를 풀기 위해서, a1,a2,a3를 풀어야 하는데, a1을 풀기위해서는 b1,b2,b3를 풀어야 하고, a2를 풀기 위해서는 b2,b3,b4를, a3를 풀기 위해서는 b3,b4,b5를 풀어야 합니다. 만일 이러한 문제를 DivideAndConquer로 풀게 되면, b2,b3,b4,b5를 2번씩 풀어야겠죠? 이것을 Overlapping Subproblem이라고 합니다. 두 가지가 어떤 차이를 가지고 있는지 아시겠지요? Optimal Substructure라는 것은 반드시 어떤 문제의 subproblem의 해의 조합으로 원래 문제의 해가 된다는 것이고, Overlapping subproblem은 서로 독립적이라고 생각했던 몇 개의 문제에 대해서, 그것을 풀기 위한 subproblem이 중복됨을 의미합니다. --naya
Q : GreedyAlgorithm은 1.Greedy-choice property와 2.optimal substructure 에 해당하는 문제일때 접근가능하고 DynamicProgramming은 1.optimal substructure와 2.overlapping subproblem에 해당할때 접근가능하다고 하는데 Greedy-choice property의 의미가 정확히 구분이 안되는데 설명 좀 부탁드립니다.Greedy-choice property 는 a globally optimal solution can be arrived at by making a locally optimal choice 라고 되있고 optimal substructure는 if an optimal solution to the problem contains within it optimal solutions to subproblems 라고 되있는데 둘다 비슷해 보입니다 ㅡㅡ; 글구 GreedyAlgorithms의 적용가능예로 minimum-spanning-tree과 Dijkstra's algorithm for shortest paths from a single source등이 있는데 이것들은 DynamicProgramming도 적용가능하져? --아무로