오랜만에 알고리즘 공부를 다시 시작하고 있다.
그런데... 다 잊었다! 다시 복습해보자!
1. 동적 계획법(Dynamic Programming, DP)란?
큰 문제를 작은 문제로 나누어 푸는 방식이다.
문제를 풀기 위해 작은 문제의 결과를 저장해두고, 같은 문제를 다시 풀 필요가 없도록 한다.
동적 계획법은 보통 재귀적 문제 해결에서 사용되는데, 단순히 재귀만 사용하는 것보다 훨씬 효율적이다.
재귀는 큰 문제를 풀기위해 동일한 작은 문제를 반복해서 호출하는 방식인데,
DP는 이미 계산한 값은 저장해두고 재사용하므로, 동일한 계산을 반복하지 않는다.
2. 왜 동적 계획법을 사용할까?
일반적인 재귀방식은 같은 계산을 여러 번 반복하여 비효율적이다.
예를 들어, 피보나치 수열을 재귀로 계산할 때, fibonacci(5)를 계산하기 위해 fibonacci(3) 과 fibonacci(4)가 필요하고,
fibonacci(3)을 구하기 위해 다시 fibonacci(1)과 fibonacci(2) 를 계산해야한다.
이렇게 되면 같은 값을 여러 번 반복해서 계산하는 것과 다름이 없어진다.
동적 계획법은 중복 계산을 피함으로써 시간 복잡도를 줄여주고, 효율적인 문제 해결이 가능하도록 한다.
이는 특히 큰 수를 다루는 문제나 복잡한 계산이 반복되는 문제에서 유용하다.
3. DP의 두 가지 주요 방식
동적 계획법에는 탑다운(Top-Down) 방식과 바텀업(Bottom-Up) 방식, 두 가지 접근 방법이 있다.
1. 탑다운(Top-Down) 방식
- 탑다운 방식은 보통 메모제이션(Memoization)과 함께 사용된다.
- 큰 문제를 작은 문제로 나누어 해결하고, 각 작은 문제의 결과를 저장해두는 방식이다.
- 예를 들어, 재귀적으로 함수를 호출하면서 계산된 결과를 배열이나 객체에 저장해 중복 계산을 방지한다.
2. 바텀업(Bottom-Up)방식
- 바텀업 방식은 보통 반복문을 사용하여 작은 문제부터 차례대로 풀어나간다.
- 작은 문제를 먼저 해결한 후, 그 결과를 차례차례 이용해서 큰 문제를 해결하는 방식이다.
- 보통 배열이나 테이블을 이용해 작은 문제부터 결과를 저장하고, 최종적으로 큰 문제를 해결한다.
4. 그래서, 이거 언제 필요할까?
동적 계획법이 필요한 알고리즘 문제는 보통 최적 부분 구조와 중복되는 부분 문제라는 특징을 가진다.
- 최적 부분 구조
- 문제를 작은 문제로 나누어 풀 수 있을 때, 작은 문제들의 결과로 큰 문제를 풀 수 있는 구조
- 중복되는 부분문제
- 동일한 작은 문제를 여러 번 계산하게 될 때 중복되는 계산을 피하고 효율을 높이기 위해 사용
5. 예시는? - 피보나치 수열
사실 내가 풀다가 온갖 시간초과에,, 런타임 에러를 만난게 바로 이 피보나치 수열 문제였다.
단순히 재귀로만 풀다가 문제한테 뺨맞고 gpt 의 손을 빌렸다.
피보나치 수열은 매우 간단하지만, DP를 설명하기 정말 좋은 예시다.
피보나치 수열에서 n 번째 수는 이전 두 수의 합으로 정의된다.
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
위 함수는 중복된 계산이 많아서 비효율적이다.
만약 fibonacci(5)를 계산해야한다면, fibonacci(3)을 두 번이나 계산해야하는 셈이다.
function fibonacci(n, memo={}) {
if (n <=1 ) return n;
if (memo[n]) return memo[n];
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
return memo[n];
}
여기서는 중복 계산이 발생하지 않는다.
너무 좋다.
위는 탑-다운 방식으로 메모제이션을 사용해서 풀었다.
function fibonacci(n) {
if (n <= 1) return n;
let dp = [0, 1]; // 초기값 설정: dp[0] = 0, dp[1] = 1
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 이전 두 값을 더해서 저장
}
return dp[n]; // 최종적으로 n번째 피보나치 수 반환
}
이렇게 풀면 바텀업 방식으로, for 문을 돌면서 작은 것들을 계속 더해가는 방식이다.
만약 자신이 아는 것을 테스트해보고 싶은 개발자라면,
아래 프로그래머스 문제를 풀어보는 것도 정말 추천한다!
https://school.programmers.co.kr/learn/courses/30/lessons/12945/solution_groups?language=javascript