동적 계획법(Dynamic Programming, DP)은 알고리즘 설계 기법 중 하나로, 복잡한 문제를 단순한 여러 개의 하위 문제로 나누어 해결하는 방법입니다.
이 글에서는 스위프트 언어를 사용하여 동적 계획법을 적용하는 방법을 배워보고, 실제 알고리즘 문제를 통해 이론을 실습하는 기회를 가지려고 합니다.
동적 계획법의 기초
동적 계획법은 주어진 문제를 최적 부분 구조에 따라 나누어 해결하는 방식입니다.
기본적으로 두 가지 주요 요소가 있습니다: 메모이제이션(Memoization)과 타뷸레이션(Tabulation).
메모이제이션은 재귀적으로 풀어진 문제의 결과를 저장하여 중복 계산을 피하는 방법이고,
타뷸레이션은 하위 문제의 결과를 테이블에 저장하여 바텀 업 방식으로 문제를 해결하는 것입니다.
문제 소개: 피보나치 수열
피보나치 수열은 자연수의 수열로, 처음 두 개의 항이 0과 1이며,
그 이후의 항은 바로 앞의 두 항을 더한 값으로 정의됩니다.
즉, F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2)입니다.
피보나치 수열을 계산하는 효율적인 방법을 구현하면서 동적 계획법의 개념을 이해해봅시다.
문제 풀이 과정
1. 문제 파악하기
피보나치 수열의 n번째 항을 구하는 문제입니다.
간단한 정의는 있지만, 재귀적 방법으로 구현할 경우 중복 계산이 발생하여 비효율적입니다.
2. 동적 계획법 적용
동적 계획법을 사용하면 중복 계산을 피할 수 있습니다.
특히 하위 문제에서 이미 계산된 결과를 저장하고 재사용함으로써 시간 복잡도를 줄일 수 있습니다.
여기서는 메모이제이션 방식을 사용하여 문제를 해결하겠습니다.
3. 메모이제이션 구현
메모이제이션은 재귀 함수에 추가적인 변수를 사용하여 이전에 계산한 결과를 저장하는 방식입니다.
스위프트로 코드를 작성해 보겠습니다.
func fibonacci(_ n: Int, _ memo: inout [Int?]) -> Int {
if let value = memo[n] {
return value
}
if n <= 1 {
memo[n] = n
return n
}
memo[n] = fibonacci(n - 1, &memo) + fibonacci(n - 2, &memo)
return memo[n]!
}
func fibonacciWrapper(n: Int) -> Int {
var memo = Array(repeating: nil, count: n + 1)
return fibonacci(n, &memo)
}
// 호출 예
let result = fibonacciWrapper(n: 10)
print(result) // 출력: 55
4. 시간 복잡도 분석
메모이제이션을 사용한 피보나치 수열의 시간 복잡도는 O(n)입니다.
각 n에 대해 한 번만 계산하고 결과를 저장하므로 효율적인 성능을 보여줍니다.
공간 복잡도 역시 O(n)입니다.
5. 타뷸레이션 방법으로 구현하기
이번에는 타뷸레이션 방법을 사용하여 동일한 문제를 해결해보겠습니다.
이 방법은 하위 문제의 결과를 테이블에 저장하여 바텀업 방식으로 접근합니다.
스위프트로 코드를 작성해 보겠습니다.
func fibonacciTabulation(_ n: Int) -> Int {
if n <= 1 { return n }
var dp = Array(repeating: 0, count: n + 1)
dp[0] = 0
dp[1] = 1
for i in 2...n {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}
// 호출 예
let resultTabulation = fibonacciTabulation(n: 10)
print(resultTabulation) // 출력: 55
6. 결론
이번 글에서는 스위프트를 사용하여 동적 계획법의 기본 개념을 배우고,
피보나치 수열 문제를 통해 메모이제이션과 타뷸레이션 기법을 실습해 보았습니다.
동적 계획법은 다양한 알고리즘 문제에서 활용될 수 있는 강력한 도구이며,
이론을 잘 이해하고 활용하는 것이 코딩 테스트에서도 큰 도움이 될 것입니다.