[알고리즘/JAVA] 동적 계획법(DP) : 개념 (파도반 수열 / 1로 만들기 / 계단 오르기)
부분 문제 해결 : Top-Down & Bottom-Up
이전 포스팅에서 재귀와 반복 알고리즘을 살펴보면서, 복잡한 문제를 하위 문제로 나누어 해결하는 방법들에 대해서 살펴 보았었다.
부분 문제 해결 방법에는 크게 두 가지 방식이 있다.
1. Top-Down 방식 : 재귀적인 방식으로 문제를 해결해서 큰 부분의 문제를 작은 부분의 문제로 쪼개가면서 해결하고, 작은 부분 문제들을 결합하여 전체 문제의 해를 구하는 방식이다.
2. Bottom-Up 방식 : 주로 반복적인 방법을 사용하여, 먼저 작은 부분 문제들을 해결하고 이를 이용하여 더 큰 부분 문제들을 해결하는 과정이다.
피보나치 수열의 Top-Down 방식
static int fib(int n){
if(n <= 1){
return n;
}
return fib(n-1) + fib(n-2);
}
피보나치 수열의 Bottom-Up 방식
static int fib(int n){
int prev = 1;
int current = 1;
for(int i = 3; i <= n; i++){
int tmp = prev + current;
prev = current;
current = tmp;
}
return current;
}
하지만 이런 재귀 및 반복 과정에서는 중복되는 연산이 많이 발생하게 될 수 있다.
아래의 fib(4)를 재귀호출 시 발생하는 연산을 살펴보자.
recursiveFib(4)
├─ recursiveFib(3)
│ ├─ recursiveFib(2)
│ │ ├─ recursiveFib(1)
│ │ │ └─ return 1
│ │ └─ recursiveFib(0)
│ │ └─ return 0
│ └─ recursiveFib(1)
│ └─ return 1
└─ recursiveFib(2)
├─ recursiveFib(1)
│ └─ return 1
└─ recursiveFib(0)
└─ return 0
살펴보면 알 수 있듯 이전에 부분 문제의 해를 구하는 연산을 했음에도 불구하고 또다시 연산을 재귀적으로 호출하므로 답을 이미 알고 있는 부분해의 경우에도 연산을 수행하고 있는 것을 알 수 있다.
- fib(3) : 1회 연산
- fib(2) : 2회 연산
- fib(1) : 3회 연산
- fib(0) : 2회 연산
동적 계획법 (Dynamic Programing, DP)
앞의 부분 문제에 대한 중복된 연산을 방지하고자 매모리제이션(Memorization), 타뷸레이션(Tabulation)이라는 개념이 등장하였다.
메모리제이션은 Top-down 방식에서 사용되는 단어이고, 타뷸레이션은 Bottom-up 방식에서 사용되는 단어이다.
어려운 단어 같아 보이지만 둘 다 공통적으로, 앞에서 연산한 것을 기억해두고, 만약 똑같은 연산을 하게 되면 처음부터 풀지 말고 미리 풀어둔 해답을 사용하자는 뜻이다. 그리고 사실 이것이 동적 프로그래밍의 전부이다.
- 메모리제이션 : 재귀 함수 내에서 이전에 계산한 값을 저장하여 동일한 재귀 호출에 대한 중복 계산을 피한다.
- 타뷸레이션 : 작은 문제부터 시작하여 부분 문제를 먼저 해결한 후, 해당 값을 저장해두고, 이를 필요할 때 마다 사용한다.
- 최적 부분 구조 : 해를 구하기 위해서 이전 부분 문제의 해를 계속 이용해야 하는 구조
사실 메모리에지션과 타뷸레이션은 용어를 구분해 두긴 했지만, 부분해들을 저장해 두는 기법들이라고만 묶어서 생각해 두면 될 것 같다.
최적 부분 구조 문제 해결
동적 계획법(DP) : 최적 부분 구조가 가진 중복된 하위 부분해를 사용해서 복잡한 문제를 풀이하는 방법
주로 [Top-Down + 메모리제이션]혹은 [Bottom-Up + 타뷸레이션]을 사용하는 전략을 사용하며 동일한 작은 문제가 여러 번 반복되는 경우가 많은 경우 유용하게 사용된다.
- Top-down 방식 DP: 재귀 호출을 사용하여 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 계산할 때 해당 결과를 저장하고 재활용한다. 이를 통해 중복 계산을 피하고 연산 시간을 절약할 수 있다.
- Bottom-up 방식 DP : 작은 부분 문제부터 시작하여 상위 문제로 올라가면서 저장해둔 부분 문제의 결과를 사용한다.
분할 정복법 vs 동적 계획법
분할 정복법은 문제를 더 작은 부분 문제로 나눈 후 각각을 해결하고, 그 결과를 합쳐서 전체 문제의 해답을 구한다. 즉, 모든 부분 해를 합치게 된다.
동적 계획법은 주어진 문제를 작은 부분 문제로 나눈 후, 각 부분 문제의 해답을 저장하고 필요할 때 이를 활용하여 전체 문제의 해답을 구한다. 일부 해답만 사용하면서도 중복 계산을 피하기 위해 메모리제이션(타뷸레이션)을 사용하는 것이 DP의 아이디어이다.
이름이 다이나믹 프로그래밍라고 하는데 프로그래밍에서 등장하는 이름과 내용이 전혀 연관없는 케이스 중 하나인 것 같다.
Top-Down DP : 피보나치
public class Main {
static int count = 0;
static int countDP = 0;
static Integer[] f;
static int fib(int n){
count++;
if(n <= 1){
return n;
}
return fib(n-1) + fib(n-2);
}
static int fib_dp(int n){
if(n <= 1){
return n;
}
if(f[n] == null){
f[n] = fib_dp(n-1) + fib_dp(n-2);
countDP++;
}
return f[n];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
f = new Integer[n + 1];
System.out.println(fib(n) + " " + count);
System.out.println(fib_dp(n) + " " + countDP);
}
}
fib_dp()는 앞에서 작성했던 피보나치에 메모리제이션을 적용시킨 것이다.
방법을 설명하면 부분해들을 저장시킬 배열을 선언해두고, 만약 처음 푸는 경우라면 해당 배열에 부분해를 저장해 둔다. 예를 들어 fib(4)를 계산하였다면 f[4]에 해당 값을 저장시켜 두고, 나중에 사용할 때 해당 값을 재사용하는 것이다.
위의 코드에서 연산을 몇 번 수행하는지도 파악하기 위해서 함께 작성해놓았는데, DP를 적용한 것과 그렇지 않은 것의 차이는 명확하다.
단순 재귀로 피보나치(30) 연산 횟수 : 2692537
DP로 피보나치(30) 연산 횟수 : 29
Bottom-Up DP : 피보나치
public class Main {
static int count = 0;
static int countDP = 0;
static int fib(int n){
int prev = 1;
int current = 1;
for(int i = 3; i <= n; i++){
count++;
int tmp = prev + current;
prev = current;
current = tmp;
}
return current;
}
static int fib_dp(int n){
int[] f = new int[n + 1];
f[1] = 1;
f[2] = 1;
for(int i = 3; i <= n; i++){
f[i] = f[i-1] + f[i-2];
countDP++;
}
return f[n];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(fib(n) + " " + count);
System.out.println(fib_dp(n) + " " + countDP);
}
}
Bottom-Up 방식에서도 타뷸레이션을 사용하는 예시이다. 피보나치의 경우 반복문 내에서 이전에 구해 둔 부분해를 여러번 사용하는 경우가 적기 때문에 적용의 효과가 미미하지만 Bottom-Up 방식의 DP의 예시로서 작성하였다.
하지만 앞으로 작성하는 DP 문제들을 주로 Bottom-Up 방식으로 풀어 볼 예정이다.
언제 사용해야 할까?
DP를 사용하는 경우는 여러가지 경우가 있지만 아래의 프로세스를 따라갈 수 있다면 사용하기 적절할 확률이 높다.
1. 문제의 입력값과 시간 복잡도를 보고, 백트래킹, 브루트 포스 등 모든 경우의 수에 대한 탐색이 불가능 -> 규칙이 숨어있다는 것을 유추, 부분해로 표현 가능한지와, 그에 따르는 규칙을 찾아내볼 준비를 하자.
2. 큰 문제의 해가 부분 문제의 최적해로 분리할 수 있을 때 -> 큰 문제를 작은 문제로 표현 가능.
3. 큰 문제를 작은 문제로 표현할 수 있는 규칙(점화식)을 찾아내기 -> Top-down, Bottom-up
4. 부분 문제가 중복되어서 사용돠는 경우 -> 메모리제이션, 타뷸레이션
한번 아래의 DP 문제들을 함께 살펴보면서 해당 케이스들을 체화해보자.
문제 : 파도반 수열 (백준 9461)
P(1)부터 P(10)까지의 수열의 규칙을 한번 파악해보자. 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. 뭔가 냄새가 난다. 규칙이 있는 듯한..
살펴보면 P(N)은 부분문제 P(N-2)와 P(N-3)의 합으로 점화식 규칙이 성립되는 것을 알 수 있다.
구현
static long[] p;
static void padoban(int k){
p[1] = 1;
p[2] = 1;
p[3] = 1;
for(int i = 4; i <= k; i++){
p[i] = p[i - 2] + p[i - 3];
}
}
DP(Bottom-Up 방식 + 타뷸레이션)로 파도반 수열을 구현한 코드이다.
1번째, 2번째, 3번째 수열은 1로 고정이다. 그리고 4번째 수열부터 1번째 수열과 2번째 수열의 합, 즉 P(N) = P(N-2) + P(N-3)으로 표현되도록 계산하면 된다.
타뷸레이션의 효과를 한번 살펴보면 만약 i가 4일 때를 살펴보자. p[2] + p[1]의 계산이 이루어 질 것이다. 그리고 i가 5일 때도 살펴보자. p[3] + p[2]의 계산이 이루어진다. 타뷸레이션을 사용함으로서 p[2]를 또 다시 사용할 일이 생기더라도 언제든지 이전에 계산해 두었던 것을 다시 활용해서 사용할 수 있었다.
입출력 코드는 생략하도록 하겠다.
문제 : 1로 만들기 (백준 1463)
문제만 놓고 봤을 때 초심자의 마인드에서 오해하기 쉬울 수 있을 것 같다.
3으로 나누어 떨어지면 3으로 나누고, 그렇지 않으면 2로 나누어 떨어지면 2로 나누고, 이것도 안되면 1을 빼면 된다고 생각할 수 있다.
하지만 10의 경우를 놓고 생각하면 위의 생각으로는 총 4번의 연산을 수행해야 한다. 하지만 실제로 최소 연산의 수는 3번이다.
- 4번의 연산 수행 : 10 / 2 = 5 -> 5 - 1 -> 4 -> 4 / 2 = 2 -> 2 / 2 = 1
- 3번의 연산 수행 : 10 -1 = 9 -> 9 / 3 -> 3 -> 3 / 3 = 1
10이라는 수만 딱 놓고 보았을 때 떠올릴 수 있는 수가 있겠는가? 찾더라도 큰 수의 경우라면? 규칙성을 찾아내야 한다.
모든 경우의 수를 찾는다? 시간 제한이 0.15초인데 반해, 입력값의 범위는 100만이다. n^2 이상의 연산은 꿈도 못꾼다. 따라서 브루트 포스나 백트래킹 등의 완전 탐색을 할 생각은 접자.
10을 연산하는 경우의 수는 3으로 나누는 경우, 2를 나누는 경우, 1을 빼는 경우 세 가지이다. 그리고 해당 세 가지 경우는 부분 문제의 해를 통해서 표현할 수 있음을 알 수 있다.
10을 3으로 나누는 경우 연산수 : 나누어 떨어지지 않으므로 불가능
10을 2으로 나누는 경우 연산수 : calc(5) + 1
10을 1로 뺄셈하는 경우 연산수 : calc(9) + 1
(calc(N)는 N을 1로 만들 때 최소로 필요한 연산 수라고 하자, 앞의 식에서 파악할 수 있듯 calc(5)=3, calc(9)=2 이다)
즉, 정답으로 나와야 하는 calc(10)은 min(calc(5), calc(9)) + 1로 표현할 수 있다. 이를 일반식으로 표현해보자.
calc(N) = min(calc(N/3), calc(N/2), calc(N-1)) + 1 (단 나누어 떨어지는 경우만 경우의 수 포함)
다시 10을 계산하는 과정을 살펴보자
calc(10) = min(calc(5), calc(9)) + 1 = 3
calc(9) = min(calc(3), calc(8)) + 1 = 2
calc(8) = min(calc(4), calc(7)) + 1 = 3
calc(7) = min(calc(6)) + 1 = 3
calc(6) = min(calc(3), calc(2), calc(4)) + 1 = 2
calc(5) = min(calc(4)) + 1 = 3
calc(4) = min(calc(2), calc(3)) + 1 = 2
calc(3) = min(calc(1), calc(2)) + 1 = 1
calc(2) = min(calc(1), calc(1)) + 1 = 1
calc(1) = 0
따라서 큰 문제를 작은 문제에 대한 식으로 표현이 가능하다면, 그리고 부분해가 중복해서 많이 사용되기까지 하였으므로 DP로 풀이할 준비가 되었다는 것이다.
구현
public class Main {
static int[] numbers;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
numbers = new int[n + 1];
numbers[1] = 0;
for(int i = 2; i <= n; i++){
numbers[i] = numbers[i - 1] + 1;
if(i % 3 == 0){
numbers[i] =Math.min(numbers[i], numbers[i / 3] + 1);
}
if(i % 2 == 0){
numbers[i] = Math.min(numbers[i], numbers[i / 2] + 1);
}
}
System.out.println(numbers[n]);
}
}
이번에도 Bottom-up 방식 + 타뷸레이션 사용한 DP로 문제를 풀이하였다.
1. numbers[i]에는 숫자 i에 대한 부분해의 결과를 저장한다.
2. 2부터 N까지의 해를 도출한다. 해당 해를 도출할 때에는 이전에 사용했던 부분해를 이용한다.
3. 도출식에는 numbers[i]를 1로 더하는 경우, (2로 나누어 떨어진다면) numbers[i]를 2로 나누는 경우, (3으로 나누어 떨어진다면) numbers[i]를 3으로 나누는 경우를 부분해를 사용해서 연산 횟수를 계산하고, 계산한 최솟값을 현재 숫자의 해로 설정한다.
4. 최종적으로 numbers[N]이 최종 해가 된다.
문제 : 계단 오르기 (백준 2579)
이번에도 문제의 접근을 DP의 관점에서 해보자.
1. 마지막 도착 계단을 밟았을 때의 최대 점수 = 이전 밟은 계단의 최대 점수 + 현재 계단의 점수
2. 이전 밟은 계단의 최대 점수 = max(1번째 전 계단의 최대 점수, 2번째 전 계단의 최대 점수)
여기서 생각해 보아야 할 것이 문제의 조건중에 단 연속해서 3개의 계단을 밟을 수 없다고 하였다. 그렇다면 위의 예시에서 1번째 전 계단의 점수에는 2번째 전 계단의 점수가 포함될 수 없다는 뜻이다.
따라서 우리는 계단을 밟는 경우를 두 가지 케이스로 분리해 보아야 할 필요가 있다. 따라서 해당 케이스를 아래의 식으로 표현하도록 하겠다.
1. Jump(k) : k번째 계단을 첫 계단으로 밟는 경우의 최대 점수값, k-2번째 계단의 Jump/Step 케이스 중 상관없이 큰 값을 부분해로 포함할 것이다.
2. Step(k) : k번째 계단을 연속해서 두 번째 계단으로 밟는 경우의 최대 점수값. k-1번째 계단의 Jump 케이스를 부분해로 포함할 것이다.
이를 토대로 부분해들에 대해서 점수를 계산해보자.
| 점수 | - | - | 10 | 20 | 15 | 25 | 10 | 20 |
| k | - | - | 1 | 2 | 3 | 4 | 5 | 6 |
| Jump(k) | 0 | 0 | 10 | 20 | 25 | 55 | 45 | 75 |
| Step(k) | 0 | 0 | - | 30 | 35 | 50 | 65 | 65 |
1. 이전 밟은 계단의 최대 점수 = max(Jump(k-1), max(Jump(k-2), Step(k-2)))
- Jump(k) = max(Jump(k-2), Step(k-2))) + Score(k)
- Step(k) = Jump(k-1) + Score(k)
2. 마지막 계단(N)번째 계단의 최대 점수 : max(Jump(N), Step(N)
k=4 를 예시로 들면
- Jump(첫 번째로 밟는 경우의 최대점수)에는 k=2일 때의 최대(Jump/Step)와 현재 점수를 더해서 30+25 = 55가 되었다.
- Step(두 번째로 연속 밟는 경우의 최대점수)에는 k=3일 때의 Step과 현재 점수를 더해서 25+25 = 50이 되었다.
선택된 계단의 값들은 위의 표에서 보라색 볼트체로 표시된 것과 같으며, 1,2,4,6번째 계단을 밟았을 때 최대 점수를 얻을 수 있는 것을 확인하여 해당 점화식이 사용 가능하다는 것을 확인하자.
구현
public class Main {
static int n = 0;
static int[] values;
static int[][] steps; //steps[i][0]은 Step, steps[i][1]은 Jump
static void stepOut(){
//1번째, 2번째 계단은 i-2번째 계단이 존재하지 않으므로 점화식을 이용할 수 없기 때문에 값을 채워준다.
steps[1][0] = values[1]; //1번째 계단 Jump
steps[1][1] = 0; //1번째 계단 Step (Step은 연속으로 오를 계단이 없으므로 존재X -> 0점)
steps[2][0] = values[2]; //2번째 계단 Jump
steps[2][1] = values[2] + steps[1][0]; //2번째 계단 Step
for(int i = 3; i <= n; i++){
//Jump : 2번째 이전 계단의 (Jump/Step) 중 최대점수 + 현재 점수
steps[i][0] = Math.max(steps[i-2][0], steps[i-2][1]) + values[i];
//Step : 1번째 이전 계단의 Jump 점수 + 현재 점수
steps[i][1] = steps[i-1][0] + values[i];
}
int max = Integer.MIN_VALUE;
// N번째 계단(마지막 계단)의 Jump, Step 케이스 중 최대 점수 계산
for(int j = 0; j < 2; j++){
max = Math.max(max, steps[n][j]);
}
System.out.println(max);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
values = new int[n + 2];
steps = new int[n + 2][2];
for(int i = 1; i <= n; i++){
st = new StringTokenizer(br.readLine());
values[i] = Integer.parseInt(st.nextToken());
}
stepOut();
}
}
각 계단에 대한 점수를 저장할 배열(values) : 1번째 인덱스부터, 1번째 계단의 점수를 저장할 배열이다.
DP 부분해 저장(타뷸레이션)을 위한 배열(step): 1번째 인덱스부터 각 계단에서의 Jump, Step 두 가지 케이스에 대한 최대 점수를 저장할 배열이다. steps[i][0]에는 Jump를, steps[i][1]에는 Step을 저장할 것이다.
1번째 계단과 2번째 계단 : 해당 계단들은 i-2번째 계단이 존재하지 않으므로 이를 사용한 점화식을 사용할 수 없다. 따라서 초기값을 설정해준다.
i번째 계단 계산 : 해당 계단들은 점화식을 사용해서 이전에 구해놓은 부분해를 사용하여 해를 도출해낸다. Jump, Step 두 가지 경우의 수에 대해서 나올 수 있는 최대값들을 계산하여 DP 배열에 저장해두고, 이를 다음 계단에서 부분해로 사용한다.
N번째 계단 계산 : 점화식을 통해 최종적으로 나온 N번째 계단에 대해서 Jump된 경우, Step된 경우 중 더 큰 값을 선택하고, 해당 값이 마지막 계단을 올랐을 때의 최대 점수가 된다.
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [알고리즘/JAVA] 동적 계획법(DP) : 문제 (평범한 배낭, 0-1 Knapsack) (0) | 2024.04.30 |
|---|---|
| [알고리즘/JAVA] 누적 합 (Prefix Sum) (0) | 2024.04.20 |
| [알고리즘/JAVA] 백트래킹(Backtracking) : 개념 (N-Queen / 스도쿠) (0) | 2024.04.16 |
| [알고리즘/JAVA] 정렬 알고리즘 : 선택, 삽입, 버블, 병합, 퀵 정렬 (0) | 2024.04.05 |
| [자료구조/JAVA] 해시 테이블 (Hash Table) (0) | 2024.03.31 |
