[Algorithm] Dynamic Programming(DP; 동적계획법)

오늘은 알고리즘 기법 중 Dynamic Programming에 대해 알아보도록 하겠습니다.

 

동적 프로그래밍, 다이나믹 프로그래밍, DP, 동적 계획법 등 다양한 이름으로 불립니다.

알고리즘의 핵심은 문제를 작은 하위 문제들로 나누고 하위 문제들의 값을 캐싱하고 활용하여 큰 문제를 해결한다는 점입니다.

 

접근법

DP는 두 가지 접근법이 존재합니다.

1. 탑다운(Top-Down) 방식: 재귀와 캐싱

2. 바텀업(Bottom-Up) 방식: 반복문을 통한 DP

 

DP의 활용 예제로는 피보나치(Fibonacci) 함수 구현이 있습니다.

탑다운(Top-Down) 방식

var cache = [Int: Int]()

func fibonacci(_ n: Int) -> Int {
    if let result = cache[n] { return result }
    if n <= 1 { return n }
    
    cache[n] = fibonacci(n-1) + fibonacci(n-2)
    return cache[n]!
}

fibonacci(10) // 55

 

기존에 n-1와 n-2로 나누어 함수를 호출하던 탑다운 재귀 방식에서 n번째 값을 저장하여 함수의 중복 호출을 막을 수 있습니다.

바텀업(Bottom-Up) 방식

func fibonacci(_ n: Int) -> Int {
    if n <= 1 { return n }
    var dp = [0, 1]    
    for i in 2...n {
        dp.append(dp[i-1] + dp[i-2])
    }
    
    return dp[n]
}

fibonacci(9) // 45

 

피보나치 수열의 1번째, 2번째 항을 먼저 저장해두고, 반복문을 통해 항을 추가해나갑니다.

이와같이 구현하면 탑다운 방식과 비교하여 함수 호출에 대한 오버헤드를 줄일 수 있다는 장점이 있습니다.

 

핵심

 

DP의 핵심은 다음과 같습니다.

1. 문제를 작은 문제로 나누기

2. Caching 데이터 

3. 점화식

4. 최소 단위 조건(가장 작은 문제가 무엇인가?)

 

예제

이번엔 백준(BOJ)에서 DP 알고리즘 문제를 가져왔습니다.

https://www.acmicpc.net/problem/2579

출처: https://www.acmicpc.net/problem/2579

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
   즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

마지막 계단에 도착했을 때의 얻을 수 있는 최대 점수를 구하시오.

계단의 수 N과 각 계단의 점수 M이 N개 주어진다.

Example 1:
  Input:
6
10
20
15
25
10
20
  Output:
75

 

먼저 문제를 작은 단위로 나누는 작업부터 해봅시다.

예제에서 계단에 따른 점수:
  1   2   3   4   5   6
[10, 20, 15, 25, 10, 20]

 

규칙대로라면 마지막 계단인 6번째 계단을 가기 위해서는 이전에 어떤 계단을 밟았더라도 반드시 5번째 혹은 4번째 계단에 도착해야합니다.

또한 만약 5번째 계단에서 올라왔다면 연속된 세 개의 계단을 밟을 수 없기 때문에 반드시 3번째 계단에서 올라왔을 것입니다.

결과적으로 이전계단을 밟다가 4번째 계단을 밟는 것과 3번째 계단을 밟는 것 + 5번째 계단의 점수 중에 더 큰 값을 구하면 되겠습니다.

그렇다면 문제는 4번째 계단에 도착했을 때와 3번째 계단에 도착했을 때의 최대 점수를 구하는 것으로 나뉘었습니다.

 

의사코드를 작성해봅시다.

// Pseudocode
func stair(i: Int) {
    // 최소 단위 조건 code
    return max(stair(i-2), stair(i-3) + point[i-1])
}

 

그렇다면 어떤 데이터를 캐싱해야할까요?

이미 n번째 계단까지의 최대 값을 알고 있다면, 다시 구할 필요가 없습니다.

var cache: [Int: Int] // Key: Stair Index, Value: Max Point

// Pseudocode
func stair(i: Int) {
    // 최소 단위 조건 code
    // 이미 계산 값이 있다면 바로 리턴
    if let value = cache[i] else { return value }
    
    // 없다면 계산해서 저장 후 리턴
    let value = max(stair(i-2), stair(i-3) + point[i-1]) 
    cache[i] = value
    return value
}

 

이제 최소 단위 문제는 무엇일까요?

마지막 계단부터 시작했으니, 계단을 오르기 시작하는 순간이 최소 단위일 것입니다.

의사코드에서 이후의 호출에서 i가 0보다 작아지는 경우는 i가 2일 때입니다.

따라서 i가 2이하일때의 조건을 주면 되겠습니다.

if i == 0 { return point[0] } // 첫 번째 계단
else if i == 1 { return point[0] + point[1] } // 두 번째 계단
else if i == 2 { return max(point[0], point[1]) + point[2] } // 세 번째 계단

 

이제 코드를 합쳐봅시다.

var point: [Int] = []
var cache: [Int: Int] = [:] // Key: Stair Index, Value: Max Point

// Pseudocode
func stair(_ i: Int) {
    // 최소 단위 조건 code
    if i == 0 { return point[0] } // 첫 번째 계단
    else if i == 1 { return point[0] + point[1] } // 두 번째 계단
    else if i == 2 { return max(point[0], point[1]) + point[2] } // 세 번째 계단
    
    // 이미 계산 값이 있다면 바로 리턴
    if let value = cache[i] else { return value }
    
    // 없다면 계산해서 저장 후 리턴
    let value = max(stair(i-2), stair(i-3) + point[i-1]) 
    cache[i] = value
    return value
}

cache = [:]
point = [10, 20, 15, 25, 10, 20]
stair(point.count - 1)
// 10 -> 20 -> 25 -> 20 : 75

cache = [:]
point = [10, 30, 10, 50, 10, 20, 10]
stair(point.count - 1)
// 10 -> 30 -> 50 -> 20 -> 10 : 120

 

Conclusion

DP 문제는 차근히 문제를 나누고, 최소 조건만 빠르게 찾는다면 쉽게 풀어날 수 있는 유형이라고 생각합니다.