[알고리즘] Dynamic Programming

다이나믹 프로그래밍

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
• 다이나믹 프로그래밍의 구현은 보통 두 가지의 방식(탑다운, 바텀업)으로 구성

DP 조건

1. 최적 부분 구조
   : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음

2. 중복되는 부분 문제
   : 동일한 작은 문제를 반복적으로 해결

피보나치 수열

public class Fibo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fibo(n));
    }
    public static int fibo(int idx) {
        if (idx < 0) {
            return 0;
        } else if (idx < 3) {
            return 1;
        } else {
            return fibo(idx-1) + fibo(idx-2);
        }
    }
}

• 재귀함수로 구현할 경우 '중복되는 부분 문제' 발생
  Ex. fibo(5)를 구할 경우
  fibo(5) = fibo(4) + fibo(3)
  fibo(4) = fibo(3) + fibo(2)
  fibo(3) = fibo(2) + fibo(1)
  fibo(3) = fibo(2) + fibo(1)
  ...
• 중복해서 fibo(3), fibo(2), fibo(1)을 계산하게 됨

Memoization

• 메모이제이션은 DP를 구현하는 방법 중 하나 -> 탑다운 방식(하향식)
• 한 번 계싼한 결과를 메모리 공간에 메모하는 기법
• 값을 기록해 놓는다는 점에서 Caching(캐싱)이라고도 함

피보나치 수열 - DP 활용

public class FiboWithDP {
    public static int[] d = new int[100];
    public static void main(String[] args) {
        System.out.println(f(99));
    }
    public static int f(int x) {
        if (x==1 || x==2) {
            return 1;
        }
        if (d[x] != 0) {
            return d[x];
        } else {
            d[x] = f(x-1) + f(x-2);
            return d[x];
        }
    }
}

문제 1: 개미 전사

• 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량 창고를 몰래 공격하려고 한다.
  메뚜기 마을에는 여러 개의 식량 창고가 있는데 식량 창고는 일직선으로 이루어져 있다
• 각 식량 창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.
  이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.
• 따라서 개미 전사는 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
• 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하시오.
  [입력]
  4
  1 3 1 5
  [출력]
  8

해답

문제 2: 1로 만들기

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

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

• 정수 X가 주어졌을 때 연산 4개를 적절히 사용해서 값을 1로 만들고자 한다.
  연산을 사용하는 횟수의 최솟값을 출력하시오.
• 예를 들어 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
  26 -> 25 -> 5 -> 1
  [입력]
  26
  [출력]
  3

해답

문제 3: 효율적인 화폐 구성

• N가지 종류의 화폐가 있다. 이 화폐들의 갯수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.
  이 때 각 종류의 화폐는 몇 개라도 사용할 수 있다.
• 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 갯수이다.
• M원을 만들기 위한 최소한의 화폐 갯수를 출력하는 프로그램을 작성하시오
• 불가능할 때는 -1을 출력한다.
  [입력]
  2 15
  2
  3
  [출력]
  5

해답

문제 4: 금광

• n m 크기의 금광이 있다. 금광은 1 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다.
• 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다.
  이후에 m-1 번에 걸쳐 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동한다.
• 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하시오.
• 첫 번째 줄에 케이스 수 : T 입력
• 매 테스트 케이스 첫째 줄에 n과 m 입력
• 둘째 줄에 n*m 위치에 매장된 금의 갯수 입력
  [입력]
  2
  3 4
  1 3 3 2 2 1 4 1 0 6 4 7
  4 4
  1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
  [출력]
  19
  16

해답

문제 5: 병사 배치하기

• N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있다.
• 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다.
  다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.
• 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 한다.
  [입력]
  7
  15 11 4 8 5 2 4
  [출력]
  2

해답

출처 : 이것이 취업을 위한 코딩테스트다, 나동빈