1. 기초 동적 계획법(Basic Dynamic Programming)
Basic Dynamic Programming
•
부분 문제를 해결한 결과를 이용하여 전체 문제를 해결합니다.
•
"나"를 해결함으로써 "나"를 해결하는 구조입니다.
Ex) 피보나치 수열
•
분할 정복법과 차이는 큰 문제를 독립적으로 나누는 것과 달리, 작은 "나"를 해결한 결과를 계속해서 사용한다는 점입니다.
•
따라서, 작은 소문제를 먼저 모두 기억해 놓는 것이 동적 계획법의 아이디어라고 말할 수 있습니다.
•
분할 정복법은 Top-Down Approach, 동적 계획법은 Bottom-Up Approach 방법입니다.
//MARK: - Function
func solution() -> Void {
//MARK: - Input
guard let n: Int = Int(readLine() ?? "0") else { return }
var fibonacci: [Int] = Array(repeating: 0, count: n + 10)
//MARK: - Process
fibonacci[0] = 0
fibonacci[1] = 1
if n >= 2 {
for i in 2...n {
fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]
}
}
//MARK: - Output
print(fibonacci[n])
}
Swift
복사
2. 동적 계획법의 문제 풀이 순서
Tip
•
부분 문제를 정의 -> 무슨 값을 구할지를 정의합니다.
•
점화식을 구함 -> 그 값을 어떻게 구할지에 대한 식을 세웁니다.
•
문제를 해결 -> 코드를 작성합니다.
3. 중급 동적 계획법(Intermediate Dynamic Programming)
Intermediate Dynamic Programming
•
[1, 2, -4, 5, 3, -2, 9, 10] 다음과 같은 수열에서 연속부분최대합을 구하는 문제에 대해
•
완전탐색의 경우 O(N^2), 분할정복법의 경우 O(N log N)의 시간복잡도로 해결할 수 있습니다.
•
동적계획법을 활용하면 이 문제를 O(N)으로 해결할 수 있으므로, 해당 문제에 대해 위 3가지 알고리즘 중에 가장 효율적인 알고리즘이라고 할 수 있습니다.
•
가장 빠르고, 구현도 쉽지만 구현까지 오는데 과정이 제일 복잡하므로, 동적 계획법의 경우는 키보드에서 손을 떼고, 종이와 펜으로 설계를 정확하게 하는데 초점을 맞추는 것이 좋습니다.
4. 동적 계획법 정리
Tip
•
부분 문제를 정의하는 것이 가장 어려운 부분입니다.
•
문제가 "재귀적으로 해결되는지"(나를 통해 나를 해결할 수 있는지)를 볼 줄 알아야 합니다.
•
무조건 많은 예제를 풀어보아야 합니다.