12주차
Dynamic Programming, 즉 DP는 큰 문제를 작은 문제로 나누고, 작은 문제의 결과를 저장해두었다가 다시 사용하는 알고리즘 방식입니다.
쉽게 말하면, 이미 계산한 값을 또 계산하지 않도록 저장해두는 방식입니다.
예를 들어 어떤 문제를 풀 때 같은 계산이 여러 번 반복된다면, 매번 새로 계산하는 것보다 한 번 계산한 결과를 저장해두고 다시 사용하는 것이 훨씬 효율적입니다.
DP를 사용할 수 있는 문제는 보통 두 가지 특징을 가집니다.
첫 번째는 큰 문제의 답을 작은 문제의 답으로 만들 수 있다는 점입니다.
두 번째는 같은 작은 문제가 여러 번 반복해서 등장한다는 점입니다.
그래서 DP는 “이전 결과를 저장하고, 그 결과를 이용해서 현재 문제를 해결하는 방법”이라고 설명할 수 있습니다.
DP 문제는 보통 현재 값을 이전 값들로 계산할 수 있을 때 등장합니다.
예를 들어 다음과 같은 질문이 나오면 DP를 의심해볼 수 있습니다.
“n번째 값을 구하려면 n - 1번째 값과 n - 2번째 값이 필요한가?”
“현재 위치까지 오는 방법의 수를 이전 위치들의 방법 수로 구할 수 있는가?”
“현재까지의 최댓값이나 최솟값을 이전 상태에서 이어받아 계산할 수 있는가?”
DP는 특히 경우의 수, 최댓값, 최솟값을 구하는 문제에서 자주 사용됩니다.
대표적인 DP 문제 패턴은 다음과 같습니다.
1차원 DP는 이전 값들을 이용해 현재 값을 구하는 형태입니다. 예를 들어 계단 오르기, 멀리 뛰기, 피보나치 수 문제가 여기에 해당합니다.
2차원 DP는 두 가지 기준을 함께 고려해야 하는 형태입니다. 예를 들어 등굣길, 최장 공통 부분 수열, 배낭 문제가 있습니다.
경우의 수 DP는 가능한 방법의 수를 누적하는 방식입니다.
최댓값/최솟값 DP는 여러 선택지 중 가장 좋은 값을 저장하면서 진행하는 방식입니다.
메모이제이션은 한 번 계산한 결과를 저장해두고, 같은 계산이 다시 필요할 때 저장된 값을 바로 사용하는 방법입니다.
예를 들어 dp[5]를 구하는 과정에서 dp[3]이 여러 번 필요할 수 있습니다.
이때 dp[3]을 매번 다시 계산하면 비효율적입니다.
그래서 처음 dp[3]을 구했을 때 배열이나 Map에 저장해두고, 다음에 dp[3]이 필요하면 저장된 값을 바로 사용합니다.
즉, 메모이제이션은 “계산 결과를 기억해두는 것”이라고 이해하면 됩니다.
탑다운은 말 그대로 위에서 아래로 내려가는 방식입니다.
먼저 구하고 싶은 큰 문제부터 시작합니다.
예를 들어 n칸까지 가는 방법의 수를 구하고 싶다면, 먼저 dp(n)을 호출합니다.
그런데 dp(n)을 구하려면 dp(n - 1)과 dp(n - 2)가 필요합니다.
그래서 재귀적으로 dp(n - 1), dp(n - 2)를 계속 호출하면서 작은 문제로 내려갑니다.
이 과정에서 이미 계산한 값은 메모이제이션을 통해 저장해두고 다시 사용합니다.
탑다운 방식은 점화식을 그대로 코드로 옮기기 쉬워서 이해하기 좋습니다.
다만 재귀를 사용하기 때문에 입력이 크면 스택 오버플로우가 발생할 수 있습니다.
바텀업은 아래에서 위로 올라가는 방식입니다.
가장 작은 문제의 답을 먼저 구하고, 그 값을 이용해서 더 큰 문제의 답을 차례대로 구합니다.
예시 문제는 프로그래머스의 “멀리 뛰기”입니다.
이 문제에서는 한 번에 1칸 또는 2칸을 뛸 수 있습니다.
목표는 n칸 끝에 도달하는 방법의 수를 구하는 것입니다.
예를 들어 n이 4라면 다음과 같은 방법들이 있습니다.
1칸, 1칸, 1칸, 1칸
1칸, 1칸, 2칸
1칸, 2칸, 1칸
2칸, 1칸, 1칸
2칸, 2칸
따라서 n이 4일 때 정답은 5입니다.
이 문제를 DP로 생각해보면, n번째 칸에 도착하는 방법은 두 가지로 나눌 수 있습니다.
첫 번째는 n - 1번째 칸에서 1칸을 뛰어서 오는 경우입니다.
두 번째는 n - 2번째 칸에서 2칸을 뛰어서 오는 경우입니다.
즉, n번째 칸에 도착하는 방법의 수는 다음과 같이 표현할 수 있습니다.
dp[n] = dp[n - 1] + dp[n - 2]
여기서 dp[i]는 i번째 칸까지 도달하는 방법의 수를 의미합니다.
초기값은 다음과 같습니다.
dp[1] = 1
1칸에 도달하는 방법은 1칸 한 번 뛰는 방법뿐입니다.
dp[2] = 2
2칸에 도달하는 방법은 1칸 + 1칸, 또는 2칸 한 번 뛰는 방법입니다.
이후부터는 이전 두 값을 더해가며 dp 배열을 채우면 됩니다.
문제에서 결과를 1234567로 나눈 나머지를 반환하라고 했기 때문에, 값을 계산할 때마다 나머지 연산을 적용합니다.
class Solution {
public long solution(int n) {
if (n == 1) {
return 1;
}
long[] dp = new long[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
}
return dp[n];
}
}def solution(n):
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567
return dp[n]function solution(n) {
if (n === 1) {
return 1;
}
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
}
return dp[n];
}DP 문제를 풀 때 가장 먼저 해야 할 일은 dp 배열의 의미를 정확히 정하는 것입니다.
예를 들어 이 문제에서는 dp[i]를 “i번째 칸까지 도달하는 방법의 수”라고 정의했습니다.
이 정의가 명확하지 않으면 점화식을 세우기 어렵습니다.
두 번째는 초기값을 정확히 설정해야 합니다.
이 문제에서는 dp[1] = 1, dp[2] = 2가 기본값입니다.
초기값이 잘못되면 이후 값이 모두 잘못 계산됩니다.
세 번째는 점화식을 잘 세워야 합니다.
n번째 칸에 오려면 n - 1번째 칸에서 1칸 뛰거나, n - 2번째 칸에서 2칸 뛰어야 합니다.
그래서 점화식은 dp[i] = dp[i - 1] + dp[i - 2]가 됩니다.
네 번째는 배열 범위에 주의해야 합니다.
dp[2]를 사용하려면 n이 1인 경우를 따로 처리해야 합니다.
다섯 번째는 나머지 연산을 빠뜨리지 않는 것입니다.
문제에서 1234567로 나눈 나머지를 반환하라고 했기 때문에, 계산 과정에서 계속 나머지 연산을 적용해야 합니다.
마지막으로 DP 문제를 풀 때는 다음 순서로 접근하면 좋습니다.
- dp 배열의 의미를 정합니다.
- 초기값을 정합니다.
- 점화식을 세웁니다.
- 반복문의 시작 위치를 정합니다.
- 문제 조건에 맞게 최종 값을 반환합니다.