[이것이 코딩 테스트다 with Java] 다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍

 

개요

큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 문제를 해결하는 방향에 따라 두 가지로 나뉘는데 큰 문제를 해결하기 위해 작은 문제를 호출하는 탑다운(하향식, Top-Down)방식과 작은 문제부터 차근차근 답을 도출하는 보텀업(상향식, Bottom-Up)이다. 항상 다이나믹 프로그래밍을 사용할 수는 없으며 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 잇다. 
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 위와 같은 조건을 만족하는 대표적인 문제이다. 피보나치 수열은 일반적으로 탑다운 방식으로 구현하면 재귀함수를 보텀업 방식으로 구현할 경우 반복문을 사용한다. 이때 메모이제이션(Memoization) 기법을 사용하지 않고 재귀함수 방식으로 피보나치 수열을 구현할 경우 아래와 같은 코드가 작성된다.

public static int fibo(int x) {
    if (x == 1 || x == 2) {
        return 1;
    }
    return fibo(x - 1) + fibo(x - 2);
}

위와 같이 코드를 작성할 경우 O(2ⁿ)의 시간이 소요된다. 예를 들어 N = 30이면 약 10억 가량의 연산을 수행하여 한다. 또한  f(6)일 때 호출 과정은 아래 그림과 같다. 

그림을 보면 동일한 파라미터를 가진 함수가 반복적으로 호출되는 것을 알 수 있다. 이 문제를 메모이제이션(Memoization) 기법으로 해결해볼 수 있다.

 

메모이제이션 기법

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 같은 문제를 호출하면 메모했던 결과를 그대로 가져온다. 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

 

피보나치 수열 (탑다운, 메모이제이션 기법 적용)

import java.util.*;

public class Main
{
    
	// 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열
	public static long[] cacheFibo;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int num = scan.nextInt();
		cacheFibo = new long[num + 1];
		
		System.out.println("result = " + fibonacci(num));
	}
	
	public static long fibonacci(int num){
		if(num <= 2)  return 1;
		
		if(cacheFibo[num] == 0){
			cacheFibo[num] = fibonacci(num -1) + fibonacci(num-2);
		}
		
		return cacheFibo[num];
	}
}

 

피보나치 수열 (탑다운, 메모이제이션 기법 적용)

import java.util.*;

public class Main
{
    
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int num = scan.nextInt();
		long[] fibo = new long[num + 1];
		fibo[1] = 1;
		fibo[2] = 1;
		
		for(int i = 3; i < fibo.length; i++){
			fibo[i] = fibo[i-1] + fibo[i-2];
		}
		
		System.out.println("result = " + fibo[num]);
	}

}

 

예제 1 - 1로 만들기

난이도 ●◐○ | 풀이 시간 20분 | 시간 제한 1초 | 메모리 제한 128MB

정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

1. X가 5로 나누어떨어지면, 5로 나눈다.
2. X가 3으로 나누어떨어지면, 3으로 나눈다.
3. X가 2로 나누어떨어지면, 2로 나눈다.
4. X에서 1을 뺀다.

정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들어야한다. 연산을 사용하는 횟수의 최솟값을 출력해라.
X = 26일 경우 아래와 같이 계산해서 3번의 연산이 최솟값이다.

1. 26 - 1 = 25
2. 25 /5 = 5
3. 5 / 5 = 1

 

입력 조건

• 첫째 줄에 정수 X이 주어진다. (1<=X<=30,000)

 

출력 조건

• 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

입력/출력 예시

입력 예시	출력 예시
26	3

 

요점

• 4가지 방법 중 연산 횟수가 가장 적게 들어가는 횟수 + 1 이라는 점화식을 세운다.
• 이 점화식을 토대로 보텀업 다이나믹 프로그래밍 소스코드를 작성한다.

 

소스 코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int x = scan.nextInt();
		int[] count = new int[x+1];
		int[] divisors = {2, 3, 5};
		
		count[1] = 0;
		count[2] = 1;
		
		for(int i = 3; i <= x; i++){
			count[i] = count[i-1] + 1;
			
			for(int divisor : divisors){
				if(i % divisor == 0) count[i] = Math.min(count[i], count[i/divisor] + 1);
			}
		}
		
		System.out.println("result = " + count[x]);
	}
}

 

예제 2 - 개미 전사

난이도 ●●○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB

개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.

1

3

1

5

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다.
개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오

 

입력 조건

