[Algorithm] 동적 계획법

알고리즘 스터디 DP팀 발표 내용 및 SW Expert Academy 동적 계획법 강의 내용을 참고하였습니다.

정의

동적 계획법(Dynamic Programming)은 최적화 문제를 해결하는 알고리즘이다.

그리디 알고리즘과 비슷하게, 이 알고리즘 역시 문제를 해결하기 위한 논리에 가깝다. 그리디 알고리즘이 그랬듯, 완전 탐색을 조금 더 효율적으로 하기 위한 문제 해결 방법이기도 하다.

구현

최적해를 구하기 위해 큰 문제를 부분문제로 분할 하는 방식을 사용한다. 작은 부분 문제들의 해를 구하고, 이를 이용해 더 큰 크기의 부분 문제들을 해결하는 것이다.

구현에 있어 핵심이 되는 기술은 재귀와 메모이제이션이다.

재귀 란, 문제를 재귀적으로 정의해서 해결하는 것을 의미한다. 재귀 함수를 사용한다는 의미가 아니다. 문제를 재귀적으로 정의하고, 점화식을 찾아 수식 형태로 표현해야 한다.

메모이제이션 이란, 프로그램 실행 시 이전에 계산한 값을 메모리에 저장해서 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술이다.

특징

적용할 수 있는 문제

문제가 중복 부분문제 구조, 최적 부분문제 구조를 가지고 있을 때 적용할 수 있다.

1. 중복 부분문제
   • 작은 문제들의 최적해를 이용해 순환적으로 큰 문제를 해결하는 구조.
   • 순환적 성질 때문에, 이전에 계산한 작은 문제의 해를 더 큰 문제의 해를 구할 때 중복해서 사용.
     • 이미 해결된 작은 문제의 해를 저장 공간에 저장.
     • 작은 문제의 해들이 다시 필요할 때마다 저장 공간을 참조해 중복 계산을 피함.
2. 최적 부분문제
   • 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해도 최적이어야 함.

쉽게 말해, 답을 재활용하는 것이다. 최적의 답을 찾기 위해 문제를 쪼개고, 앞에서 구한 답을 뒤에서도 이용하고, 옆에서도 이용하고, 계속해서 사용할 때 이 알고리즘을 적용한다.

비교

문제를 작은 부분으로 나눈다는 점에서 분할정복 알고리즘과 자주 비견된다. 부분문제를 사용해 더 큰 문제를 구한다는 것은 공통점이다. 그러나 다음의 영역에서 차이가 있다.

1. 부분 해의 중복 사용

분할정복의 경우, 부분 문제를 재귀적으로 해결한 뒤, 필요한 경우 부분문제의 해를 결합한다. 큰 문제의 해가 작은 문제의 해를 포함한다는 의미이다. 그러나, 작은 문제의 해를 큰 문제에서 중복하여 사용하지는 않는다.

“병합정렬, 퀵정렬 등의 알고리즘을 재귀적으로 구현할 때, 중복 호출의 문제가 없었다.”는 점을 돌이켜 보자.

그러나 동적 계획법의 경우, 부분문제들의 해가 더 작은 부분문제들의 해를 공유한다. 모든 부분문제를 한 번만 사용하는 것이 아니라, 결과를 저장해 놓고 필요하면 중복하여 사용하게 된다.

1. 부분해의 의존 여부

분할정복의 경우, 부분해는 분할 전 포함되어 있던 더 큰 부분문제의 해를 구할때만 사용된다. 반면 동적 계획법의 경우, 분할 전 포함되어 있지 않았다 하더라도 다른 더 큰 부분문제를 해결할 때 중복해서 사용될 수 있다.

^{출처 : SW Expert Academy - 파이썬 SW문제해결 응용 - 최적화 - 동적 계획법의 소개}

위 그림에서 E, F, G의 해가 C를 해결하는 데 사용된다. 또한, 부분문제 E와 F는 부분문제 B를 해결하는 데도 중복해서 사용된다.

결과적으로, 분할정복의 경우 하향식 방법으로 주어진 문제를 더 이상 나눌 수 없을 때까지 쪼개서 해결하는 반면, 동적 계획법은 상향식 방법으로 각 부분 간 의존성을 해치지 않게 작은 문제에서 더 큰 문제 순서로 해결해 나가야 한다.

” 대부분의 DP 문제에서 의존 관계는 문제에 따라 다르고, 뚜렷하게 파악되지 않는다. 그래서 이 순서를 함축된 순서라고 한다. 문제를 많이 풀어 보고, 수학적으로 생각하는 습관을 들이자.”

적용

피보나치 수열

피보나치 수열을 구하는 문제를 생각해 보자.

^{출처 : 위키피디아 - 피보나치 수}

