다이나믹 프로그래밍 (Dynamic Programming) / 동적 계획법

 

다이나믹 프로그래밍( 동적 계획법 ) 이란?

한 번 연산된 값을 반복하여 연산하지 않도록 이미 연산된 값을 메모리에 저장하는 방식이다.

 

 

대표적인 예 : 피보나치 수열

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예로는 피보나치 수열이 있다.

 

출처 : 위키피디아

 

위와 같이 정의가 된 피보나치 수열은

F(3) = F(1) + F(2)

F(4) = F(2) + F(3)

...

으로 계산이 되므로 반복적인 계산이 나온다.

이전에 계산된 F(3)을 메모리에 저장해 둔다면, F(4)를 계산할 때, F(3)을 다시 계산하지 않아도 된다.

 

 

문제 풀이 방식

다이나믹 프로그래밍의 풀이 방식은 두가지로 나뉜다.

 

탑다운 방식 ( Top-Down 방식 )

큰 문제를 해결하기 위해 작은 문제를 호출하는 방식으로 재귀함수로 푸는 방법이다. ( 하향식 방법 )

탑다운은 메모이제이션 기법을 사용하는데, 메모이제이션 기법이란 한번 구현된 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 메모이제이션은 캐싱(Caching)이라고도 한다.

 

위의 피보나치 수열을 탑다운 방식으로 풀어보자.

var dp = [Int](repeating: 0, count: 101)

dp[1] = 1
dp[2] = 1

//피보나치 수열
func fibo(_ n: Int) -> Int {
	if dp[n] != 0 {
    	return dp[n]
    }
    
    dp[n] = fibo(n-1) + fibo(n-2)
    return dp[n]
}

 

 

보텀업 방식 ( Bottom-Up 방식 )

작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식으로 for문으로 푸는 방법이다. ( 상향식 방법 )

탑다운 방식과는 달리 작은 수에서 큰 수로 올라가며 계산한다. 이 방식에서 사용되는 배열을 DP 테이블 이라고 한다.

위의 피보나치 수열을 보텀업 방식으로 풀어보자.

var dp = [Int](repeating: 0, count : 101)

dp[1] = 1
dp[2] = 1

func fibo(_ n: Int) -> Int {
	for i in 3...n {
    	dp[i] = dp[i-1] + dp[i-2]
    }
    
    return dp[n]
}

 

 

탑다운에 쓰이는 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문에 보통 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 더 권장한다.

 

 

예시문제

 

백준 1463번 : 1로 만들기

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

1463번: 1로 만들기

 

풀이 방법

let x = Int(readLine()!)!

var dp = [Int](repeating: 0, count: x+1)

for i in 2..<x+1 {
    dp[i] = dp[i-1] + 1
    
    if i % 2 == 0 {
        dp[i] = min(dp[i], dp[i/2] + 1)
    }
    if i % 3 == 0 {
        dp[i] = min(dp[i], dp[i/3] + 1)
    }
}

print(dp[x])