동적계획법 DP(Dynamic Programming)

동적계획법

- 큰 문제의 답을 얻기 위해, 작은 문제로 나누어 답을 저장하고 재활용한다.

- 분할정복 알고리즘과 비슷하지만, 작은문제로 나누어 해결하고 답을 재활용하며 반복해나간다는 점에서 차이가 있다.

- DP는 나누어진 모든 작은문제들을 한번씩 풀고 그 답을 저장해놓는다. 그다음 큰 문제를 위해 저장해둔 작은 문제를 활용하여 풀어나간다.

- DP를 이용하려면, 작은 문제가 반복적으로 일어나야한다.

 

Memoization

- 동일한 계산을 반복하는경우, 한번 계산한 결과를 메모리에 저장해 두었다가 필요할때 꺼내쓰는 기법이다.

- 일반적으로 반복계산을 했을때 메모리 할당의 중복 비용을 줄여주고, 계산에 소요되는 시간 비용을 줄여준다.

- DP의 핵심기법

 

DP 의 예시) 피보나치수열

피보나치 수열 fib(n) = fib(n-1) + fib(n-2)을 일반적으로 계산했을때, 재귀함수를 호출하여 계산한다.

import Foundation

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

fib(4)

= fib(3) + fib(2)

= fib(2) + fib(1) + fib(1) + fib(0)

= fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

---> fib(4)를 구하기 위해 fib함수 5번 수행되었다.

이와같이 일반적으로 계산하는 경우 fib(n)의 n이 커질수록 계산횟수는 기하급수적으로 증가하게된다. 시간복잡도 O(n^2)

 

DP의 Memoization기법을 이용하면 시간복잡도를 줄일 수 있다.

import Foundation

func fibonacci(_ num: Int) -> Int {
    var dp = Array(repeating: 0, count: num+1)
    if num == 1 || num == 2 {
        return 1
    }
    for i in 1...num {
        if i < 3 {
            dp[i] = 1
            continue
        }
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[num]
}

예로 fib(5) 를 구하기위해

dp[3] = dp[2] + dp[1] = fib(3) 을 저장후 dp[4]를 구할 때 재사용

dp[4] = dp[3] + dp[2] = fib(4) 도 저장후 dp[5]를 구할 때 재사용

dp[5] = dp[4] + dp[3] = fib(5)

 

위의 방법은 for문 한번만 돌기때문에 시간복잡도는 O(N) 이다.

재귀함수 호출하는 일반적인 계산방법보다 더 빠르게 계산한다.

 

DP는

1. 겹치는 동일한 작은 문제들의 반복성

2. 작은 문제들의 최적의 결과를 이용해 전체 결과를 낼 수 있는지

 

문제에서 DP를 이용 할 수 있는지 파악하는게 젤 어렵긴하다.

1. 큰 문제를 반복되는 작은 문제로 나눌 수 있는지

2. 점화식을 구현할 수 있는지 ( 1번이랑 비슷함)

3. 결과값을 최신화 하며 해결해나가면 결국 문제의 답이 나오는지..

 

 

-------------------------------------------------------

틀린부분과 추가할 부분이 있다면 댓글 남겨주시면 감사합니다~

 

 

글을 쓸때 참고한곳:

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 나무위키

https://galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?