다이나믹 프로그래밍

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

다이나믹 프로그래밍이란?

동적 계획법이라고도 하며,  큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

 

다이나믹 프로그래밍 구현 방법

1. 작은 문제들을 한번만 푼다.
2. 정답을 구한 문제의 답을 어딘가에 메모한다.
3. 다시 그 문제가 나오면 앞서 메모한 작은 문제의 결과값을 이용한다.

 

다이나믹 프로그래밍을 사용하기 위한 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

위 두 조건이 만족해야 동적 프로그래밍을 사용할 수 있다.

피보나치 수열은 이러한 조건을 만족하는 가장 대표적인 문제이다. 

 

다이나믹 프로그래밍과 분할 정복의 차이 

가장 큰 차이점은 작은 문제가 중복되는지 안되는지이다.

분할정복은 큰 문제를 해결하기 어려워 작은 문제로만 단순하게 나누어 푸는 방법이고, 다이나믹 프로그래밍은 작은 문제들이 반복되는 것이다. 

 

시간 복잡도 

다이나믹 프로그래밍의 시간 복잡도는 O(N)이다.

왜냐하면 f(1)을 구한 값이 f(2)를 푸는데 사용되고 f(2) 값이 f(3)을 푸는데 사용되기 때문이다.

 

메모제이션이란?

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한번 구한 결과를 메모리 공간에 메모해두고 같은 문제를 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.

메모제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다.

 

메모제이션 구현 방법

1. 단순하게 한번 구한 답을 배열에 저장한다.
2. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 답이 필요할 때는 이미 구한 답을 배열에서 가져와 사용한다.

 

탑다운 방식

재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

하향식이라고도 하며 메모제이션 기법은 탑다운 방식에 국한되어 사용되는 기법이다.

let n = 6
var memoizationArr = Array(repeating: 0, count: n + 1)

func fibo(x: Int) -> Int {

    if x == 1 || x == 2 {
        return 1
    }
    
    if memoizationArr[x] != 0 {
        return memoizationArr[x]
    }

    memoizationArr[x] = fibo(x: x - 1) + fibo(x: x - 2)

    return memoizationArr[x]
}


print(fibo(x: n)) // 8

 

바텀업 방식

단순히 반복문을 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

상향식이라고도 하며 다이나믹 프로그래밍의 전형적인 형태이다.

let n = 6
var dpTable = Array(repeating: 0, count: n + 1)

dpTable[1] = 1
dpTable[2] = 1

for i in 3..<dpTable.count {
    dpTable[i] = dpTable[i - 1] + dpTable[i - 2]
}

print(dpTable.last!) // 8

 

 

피보나치 수열로 다이나믹 프로그래밍을 예로 들면 아래와 같은 형태로 끝없이 이어진다.

1번

위 형태를 그래프로 그려서 보면 아래와 같은 그래프가 된다.

2번

위 그림에서 보이듯이 동일한 함수가 반복적으로 호출되는것을 볼 수 있다. 이미 한번 계산했지만 계속 호출할 때마다 계산하는것이다. 

그림에서 f(3)이 총 3번 호출되었는데 즉, f(n)에서 n이 커지면 커질수록 반복되어 호출되는 수가 많아진다.

이러한 문제점을 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.

 

위 문제를 메모제이션 기법을 이용하여 그려보면 아래 그림처럼 색칠된 노드만 방문하게 된다.

실선으로 표현된 노드들은 사실상 호출되지 않는다고 이해하면 된다.

왜냐하면 호출하더라도 따로 계산하지 않고 배열에서 값을 가져오거나 바로 1을 반환하기 때문이다.

다만, 재귀함수를 이용하게 되면 컴퓨터 시스템에서는 함수를 다시 호출했을때 메모리 상에 적재(스택)되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다.

따라서, 재귀 함수 대신 반복문을 사용하여 오버헤드를 줄일 수 있다.

일반적으로 반복문을 이용한 다이나믹 프로그래밍이 성능이 더 좋기 때문이다. 

3번

위 그림이 실제로 호출되었을 때는 아래 그림과 같이 호출된다.

4번

위 그림 소스코드로 확인해보기

let n = 6
var memoizationArr = Array(repeating: 0, count: n + 1)

func fibo(x: Int) -> Int {
    
    print("f\(x)")
    if x == 1 || x == 2 {
        return 1
    }
    
    if memoizationArr[x] != 0 {
        return memoizationArr[x]
    }

    memoizationArr[x] = fibo(x: x - 1) + fibo(x: x - 2)

    return memoizationArr[x]
}

print(fibo(x: n)) // 8

// 호출결과
// f6 f5 f4 f3 f2 f1 f2 f3 f4

 

---