다이나믹 프로그래밍(Dynamic Programming)
- 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
- 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(
Top Down,Bottom Up)으로 구성된다.
다이나믹 프로그래밍의 조건
-
최적 부분 구조 (Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. -
중복되는 부분 문제 (Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결해야 한다.
Memoization
다이나믹 프로그래밍을 구현하는 방법 중 하나
한번 계산한 결과를 메모리 공간에 메모하는 기법
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
- 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.
Top down(하향식) 🆚 Bottom up(상향식)
다이나믹 프로그래밍의 전형적인 형태는 Bottom Up 방식이다.
결과 저장용 배열은 DP 테이블 이라고 부른다.
엄밀히 말하면 Memoization은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념
따라서 Memoization은 다이나믹 프로그래밍에 국한된 개념은 아니다.
한번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용되지 않을 수도 있다.
📄 비효율적인 피보나치 수열
import java.util.*;
public class Main {
// 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
public static int fibo(int x) {
if (x == 1 || x == 2) {
return 1;
}
return fibo(x - 1) + fibo(x - 2);
}
public static void main(String[] args) {
System.out.println(fibo(4));
}
}📄 피보나치 수열(Top-down)
import java.util.*;
public class Main {
// 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
public static long[] d = new long[100];
// 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
public static long fibo(int x) {
// 종료 조건(1 혹은 2일 때 1을 반환)
if (x == 1 || x == 2) {
return 1;
}
// 이미 계산한 적 있는 문제라면 그대로 반환
if (d[x] != 0) {
return d[x];
}
// 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
public static void main(String[] args) {
System.out.println(fibo(50));
}
}📄 피보나치 수열(Bottom-up)
import java.util.*;
public class Main {
public static long[] d = new long[100];
public static void main(String[] args) {
// 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1;
d[2] = 1;
int n = 50; // 50번째 피보나치 수를 계산
// 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for (int i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
System.out.println(d[n]);
}
}
이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리한다.
실제 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문한다.
다이나믹 프로그래밍 🆚 분할 정복
-
다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있습니다.
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
-
다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복입니다.
- 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됩니다.
- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않습니다.
다이나믹 프로그래밍 문제에 접근하는 방법
주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있다.
다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해 보자.
일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 Top Down 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다.
일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.
📕 <문제> 개미 전사
- 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 합니다. 메뚜기 마을에 는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있습니다.
- 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량 을 빼앗을 예정입니다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창 고가 공격받으면 바로 알아챌 수 있습니다.
- 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식 량창고를 약탈해야 합니다.
개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구해라.
🧐 문제 해결 아이디어
N = 4일 때, 다음과 같은 경우들이 존재할 수 있다.
식량을 선택할 수 있는 경우의 수는 다음과 같이 8가지
7번째의 경우에서 8만큼의 식량을 얻을 수 있으므로 최적의 해는 8
✨ 답안 코드
import java.util.*;
public class Main {
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
public static int[] d = new int[100];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 정수 N을 입력받기
int n = sc.nextInt();
// 모든 식량 정보 입력받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = arr[0];
d[1] = Math.max(arr[0], arr[1]);
for (int i = 2; i < n; i++) {
d[i] = Math.max(d[i - 1], d[i - 2] + arr[i]);
}
// 계산된 결과 출력
System.out.println(d[n - 1]);
}
}📕 <문제> 1로 만들기
정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지입니다.
- X가 5로 나누어 떨어지면, 5로 나눕니다.
- X가 3으로 나누어 떨어지면, 3으로 나눕니다.
- X가 2로 나누어 떨어지면, 2로 나눕니다.
- X에서 1을 뺍니다.
정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 합니다. 연산을 사용하는 횟수의 최 솟값을 출력하세요. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값입니다.
26 → 25 → 5 → 1
🧐 문제 해결 아이디어
✨ 답안 코드
import java.util.*;
public class Main {
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
public static int[] d = new int[30001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for (int i = 2; i <= x; i++) {
// 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1;
// 현재의 수가 2로 나누어 떨어지는 경우
if (i % 2 == 0)
d[i] = Math.min(d[i], d[i / 2] + 1);
// 현재의 수가 3으로 나누어 떨어지는 경우
if (i % 3 == 0)
d[i] = Math.min(d[i], d[i / 3] + 1);
// 현재의 수가 5로 나누어 떨어지는 경우
if (i % 5 == 0)
d[i] = Math.min(d[i], d[i / 5] + 1);
}
System.out.println(d[x]);
}
}📕 <문제> 효율적인 화폐 구성
N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서
그 가치의 합이 M원이 되도록 하려고 합니다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다.
예를 들어 2원, 3원 단위의 화폐가 있을 때는
15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한 의 화폐 개수입니다.
M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요.
🧐 문제 해결 아이디어
✨ 답안 코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 정수 N, M을 입력받기
int n = sc.nextInt();
int m = sc.nextInt();
// N개의 화폐 단위 정보를 입력 받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
int[] d = new int[m + 1];
Arrays.fill(d, 10001);
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = arr[i]; j <= m; j++) {
// (i - k)원을 만드는 방법이 존재하는 경우
if (d[j - arr[i]] != 10001) {
d[j] = Math.min(d[j], d[j - arr[i]] + 1);
}
}
}
// 계산된 결과 출력
if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
System.out.println(-1);
}
else {
System.out.println(d[m]);
}
}
}📕 <문제> 금광
n X m 크기의 금광이 있습니다.
금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다.
채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다.결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.
🧐 문제 해결 아이디어
금광의 모든 위치에 대하여 다음의 세 가지만 고려하면 됩니다.
1. 왼쪽 위에서 오는 경우
2. 왼쪽 아래에서 오는 경우
3. 왼쪽에서 오는 경우
세 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제를 해결합니다.
array[i][j] = 행j열에 존재하는 금의 양
dp[i][j] = 열까지의 최적의 해 (얻을 수 있는 금의 최댓값)
점화식은 다음과 같다.
dp[i][j] = array[i][j] +
max(dp[i - 1][j - 1], dp[i][j - 1], dp[i + 1][j - 1])
이때 테이블에 접근할 때마다 리스트의 범위를 벗어나지 않는지 체크해야 한다.
편의상 초기 데이터를 담는 변수 array를 사용하지 않아도 된다.
• 바로 DP 테이블에 초기 데이터를 담아서 다이나믹 프로그래밍을 적용할 수 있다.
✨ 답안 코드
import java.util.*;
public class Main {
static int testCase, n, m;
static int[][] arr = new int[20][20];
static int[][] dp = new int[20][20];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 테스트 케이스(Test Case) 입력
testCase = sc.nextInt();
for (int tc = 0; tc < testCase; tc++) {
// 금광 정보 입력
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = sc.nextInt();
}
}
// 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = arr[i][j];
}
}
// 다이나믹 프로그래밍 진행
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
int leftUp, leftDown, left;
// 왼쪽 위에서 오는 경우
if (i == 0) leftUp = 0;
else leftUp = dp[i - 1][j - 1];
// 왼쪽 아래에서 오는 경우
if (i == n - 1) leftDown = 0;
else leftDown = dp[i + 1][j - 1];
// 왼쪽에서 오는 경우
left = dp[i][j - 1];
dp[i][j] = dp[i][j] + Math.max(leftUp, Math.max(leftDown, left));
}
}
int result = 0;
for (int i = 0; i < n; i++) {
result = Math.max(result, dp[i][m - 1]);
}
System.out.println(result);
}
}
}reference
