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

 

 

 

안녕하세요:) 소들입니다

오랜만에 포스팅을 하는 것 같네요..!

아마 1월 달엔 자료구조 + 알고리즘에 대한 포스팅이 주일 것 같고..

2월달부턴 다시 iOS + Swift에 대한 포스팅을 할 예정입니다 :)

 

오늘 공부할 것은 동적 계획법, 줄임말로 DP라고 하는 것인데

정의에 대해 알아보려고 해요 :)

 

늘 느끼지만 알고리즘의 정의?는 참 어렵지 않은데,

이를 어떻게 응용해서 풀지가 어려운 것 같아요 =_=

쨌든 공부해봅시다~~ 모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 동적 계획법이란?

 

Dynamic Programming으로, DP라고 많이 부르는데,

 

상향식 접근법으로, 가장 작은 부분의 해답을 구한 후,

이를 저장하여, 저장한 값을 이용해 상위 문제를 풀어가는 방식

 

을 말함 💩

자, 여기서 중요한 단어는 "작은 부분의 해답"과 "저장"하여,

"상위 문제를 해결" 한다는 것임

 

호옹.. "저장"이라..!

 맞음..! 동적 계획의 핵심은 Memoization(메모이제이션)이라는 기법인데,

동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장하여 반복 수행을 제거하여

프로그램 실행 속도를 빠르게 한다는 말임!

 

호에.. 이건 예제로 보는 게 쉬움 :)

 

 

 

 

2. 피보나치 수열로 이해하기

 

자, 피보나치 수열이란 것으로 동적 계획법을 이해해보려고 함

피보나치 수열이 뭐냐면

 

0, 1, 1, 2, 3, 5, 8, 13 ...

 

이런 식으로, 가장 처음 0, 1을 제외하고

내 앞에 위치한 두 놈을 더해서 나를 만드는 것이 피보나치 수열임

따라서 다음과 같은 점화식을 만들 수 있음!!!

 

 

 

 

이제 이것을 이용하여 n번째 수(0번부터 시작할 경우)를 구하는 코드를

앞서 배운 재귀 함수와 동적 계획법을 이용해 구현하며,

이들의 차이점에 대해 알아보며 동적 계획법에 대해 이해를 해볼 것이셈

 

 

 

2-1. 재귀 함수을 이용한 구현

 

우리가 이전에 배운 재귀 함수로 구현한다면,

 

 

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

 

 

이렇게 간단하게 구현할 수 있음!!!

근데 만약 4번째 수를 구하기 위해 다음과 같이 실행하면,

 

 

fibo(4)

 

 

4번째 결과를 얻기까지 어떻게 되냐면

 

 

 

 

fibo(0)을 구하는 함수를 2번 중복 실행하고,

fibo(1)을 구하는 함수를 3번 중복 실행하고,

fibo(2)를 구하는 함수를 2번 중복 실행해야함

 

자, 피보나치를 쓰면 물론 매우 간단하게 구현할 수 있지만,

하나의 결과값을 도출하는 데 중복되는 값을 얻기위해 실행되는 함수가 너무 많음

(숫자가 커질 수록 프로그램 실행 속도를 떨어뜨리는 것임)

 

따라서, 메모이제이션을 사용하는 동적 계획법으로 다시 짜보자 :))

 

 

 

2-2. 동적 계획법을 이용한 구현

 

자, 동적 계획법은 뭐다??? 메모이제이션! 

즉, 가장 작은 단위부터 계산하고 저장하여, 이를 이용해서 큰 단위 값을 도출한다 했음

따라서 동적 계획법에선, 작은 단위를 저장할 저장공간이 필요함!!

 

 

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라는 저장 공간을 활용해서,

가장 작은 단위인 0, 1 부터 도출되는 값을 계속 저장해 나가는 것임

 만약 4번째 수를 구하기 위해 다음과 같이 실행하면,

 

 

fibo(4)

 

 

4보다 작은 값들인 0, 1, 2, 3번째 값까지를 먼저 구하여 저장하고,

이 값들이 저장되어 있는 메모리를 이용하여,

 

 

 

 

2번째 index + 3번째 index의 값을 더해 구하는 것임..! 

이미 저장되어 있는 값을 활용하는 것이기 때문에, 중복 실행을 할 필요가 없음!!

따라서 실행 속도가 빨라지는 것임 :)

 

 

 

 

3. 동적 계획법 vs 분할 정복

 

분할 정복은 갑자기 머냐? 하겠지

이는 다음 포스팅 예정인 퀵 정렬이나, 합병 정렬 같이 고급 정렬에 쓰는 것인데..!

혹시 이 둘을 알고 계신다면 이 둘은 같은 개념이 아니니 참고만 하셈~!!

(분할 정복에 대해 모르면 Skip~)

 

 

	동적 계획법	분할 정복
공통점	문제를 잘게 쪼개서, 가장 작은 단위로 분할하여 문제를 해결
차이점	- 작은 단위로 쪼개진 문제들은, 상위 문제를 해결하는 데 재사용 됨 - Memoization 기법을 사용함	- 작은 단위로 쪼개진 문제들은, 상위 문제를 해결하는 데 재사용되지 않음 - Memorization 기법을 사용 안함

 

 

 

 

 

 

 

 

.

.

동적 계획법이 이거구나... 하고 느낀 뒤에

프로그래머스에서 동적 계획법으로 분리된 문제를 풀어봤는데..!

재밌기도 하고 이렇게 푸는 거였구나 하면서 풀리니까 신기하기도 하고 :)

나중에 이론 끝나면 알고리즘 문제 풀이 올려 볼게요~~~

그럼 20,000