• 첫째 줄에 식량창고의 개수 N이 주어진다. (3<=N<=100)
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0<=K<=1,000)

 

출력 조건

• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

 

입력/출력 예시

입력 예시	출력 예시
4  1 3 1 5	8

 

요점

• 왼쪽부터 차례대로 식량 창고를 턴다고 가정한다.
• (현재위치 - 1)과 (현재위치 -2 + 현재 값) 중 어느 값이 더 큰지 비교한다.
• 보텀업 방식으로 작성한다.

 

소스 코드

import java.util.*;

public class Main
{
    
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		
		int count[] = new int[n+1];
		int[] food = new int[n];
		for (int i = 0; i < n; i++) {
			food[i] = scan.nextInt();
		}
		
		count[0] = food[0];
		count[1] = Math.max(food[0], food[1]);
		
		for(int i = 2; i <n; i++){
			// i-1과 i-2 중 큰 값을 결정
			count[i] = Math.max(count[i-1], count[i-2] + food[i]);
		}
		
		System.out.println("result = " + count[n-1]);
	}

}

 

예제 3 - 바닥 공사

난이도 ●◐○ | 풀이 시간 20분 | 시간 제한 1초 | 메모리 제한 128MB

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 x 2의 덮개, 2 x 1의 덮개, 2 x 2의 덮개를 이용해 채우고자 한다.

이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2 x 3 크기의 바닥을 채우는 경우의 수는 5가지이다.

 

입력 조건

• 첫째 줄에 N이 주어진다.(1 <= N <= 1,000)

 

출력 조건

• 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

 

입력/출력 예시

입력 예시	출력 예시
3	5

 

요점

• 796,796의 나머지를 출력하는 것은 결과 값이 커질 것을 대비하는 것이기 때문에 신경쓰지 않아도 된다.
• 왼쪽부터 가로 1을 채우는 방법은 하나이고 가로 2를 채우는 방법은 3가지 이다.

 

소스 코드

import java.util.*;

public class Main
{
    
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int count[] = new int[n+1];
		
		count[1] = 1;
		count[2] = 3;
		for (int i = 3; i <= n; i++) {
			count[i] = (count[i - 1] + 2 * count[i - 2]) % 796796;
		}
		
		System.out.println(count[n]);
	}

}

 

예제 4 - 효율적인 화폐 구성

난이도 ●●○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

 

입력 조건

• 첫째 줄에 N,M이 주어진다(1<= N <= 100, 1<= M <= 10,000)
• 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.

 

출력 조건

• 첫째 줄에 경우의 수 X를 출력한다.(불가능할 때는 -1을 출력한다)

 

입력/출력 예시

입력 예시	출력 예시
2 15 2 3	5

 

요점

• M 이전 숫자부터 효율적인 화폐 구성 단위를 구해간다.
• 보텀업 방식으로 작성한다.

 

소스 코드

import java.util.*;

public class Main
{
    
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int m = scan.nextInt();
		
		int[] count = new int[m + 1];
		
		int[] coins = new int[n];
		for (int i = 0; i < n; i++) {
			coins[i] = scan.nextInt();
		}
		
		Arrays.fill(count, 1, count.length, 10001);
		
		for(int coin : coins){
			for(int j = coin; j <= m; j++){
				if(count[j-coin] != 10001){
					count[j] = Math.min(count[j], count[j-coin] + 1);
				}
			}    
		}
		
		if (count[m] == 10001) {
			System.out.println("Impossible");
		} else {
			System.out.println("result = " + count[m]);
		}
	}

}

 

 

다이나믹 프로그래밍 예제를 풀어본 후

잠깐이나마...코딩 테스트 공부를 접을 뻔 했다..다이나믹 코딩의 개념은 이해할 수 있지만 어떤 문제에 적용할 수 있고 어떤 방식으로 적용해야하는지 전혀 감이 안 잡힌다. 예제 문제 풀 때 결국 다 문제 해설을 읽어봤지만 그래도 통 감이 안 잡힌다. 결국 코드도 다 봤는데 난 다이나믹 프로그래밍에 재능이 없는건지 그냥 다이나믹 프로그래밍이 어려운 건지 제발 후자였으면 좋겠다ㅜㅜ 이것도 비슷한 문제를 계속 풀다보면 패턴이 보여서 풀 수 있을 때까지 연습하는 수밖에 없는지 답답한 마음이다.

 

GitHub: https://github.com/Leeyeonjae/coding-test/tree/main/8_DynamicProgramming

참고서적 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