다이나믹 프로그래밍(DP)

점화식

인접한 항들 사이의 관계식.

 

각 항을 a_n 이라 할때, 피보나치 수열의 점화식은 다음과 같이 표현할 수 있다.

a_n+2 = f(a_n+1, a_n) = a_n+1 + a_n

 

결과적으로 피보나치 수열에서는 첫 번째 항과 두 번째 항의 값이 모두 1이기 때문에 아래처럼 나타낸다.

a_n = a_n-1 + a_n-2, a₁ = 1, a₂ = 1

• n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수
• 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1

점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용한다.

 

- 피보나치 함수

static int fibo(int n) {
    if (n == 1 || n == 2) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

 

그러나 위 방법은 O(2^N) 이라는 심각한 시간복잡도를 기록한다.

 

그림을 보면 동일한 F(3)이 반복해서  호출된다. 이는 n이 커지면 커질수록 반복해서 호출되는 함수가 많아짐을 의미한다.

 

 

 

 

 

 

방법 1) Top - Down (재귀적)

메모이제이션(Memoization) : 다이나믹 프로그래밍을 구현하는 방법 중 하나. 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져온다. -> 리스트, 배열에 저장

static int[] d = new int[100];  // 메모이제이션 배열

// 피보나치 수열 - Top Down
static int fibo(int n) {
    // 종료 조건 (1 or 2일때 1반환)
    if(n == 1 || n == 2) return 1;
    // 이미 계산한 적 있는 문제라면 그대로 반환
    if(d[n] != 0) return d[n];
    // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[n] = fibo(n - 1) + fibo(n - 2);
    return d[n];
}

 

위 메모이제이션에서는 아래 그림처럼 F(6)을 호출하면 한 번 푼 문제는 그 결과를 이용하기 때문에 아래 노드만 방문한다.

DP 방식 시간복잡도 : O(N)

 

방법 2) Bottom - Up (반복문)

int[] d = new int[100]; // DP 테이블

// 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1;
d[2] = 2;

// 피보나치 함수 반복문으로 구현 (Bottom Up)
for(int i=3; i<100; i++) {
    d[i] = d[i-1] + d[i-2];
}

System.out.println(d[99]);

다이나믹 프로그래밍

• 탑다운(Top Down) : 재귀함수 (메모이제이션)
• 바텀업(Bottom Up) : 반복문 (DP 테이블)

가능하다면 재귀함수를 이용하는 탑다운 방식보다는 바텀업 방식으로 구현하자.