DP - new

DP 알고리즘에 대해 이전에 정리했으나 다시 리마인드하는 느낌으로 정리한다.

 

DP

DP, 동적 계획법은 큰 문제를 작은 문제로 분할해서 결과를 저장하고 재사용하는 것을 의미한다. 피보나치 수열을 예시로 생각해보면 다음과 같다.

 

1, 1, 2, 3, 5, ...

피보나치 수열은 다음과 같은 형태를 지니고 있다. 

 

def recursion(n):
    if n <= 2:
        return 1
    return recursion(n - 1) + recursion(n - 2)

재귀에 대해서는 따로 설명하지는 않겠지만 return을 살펴보면 recursion(3) 이라고 했을 때, recursion(2) - recursion(1)으로 두 번의 함수 호출을 하는 것이 보인다. 여기에서 recursion(2)의 실행을 다시보면 recursion(1) + recursion(0)으로 recursion(1)에 대해서 또 다시 호출하는 상황이 발생하게 될 것이다.

 

즉, 입력받는 n의 숫자가 커지면 커질수록 반복해서 함수를 호출하고 연산하는 일이 기하급수적으로 증가되기에 컴퓨터는 이 연산에 대해서 처리하는데 오랜 시간이 걸리게 될 것이다.

 

여기에서 만약, recursion(1)에 해당하는 값을 저장하고 이 값을 꺼내서 사용한다면 어떻게 될까? 시간 복잡도는 O(n^2)에서 O(n)으로 줄어들 수 있을 것이다. (단, 상황에 따라 시간 복잡도의 계산은 다를 수 있다.) 여기서 미리 값을 구해 저장하고 꺼내 사용한다는 재사용이라는 것이 바로 DP의 개념이다.

 

DP 사용 조건

그렇다면 DP는 대체 어느 때 사용해야할까? 사실 위의 예제에서 조금 나타나긴 했는데 값을 저장해 꺼내 사용하기에 해당 연산에 대해 변하지 않고 동일할 때 사용하는 알고리즘이라고 생각한다.

 

피보나치 수열의 예시를 다시 생각해보면 결국 도출하고자 하는 것은 recursion(1), recursion(2), ...의 형태이고 recursion(n) = recursion(n - 2) + recursion(n - 1)으로 1부터 n까지의 미리 구해둔 값을 통해 n의 결과를 리턴해주면 되는 것이기에 recursion 자체로써의 연산을 변하지 않으므로 DP를 사용할 수 있는 것이다.

 

두번째로 사용할 수 있는 조건은 최적의 결과값을 낼 수 있는 경우이다. 특정 케이스에 대해 가장 최적이 될 수 있는 해를 저장하여 꺼내서 사용한다면 이 또한 DP를 사용할 수 있다는 뜻이다.

 

대충 이론을 통해 정리했으니 여러 문제를 풀어보기로 한다.