재귀함수를 사용한 구현

def fibo(n):
    if < 2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

피보나치 수열을 재귀함수로 구현한 알고리즘이다. 가장 일반적이다. 이 알고리즘에서는 아래와 같이 중복 호출이 발생한다는 치명적 인 문제가 있다.

^{출처 : SW Expert Academy - 파이썬 SW문제해결 응용 - 최적화 - 동적 계획법의 소개}

위와 같은 중복 호출의 문제점으로 인해 재귀 함수로 구현한 피보나치 수열 함수의 시간 복잡도는 2의 n제곱 에 비례하여 증가하게 된다.

메모이제이션을 추가한 구현

재귀로 구현한 함수에 메모이제이션을 더해 시간복잡도를 O(n)으로 줄일 수 있다.

def fibo_memo(n):
    if n >= 2 and memo[n] == 0:
        memo[n] == fibo_memo(n-1) + fibo_memo(n-2)
    return memo[n]

최초에 메모 리스트를 할당한다. 해당 메모 리스트는 피보나치 수열의 매개변수인 0부터 n까지의 값을 인덱스로 하여, 피보나치 수열의 n번째 수를 저장한다.

기본 케이스로 n이 0일 때와 1일 때, 즉 memo[0]과 memo[1]을 각각 0과 1로 초기화한다. 다른 위치의 수들은 모두 0으로 초기값을 설정한다.

함수가 호출되면, 다음의 경우에 따라 나누어 동작한다.

• 처음 호출되는 경우(n값이 2 이상이면서, 메모 리스트에 저장된 값이 0인 경우), n-1과 n-2에 대해 재귀 호출을 통해 결과를 반환한다. 그리고 메모 리스트에 결과값을 저장한다.

• 이미 저장되어 있는 값이 있는 경우(memo[n] != 0), 바로 메모 리스트에서 값을 반환한다.

시간 복잡도는 줄어들 수 있지만, 메모리라는 추가적인 공간을 사용한다. 또한, 재귀 호출이 누적되면서 시스템 호출 스택의 누적으로 실행 속도가 저하되고 스택오버플로우가 발생할 수 있다.

두 경우 모두, 재귀를 사용하는 것이 문제가 된다. 그렇다면 동적 계획법을 사용해 재귀를 사용하지 않고 문제를 풀어보자.

동적 계획법을 사용한 구현

피보나치 수열을 구하는 문제는 동적 계획법을 적용할 수 있는 대표적인 문제이다. 즉, 부분문제의 답으로부터 전체 문제의 답을 얻을 수 있는 구조로 되어 있다는 의미이다.

n번째 수를 구하는 문제는 n-1번째 수를 구하는 문제와 n-2번째 수를 구하는 문제로 분할된다. 그리고 가장 작은 문제부터 해를 구한 뒤, 상위 문제를 해결해 나가면 된다.

테이블에 작은 부분문제의 결과를 저장하고, 그 결과를 이용해 더 큰 문제의 결과를 구하도록 동적 계획법을 적용해 알고리즘을 구현하면 다음과 같다.

def fibo_DP(n):
    f[0] = 0
    f[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] + f[i-2]
    return f[n]

문제를 저장할 테이블로 리스트 자료구조(f)를 활용할 수 있다. 가장 작은 문제는 n이 0과 1일 때이다. 각각의 경우에 0과 1을 저장한다.

이제 n이 2 이상일 때부터, 반복문을 이용해 작은 부분문제의 해를 이용해 더 큰 문제를 구해 나간다. 재귀적 정의를 이용해 재귀적 정의를 이용하면, i번째 피보나치 수는 i-1번쨰, i-2번째 수를 더한 값이 된다.

반복이 종료되면 n번째 인덱스에 해당하는 값을 구하면 된다.

반복문을 사용하기 때문에, 함수의 중복 호출이 발생하지 않는다. 계산하는 항의 개수는 n+1이다. 테이블의 0번부터 n번 인덱스까지, 값을 한 번씩만 계산해서 저장하면 된다.

당연히, 동적 계획법을 적용한 알고리즘이 수행 속도가 훨씬 빠르다.

초기화

출처

실제로 문제에 적용할 때 가장 중요한 것으로, 메모이제이션 외에 초기화도 있다.

동적 계획법의 핵심은, 이미 계산한 값을 다시 계산하지 않는다는 논리이다. 이를 구현하기 위해서는, 메모한 테이블 상에 계산하지 않은 값(초기값)과 계산한 값(초기값에서 바뀐 값)에 차이가 있어야 한다.

따라서 문제를 보고, 계산한 값의 범위를 대략적으로 알아내고, 그 범위에 있지 않은 값으로 테이블을 초기화하는 것이 매우 중요하다.