다이나믹 프로그래밍(DP)이란 무엇일까 ?

Dynamic Programming (동적 계획법)이란 ?

동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다. 

예를 들어 코딩 테스트 문제를 풀다 보면 아래와 같은 제한사항이 종종 나오는데, 간혹 제한사항에 주어지는 숫자의 범위가 크고 경우의 수가 엄청난 값의 문제들이 대부분 DP를 이용해서 풀어야 하는 것이라고 알게 되었다.

 

Dynamic Programming 알고리즘 조건 

1) problem이 sub-problem으로 나누어 질 때

2) 각 sub-problem의 solution을 통해 상위 problem의 솔루션을 구할 수 있을 때

3) sub-problem들이 중복되며, 그 문제의 솔루션이 같을 때 → memoizaion

위 세 가지 조건을 충족하는 문제는 dynamic programming으로 해결할 수 있으며, 대표적인 예시로 피보나치 수열이 있다.

 

동적계획법의 2가지 접근 방법

▶ Bottom - up 방법

아래서 위로 접근하는 방법으로 부분 문제에서부터 문제를 해결하여 점차 큰 문제를 풀어가는 방식이다. 반복문을 이용하는 방식이 이에 해당한다.

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

cache[1] = 1
cache[2] = 1

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

▶ Top - Down 방법

위에서 아래로 접근하는 방법으로, 큰 문제에서 부분 문제로 쪼개가면서 재귀 호출을 통해 문제를 푸는 방법이다.

//범위보다 1크게
// cache[0] 초기값 상태 0으로 모두 채워줌
var cache = [Int](repeating: 0, count: 101)

cache[1] = 1
cache[2] = 1

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