[Swift Algorithm Note] 동적 계획법 (feat. Fibonacci)

그리디 문제를 풀다가,, 도저히 안풀리는 문제를 맞닥뜨리고..

알고보니 LIS라는 풀이 방법을 이용하는 문제였다. 

근데 LIS는 DP(동적 계획법)을 사용해야 가장 효율적이라고 하더라..

따라서 오늘은 동적 계획법에 대해 공부해본 결과를 정리해보려고 한다.

 

📎 동적 계획법 (Dynamic Programming)

동적 계획법은 이름과는 좀 매칭이 안되는듯.?..한데

한 문제를 작은 부분으로 나누어 풀고,

그 결과를 저장하여 상위 문제를 풀어내는 상향식 접근 알고리즘이다.

 

위의 설명을 따르면

동적 계획법을 언제 사용할 수 있는지 구체화할 수 있다. 👇

1. 같은 반복을 시행하는 부분이 존재한다.
2. 동일한 반복 연산의 결과가 일정해야한다.

 

📌  Memoization

추가로, 위 설명을 다시 한 번 보면

작은 부분을 나누어 푼 결과를 '저장'한다고 적어놓았다.

바로 이 부분이 동적 계획법의 핵심이다❗️

 

메모이제이션은 한 번 계산된 결과를 다음 반복에서 다시 사용할 수 있도록 저장해두는 것을 말한다.

이 메모이제이션을 통해 동적 계획법은 프로그램의 실행을 더 효율적으로 할 수 있게 해준다.

 

👉 DP 문제를 풀 때, 시간 초과가 나는 경우에는

무조건 이 메모이제이션이 제대로 되고 있는지 확인해봐야한다.

이미 한 번 계산한 값을 중복해서 또 계산하게 되는 순간 그건 DP가 아니다.

---

📎 피보나치 수 계산 구현

이전 재귀함수 글에서도 피보나치 수 계산을 구현했는데,

동적 계획법을 사용하면 피보나치 수를 더 효율적으로 구할 수 있다고 한다,.,!!!

따라서 오늘도 피보나치 수를 한 번 구해보자.

import Foundation

func Fibo(_ n: Int) -> Int {
    var memory = [0, 1]
    
    for i in 2...n {
        memory.append(memory[i - 1] + memory[i - 2])
    }

    return memory[n]
}

print(Fibo(4)) // 3

동적 계획법으로 구현한 피보나치 수 계산은 배열을 만들어 계속 연산의 결과를 저장함을 반복한다.

그리고 저장된 연산의 결과를 다음 반복에서 사용하여 또 연산, 저장을 계속한다.

 

이렇게 구현한 코드가 왜 재귀함수로 구현한 코드보다 더 효율적인지 살펴보자.

(재귀함수로 구현한 피보나치 수 계산은 요기👇를 참고해주세요!)

2021.07.09 - [📍 Algorithm Note/🔍 with Swift] - [Swift Algorithm Note] 꼬리 재귀 함수 (feat. Fibonacci)

 

📌  피보나치 수 계산의 구현 방법에 따른 효율성

재귀함수와 동적 계획법 각각의 실행 과정을 비교하여 효율성을 따져보자.

 

#1 재귀 함수로 구현

만약 n으로 4를 입력했을 경우 위 그림과 같이 시행되는데,

Fibo(2)를 두 번 계산했고, Fibo(1)은 세 번, Fibo(0)은 두 번 계산했다.

 

위에서 말했듯 DP는 동일한 계산을 두 번하지 않도록 memoization 방식을 사용한다.

굳이 같은 시행을 반복할 필요는 없으므로, 한 번 계산한 값은 저장해두고 사용해야 효율을 높일 수 있다.

 

여기서는 작은 값을 대입해서 케이스를 확인했지만,

더 큰 수를 입력할 경우라면 중복되는 시행이 무수히 많아지게 된다.

 

#2 동적 계획법으로 구현

위와 같이 배열을 생성하고,

앞의 두 요소를 참고하여 새로운 연산 결과를 추가하는 시행을 반복한다.

따라서 아무리 큰 수라도 중복되는 시행없이 풀이가 가능하다.

---

👀 정리

동적 계획법의 개념과 구현 방법까지 알아보았다.

 

동적 계획법은 한 마디로, '저장의 반복'이라고 요약하고싶다.

 

동적 계획법은 지금까지 단순 구현 문제에서도 나도 모르게 많이 사용했던 방법인 것 같다.

쉬운 문제에서는 내가 쓰는게 동적 계획법인지 뭔지도 모르고서도 잘 썼지만

조금 더 복잡한 문제들을 접하면서는 언제 dp를 사용할 수 있는지,

그리고 사용할 때의 효율성 등을 정확히 알고 있을 필요가 있다.