[알고리즘] 동적계획법(DP , Dynamic Programming)

 

동적계획법(DP , Dynamic Programming) 이란

큰 문제를 작은문제로 나누어 푸는 문제를 말합니다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 말하고 일반적인 방법에 비해 빠른 시간 내에 풀때 사용합니다.

 

분할 정복과 유사하지만 차이점은 작은 문제가 중복이 일어나는지에 대한 유무 입니다. 분할정복은 작은 문제에서 반복이 일어나는 부분이 없습니다.

 

 

 

동적계획법 의 조건

 

부분 반복 문제

-> 어떤 문제가 여러개의 부분 문제로 쪼개질 수 있을때를 의미합니다.

 

최적 부분 구조

-> 부분 문제의 최적 결과 값을 사용하여 전체 문제의 최적 결과를 낼 수 있는 경우를 말합니다.

 

 

 

 

예를 들어 피보나치 수열 f(5)의 값을 구하기 위해서는 f(4) 의 값 + f(3) 의 값 으로 나눌수 있습니다. ( 부분 반복 문제 )

f(4) 의 값은 또 f(3) 의 값 + f(2) 의 값으로 나눠 지는데 위의 f(3) 의 값과 중복이 일어남으로 값을 저장 시켜 놓으면은 재귀를 통해 구현했을때보다 속도가 빠릅니다.

f(n) = f(n-1) + f(n-2) 을 보았을때 f(n)이 최적의 답이 되기 위해서는 f(n-1) 과 f(n-2) 가 최적의 답이 되어야합니다 ( 최적 부분 구조 ) -> 작은 부분 문제의 최적의 답으로 큰 문제의 최적의 답을 구할 수 있어야 합니다.

 

 

 

동적계획법 의 구현방식

 

동적 계획법으로 문제를 해결하기 위해서 크게 2가지 방법이 존재합니다.

 

Top-Down 방법 -> 말 그대로 위에서 아래로 접근하는 방식으로 재귀 호출을 이용하여 풀이가 가능합니다

func fibonacci(_ n: Int) -> Int {
	if n <= 1 { return n }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

 

 

Bottom-Up 방법 -> 아래에서 위로 접근하는 방법으로 부분 문제에서 부터 점차 큰 문제를 풀어가는 방식입니다.

func fibo(_ n: Int) -> Int{
    var dp: [Int] = Array(repeating : 0, count : 101)
     
    dp[1] = 1
    dp[2] = 1
    
    for i in 3...100{
        dp[i] = dp[i-1] + dp[i-2]
    }

    return dp[n]
}

 

 

 

 

 

왜 사용해야할까 or 나만의 고민

어떤 문제가 여러개의 부분 문제로 쪼개질 수 있을때 또한 쪼개진 문제가 최적임을 보장하고 중복된 값이 다수 존재할때 dp 를 사용하여 실행속도를 빠르게 할수있음