이번 시간에는 백준 온라인 저지 2839번 문제를 **DP(동적 계획법)**으로 접근하여 살펴보도록 하겠습니다. 🙂
오늘 문제를 풀면서 사용할 동적 계획법에 대해서 먼저 알아보도록 하겠습니다.
**동적 계획법(Dynamic Programming)**은 틀이 정해진 알고리즘 코드가 아닌, 알고리즘 문제 해결 방법론 중 하나라고 생각하면 됩니다.
동적 계획법은 하나의 문제를 여러 개의 작은 문제로 쪼개어 해결하는 방법입니다.
작은 문제들을 먼저 해결하여 기억해두고, 앞서 기억해둔 작은 문제들의 해답을 통해 큰 문제를 해결해나가는 방식이라고 생각하면 됩니다.
동적 계획법은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀호출 알고리즘으로 구현 했을 때 지나친 중복이 발생하는 경우에 재귀함수를 대신하여 사용할 수 있습니다.
동적 계획법을 적용할 수 있는 가장 대표적인 예로 피보나치 수열이 있습니다.
피보나치 수열 1부터 시작하여, 바로 앞에 있는 두 항의 값을 더한 값이 바로 다음 항의 값이 되는 수열을 말합니다. 이를 일반화한 점화식은 아래와 같습니다.
f(1) = f(2) = 1 f(n) = f(n-1) + f(n-2)
→ 1, 1, 2, 3, 5, 8, 13, …
우선, 이렇게 점화식으로 일반화할 수 있는 문제는 재귀 함수를 사용하면 쉽게 코드로 구현할 수 있습니다.
따라서, 피보나치 수열 또한 아래 코드처럼 재귀 함수를 사용하여 간단하게 구현할 수 있는 문제입니다.
// 피보나치 수열의 n번째 항의 값을 반환하는 함수
int fib(int n) {
if (n == 1 || n == 2) { // 첫 번째 항과 두 번째 항의 값은 1
return 1;
}
return fib(n-1) + fib(n-2); // fib(n) = fib(n-1) + fib(n-2)
}
하지만, 재귀 함수를 사용하게 되면, 매개변수 n 값이 커지면 커질수록 연산 시간이 굉장히 오래 걸리게 됩니다.
함수 안에서 계속해서 함수를 또 다시 호출하기 때문에, 재귀 함수를 사용하면 n 값이 커지면 커질수록 굉장히 많은 메모리를 차지하게 되는 것입니다.
그렇다면 이러한 재귀 함수의 문제점을 동적 계획법으로 해결할 수 있다고 했으니, 이를 동적 계획법으로 구현해 봅시다.