[알고리즘] 동적 계획법(Dynamic Programming)

Algorithm - DP(Dynamic Programming)

동적 계획법 Dynamic Programming의 조건은 두 가지가 있다.이는 바로 최적 부분 구조(Optimal Substructure), 중복되는 부분 문제(Overlapping Subproblems)이다.

최적 부분 구조

최적 부분 구조가 있다는 것은 -> 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것을 의미한다.

fib(5)를 구하려면, fib(4)와 fib(3)을 구하는 부분 문제를 먼저 해결해야 한다. 이 점에서, 피보나치는 최적 부분 구조를 갖고 있다.

중복되는 부분 문제

재귀 함수 -> 부분문제 를 봤었음. fib(5)를 해결하기 위해 fib(4)와 fib(3)이라는 부분문제를, fib(4)를 해결하기 위해 fib(3)과 fib(2)를 구해야 한다. fib(3)을 구하기 위해 fib(2)와 fib(1)을 구해야 하는데, 이 두개는 고정된 값이므로 여기서부터 시작한다. 이 경우를 보면, 중복되는 부분 문제가 있다. (fib(3)을 두번 계산). fib(7)을 구하는 과정에서 fib(5), fib(4), fib(3)을 여러 번 계산해야 한다. 이는 중복되는 부분 문제로, 이는 매우 비효율적이다. 이를 해결하는 게 DP(Dynamic Programming)이다.

합병 정렬을 보자. merge-sort = ([16, 11, 6, 13, 1, 4, 10, 7])이 있다고 해보자. 이를 4개짜리 리스트 [16, 11, 6, 13], [1, 4, 10, 7]로 나눈다. 이후 이를 또다시 합병 정렬을 한다. 이 두 가지를 해결하는 과정은, 겹치는 게 없는 완전히 독립적이다. 즉 중복되지 않는 부분문제(Non-Overlapping Subproblem)이다.

Dynamic Programming

어떤 문제에 대해 최적 부분 구조가 있다는 것은 -> 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것을 의미한다. 즉 기존 문제를 부분 문제로 나눠서 풀 수 있다. 근데 이럴 때 중복되는 부분 문제들이 있을 수 있다. 이 경우 똑같은 문제를 여러 번 풀어야 한다는 비효율성이 발생한다. 이런 비효율을 해결하는 알고리즘이 DP이다.

1. 최적 부분 구조가 있고,
2. 중복되는 부분 문제들이 있을 경우

-> DP로 문제를 해결한다.

DP를 간단하게 설명하면, 한 번 계산한 결과를 재활용하는 방식이다. 그러니까, 중복되는 문제를 한 번만 풀고 기억해두는 것이다. 피보나치를 예로 들면, fib(7)를 구하기 위해 fib(6), fib(5), fib(4), fib(3)을 여러 번 계산해야 되는데, 이를 한 번씩만 계산하게 한 것이다.