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

정의

 

복잡한 문제를 작은 하위 문제로 나누고,

그 하위 문제의 결과를 저장해서 재활용함으로써

전체 문제를 효율적으로 해결하는 알고리즘 설계 기법

 

👉 동일한 계산을 반복하지 않고 기억해서 반복을 줄이는 것

 

 

 활용 경우

 

1. 중복되는 부분 문제

동일한 계산을 여러 번 반복하게 되는 구조

ex) 피보나치 수열

f(n) = f(n-1) + f(n-2)

이때 f(n-2)는 f(n-1)에서도 필요하고, f(n)에서도 필요해서 중복 호출이 발생합니다.

이걸 일반 재귀로 풀게 될 경우, 같은 값(f(3), f(2) 등)을 여러 번 계산을 하게되어, 굉장히 비효율적이게 되겠죠?

이럴 때 DP를 사용하면 중복을 없애고 한번 계산한 결과를 저장해서 재사용하게 되어, 효율적으로 계산할 수 있게 됩니다.

 

2. 최적 부분 구조 문제

전체 문제의 최적해가 하위 문제의 최적해로 구성됨

ex) 배낭 문제

• N개의 물건이 있고, 각각의 무게와 가치가 주어졌을 때
• 배낭의 최대 무게 제한을 넘기지 않도록 하면서
• 담을 수 있는 최대 가치를 구하는 문제

이때, 전체 배낭의 최적 상태는 앞에 있는 물건들을 담았을 때의 최적 상태 를 바탕으로 결정이 됩니다.

즉, 작은 문제들의 최적해가 큰 문제의 최적해를 구성하는 구조라는 뜻이죠.

 

설계 원칙

 

DP 문제는 항상 정형화된 패턴을 따른다고 합니다. 따라서 순서를 정해서 접근하는게 좋아요.

그 순서를 피보나치 수열 문제를 예시로 설명을 해볼게요.

 

1. 하위 문제 정의하기(= 점화식 세우기)

전체 문제를 하위 문제들로 나누는 수학적 정의

- 문제를 작은 문제들로 어떻게 나눌 수 있을까?

피보나치의 경우에는

f(n) = f(n-1) + f(n-2)

👉 "현재 값은 이전 두 값을 더해서 구할 수 있다." 라고 정의할 수 있겠죠.

 

2. DP 테이블 정의하기

DP 테이블이란 하위 문제의 결과를 저장할 구조입니다.

보통 dp[i]는 i번째 상태의 최적해로 정의합니다.

- 결과를 저장하려면 어떤 구조를 써야할까?

피보나치의 경우에는

val dp = IntArray(n + 1)

dp[i] = f(i) 값을 의미합니다.

👉 배열을 사용해서 계산한 값을 저장하시면 되겠죠?

 

3. 초기값 설정

가장 작은 문제들의 해는 직접 계산 가능하므로, 시작점을 잘 잡아야합니다.

- 가장 작은 문제의 답은 무엇인가?

피보나치의 경우에는

dp[0] = 0

dp[1] = 1

👉 f(0) = 0, f(1) = 1을 생각하시면 됩니다. 가장 작은 문제 !

 

4. 점화식을 이용해 테이블 채우기

순서대로 테이블을 채우면서 전체 문제 해결

- 앞에서 정의한 점화식을 반복문으로 어떻게 구현할까?

피보나치의 경우에는

for (i in 2..n) {
    dp[i] = dp[i - 1] + dp[i - 2]
}

👉 dp[0]과 dp[1]은 이미 이전 단계에서 초기값 설정으로 구했기 때문에 2부터 반복문을 시작해줍니다.

그럼 dp[2] = dp[1] + dp[2], dp[3] = dp[2] + dp[1] 이런 식으로 반복되겠죠.

 

구현 방법

 

1. Top-Down(재귀 + 메모이제이션)

- 큰 문제 -> 작은 문제로 나아감

- 재귀 사용

- 하위 문제의 결과를 저장(메모이제이션)

val memo = IntArray(100) { -1 }
// 크기가 100인 IntArray를 만들고, 초기값을 -1로 채웁니다. 계산할 결과를 저장하는 배열이죠.
// memo[n] = f(n)을 의미해요. -1은 아직 계산되지 않았음을 의미합니다.

fun fib(n: Int): Int {
    if (n <= 1) return n // 재귀 종료 조건이에요. f(0) = 0, f(1) = 1이기 때문에 이 두 경우는 직접 값을 반환해줍니다.
    if (memo[n] != -1) return memo[n] // 이미 계산된 값이면, 바로 반환합니다. memo[n]에 저장된 값이 있다면, 다시 계산할 필요없이 꺼내 써요. = 메모제이션 
    memo[n] = fib(n - 1) + fib(n - 2) // 계산이 안된 경우에는 재귀적으로 호출해서 구합니다. 그리고 그 결과를 memo[n]에 저장하죠.
    return memo[n]
}

 

 

2. Bottom-Up(반복문)

- 작은 문제 -> 큰 문제로 나아감

- 반복문으로 구현 👉 재귀를 사용하지 않아 스택 오버플로우 걱정이 없음

- DP 테이블을 순차적으로 채움

fun fib(n: Int): Int {
    if (n <= 1) return n
    val dp = IntArray(n + 1) // dp[i] = i번째 피보나치 수를 저장, 배열 인덱스가 0부터 시작하므로 dp[n]까지 저장하기 위하여 n+1칸으로 정의
    dp[0] = 0
    dp[1] = 1
    for (i in 2..n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

 

👉 성능

시간 복잡도: Top-Down, Bottom-Up(= O(n)) > 재귀(= O(2ⁿ))

공간 복잡도: Bottom-Up(O(n) 또는 O(1)) >= Top-Down, 재귀(= O(n))