최근 프로그래밍 면접에서는 알고리즘과 데이터 구조의 이해를 평가하기 위해 다양한 유형의 문제를 출제합니다. 그중에서도 동적 계획법(Dynamic Programming)은 많은 문제를 효율적으로 해결할 수 있는 강력한 기법으로 자리잡고 있습니다. 이 글에서는 동적 계획법의 원리에 대해 알아보고, 자바스크립트를 이용한 구체적인 문제 풀이 과정을 살펴보겠습니다.
동적 계획법이란?
동적 계획법은 큰 문제를 작은 문제로 나누어 해결하고, 이를 통해 문제의 최적해를 찾는 알고리즘 방식입니다. 주로 최적화 문제에 사용되며, 메모이제이션(memoization) 기법을 통해 중복 계산을 방지하여 성능을 개선합니다.
동적 계획법의 특징
- 문제를 작은 문제로 분할하여 푼다.
- 하위 문제의 결과를 저장하여 중복 계산을 피한다.
- 상태 전이 함수(state transition function)를 사용하여 최적해를 계산한다.
문제 제시: 피보나치 수열
이번 강좌에서는 피보나치 수열을 동적 계획법을 이용하여 계산하는 문제를 다루겠습니다. 피보나치 수열은 다음과 같이 정의됩니다:
F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) (n ≥ 2)
즉, 주어진 정수 n에 대하여 F(n)을 효율적으로 계산해보는 것이 목표입니다.
문제 풀이 과정
1. 문제 분석
피보나치 수열은 재귀적으로 정의되어 있습니다. 하지만 단순한 재귀 호출로 문제를 해결할 경우, 같은 값이 여러 번 계산되므로 비효율적입니다. 이를 해결하기 위해 동적 계획법을 사용하여 접근합니다.
2. 상태 전이 함수 정의
상태 전이 함수는 이미 계산된 하위 문제의 결과를 이용하여 상위 문제를 해결하는 방법입니다. 피보나치 수열의 경우:
F(n) = F(n-1) + F(n-2)
이 함수는 F(n)을 계산하기 위해 F(n-1)과 F(n-2)의 값을 필요로 합니다.
3. 메모이제이션 기법
메모이제이션은 하위 문제의 결과를 캐싱하여 중복 계산을 방지하는 방법입니다. 아래는 자바스크립트를 이용한 메모이제이션을 활용한 예제 코드입니다:
function fib(n, memo = {}) {
// 이미 계산된 값이 있는 경우 리턴
if (n in memo) return memo[n];
// 기저 사례
if (n <= 1) return n;
// 재귀 호출과 메모이제이션
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
// 테스트
console.log(fib(10)); // 출력: 55
4. 테이블 메소드
메모이제이션 외에도 테이블 메소드를 사용하여 동적 계획법을 구현할 수 있습니다. 테이블 메소드는 하위 문제의 결과를 배열에 저장하고 이를 점진적으로 계산해 나가는 방식입니다. 아래는 테이블 메소드를 이용한 피보나치 수열의 구현입니다:
function fibTable(n) {
if (n <= 1) return n;
const fib = new Array(n + 1);
fib[0] = 0;
fib[1] = 1;
for (let i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
// 테스트
console.log(fibTable(10)); // 출력: 55
결론
이 글에서는 동적 계획법의 기초 원리와 피보나치 수열 문제를 해결하는 과정을 살펴보았습니다. 메모이제이션과 테이블 메소드는 각각 장단점이 있으므로 문제의 특성에 따라 적절히 선택하여 사용해야 합니다. 동적 계획법은 다양한 알고리즘 문제 해결에 유용하게 사용되므로, 지속적으로 연습하고 다양한 문제에 적용해보는 것이 중요합니다.
참고문헌
- CLRS, Algorithms
- LeetCode, Dynamic Programming problems
- GeeksforGeeks, Dynamic Programming Concepts