Dynamic Programming
🤔 Dynamic Programming이란?
🙋♂️
동적 계획법은 영문은 다이나믹 프로그래밍이지만,
본질적으로 기억하며 풀기로 이해하는 것이 적절합니다.
답을 구하기 위해서 했던 계산을 계속해야 하는 최적 부분 구조의 문제에서 동적 계획법이 효과를 발휘합니다.
복잡한 문제를 해결하기 위해
- 문제를 작은 하위 문제들로 나누어서, 그 해답을 저장하고
- 재사용해서
중복 계산을 피하는 것을 말합니다.
🤔 메모이제이션, 타뷸레이션
🙋♂️
동적 계획법에서 두 가지 방식이 있습니다.
Top-Down 방식 (메모이제이션)
큰 문제에서 작은 하위 문제로 나아가서, 계산된 결과를 재사용하는 방식입니다.
이러한 과정을 통해 중복 계산을 피할 수 있으며,
재귀를 사용하는 상황에서 캐싱하여 효율성을 높일 수 있습니다.
- 필요한 하위 문제만 계산하기 때문에, 필요한 결과만 저장하여 메모리를 절약합니다.
- 비교적 직관적으로 간결하게 파악이 가능합니다.
Bottom - Up 방식 (타뷸레이션)
작은 문제부터 풀어나가면서 결과를 저장하고, 그 결과들을 사용해 큰 문제를 해결합니다.
작은 하위 문제부터 차근차근 해결해나가기 때문에,
결과를 표로 정리해나가는 방식입니다.
반복문을 사용하여 문제를 해결합니다.
- 작은 문제를 모두 계산하여, 모든 결과를 저장해서 메모리 사용이 증가됩니다.
- 메모리 사용량이 예측이 가능하고,
- 반복문 사용으로 인해 덜 직관적일 수 있습니다.
결국, 큰 문제를 해결하기 위해 작은 하위 문제들로 나누는 것이 동적 계획법의 기본 바탕이 되는 것입니다.
그리고 작은 문제들을 저장하고, 재사용이 가능해야 합니다.
🤔 예시 코드
🙋♂️
피보나치 수열 문제를 통해서 이해를 해보도록 하겠습니다.
먼저, 피보나치 수열이란 무엇일까요?
0112358…
나열한 순서처럼
이전 두 개의 숫자를 더해서 다음 숫자를 구하는 수열을 말합니다.
수열: 일정한 규칙에 따라 숫자들을 순서대로 나열한 것
메모이제이션 방식)
var momo: [Int: Int] = [:]
func fibMemo(_ n: Int) -> Int {
if let result = momo[n] {
return result
}
if n <= 1 {
return n
}
let result = fibMemo(n - 1) + fibMemo(n - 2)
momo[n] = result
return result
}
재귀적으로 계산을 하고, 이미 계산된 값은 memo 딕셔너리에 있는 값을 가져와 중복 계산을 방지합니다.
fibMemo(5)를 호출하면, fibMemo(4)와 fibMemo(3) 한 번만 계산하고 결과를 확인할 수 있게 되는 것입니다.
타뷸레이션 방식)
func fibTabul(_ n: Int) -> Int {
if n <= 1 {
return n
}
var dp = [0, 1]
for i in 2...n {
dp.append(dp[i - 1] + dp[i - 2])
}
return dp[n]
}
저장할 배열을 만들어주고,
차례대로 계산을 하면서 결과를 확인합니다.
🤔 정리
🙋♂️
동적 계획법은
- 문제를 작은 문제로 나누고,
- 그 결과를 저장해 중복 계산을 피하는 알고리즘입니다.
두 가지 방식이 있는데
메모이제이션은 재귀적으로 하위문제를 해결합니다.
타뷸레이션은 작은 문제부터 차례대로 해결합니다.
이러한 방식은 결국 문제를 효율적으로 풀기 위해 사용되는 것이고,
- 피보나치 수열
- 배낭 문제
등등 문제에 대해 동적 계획법을 생각해볼 수 있습니다.