[Algorithm] DP

다이나믹 프로그래밍

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

• 이미 계산된 결과를(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다.
• 일반적으로 두 가지 방식
  • 탑다운 : Memoization, 큰 문제에서 작은 문제들을 재귀를 통해 호출되며 작은 문제들의 결과를 배열(리스트)에 저장하여 같은 답을 구할 때 미리 계산된 값을 사용
  • 바텀업 : 반복문으로 구현, 작은 문제에서 부터 계산하여 큰 문제의 답을 자연스럽게 구함 (일반적인 DP 방식)

조건

1. 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다.
2. 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 합니다.

예제

가장 쉽고 대표적인 DP 문제인 피보나치를 예를 들 수 있다.
피보나치 문제를 일반적인 재귀로 푼다고 가정할 때 아래의 코드라고 볼 수 있다.

fun fibonacci(n: Int): Int {
	if (x == 1) return 1
    if (x == 2) return 1
    
    return fibonacci(n-1) + fibonacci(n-2)
}

위 코드의 시간 복잡도는 O(2^N) 으로, fibonacci(30) 을 계산하기 위해 약 10억가량의 연산을 수행해야 한다.
따라서, 피보나치 수열을 DP 문제로 치환하여 풀기 위해선 DP 를 적용할 수 있는지 조건을 따져보아야 한다.

• 최적 부분 구조 : 피보나치 문제는 큰 문제를 해결하기 위해 작은 문제로 나누어진다. fibonacci(3) 을 구하기 위해서는 fibonacci(2) 와 fibonacci(1) 을 사용하기 때문
• 중복되는 부분 문제 : 마찬가지로 f(4) 를 구하기 위해서 f(3) + f(2) 를 호출하고, 그 f(3) 을 구하기 위해서는 반복적으로 f(2) + f(1) 을 호출하기 때문에 결과적으로 이 예시에서만 f(2) 를 두번 호출하기 때문에 적용할 수 있다.

그렇다면 피보나치 수열 문제는 DP 문제로 치환하면 효율적으로 풀 수 있다는 것을 알았다.

DP 알고리즘에는 상향식(바텀업)과 하향식(탑다운) 방식이 있다.
피보나치 문제에 하향식 DP 를 적용하면 아래의 코드와 같을 것 이다.

// 계산된 값을 저장하는 DP Table
val dp = Array(N+1) {0}

fun fibonacci(n: Int): Int {
	if (x == 1) return 1
    if (x == 2) return 1
    
 	// 이미 계산한 값이 있을 경우 그 값을 리턴
    if (dp[n] != 0) return dp[n]
    
    dp[n] = fibonacci(n-1) + fibonacci(n-2)
    
    return dp[n]
}

따라서, 하향식 DP 를 적용한 피보나치 문제의 시간 복잡도는 O(N) 이 된다.

이번엔 상향식 DP 를 적용한 코드이다.

val dp = Array(N+1) {0}

fun fibonacci(n: Int): Int {
	dp[1] = 1
    dp[2] = 1
    
    for (i in 3..n) {
    	dp[i] = dp[i-1] + dp[i-2]
    }
    
    return dp[n]
}

본인이 문제에 대해 점화식을 작성할 수 있다면 점화식을 작성한 뒤 그 것을 코드로 옮기면 훨씬 접근하기 쉬울 것 같다.