DP(동적계획법)

안녕하세요. KataRN입니다.

 

오늘은 DP에 대해 알아보겠습니다.

 

DP란 탈영병들을 잡는 병사들을 일컫는... 죄송합니다.

 

DP(Dynamic Programming)란 ?

일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

출처 : 나무위키

 

핵심은 저장입니다.  Memoization(메모이제이션)이라고 불리기도합니다.

동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장하여 반복 수행을 줄이고 프로그램 실행 속도를 빠르게 합니다.

 

오늘도 피보나치수열로 예를 들어보겠습니다.

우선 재귀함수부터 보도록 하겠습니다.

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

 

여기에 DP를 적용하여 함수를 만든다면 아래처럼 바뀝니다.

func fibo(_ n: Int) -> Int{
    var cache: [Int] = [0, 1]
    
    for num in 2...n {
        cache.append(cache[num - 1] + cache[num - 2])
    }
    return cache[n]
}

cache라는 저장공간을 활용해서 작은 수들의 값을 계속 저장해나갑니다.

그리고 필요할때 불러서 사용함으로 반복수행이 없어 실행속도가 빠릅니다.

 

오늘의 내용은 아래 블로그에서 더 친절하게 설명하고있습니다.

오늘도 읽어주셔서 감사합니다.

 

출처 : https://babbab2.tistory.com/100

Swift) 동적 계획법 (Dynamic Programming) 이해하기