[Algorithm] Dynamic Programming

이번 장에서는 Dynamic Programming을 활용하여 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.

---

계단오르기

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.
그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

• 입력설명
  첫째 줄은 계단의 개수인 자연수 N(3≤N≤35)이 주어집니다.
• 출력설명
  첫 번째 줄에 올라가는 방법의 수를 출력합니다.
• 입력예제 1
  7
• 출력예제 1
  21
• 풀이
  다이나믹 프로그래밍은 크고 복잡한 문제를 소형화시켜서 풀이하는 방법
  문제를 확장시키면서 메모이제이션을 하여 단계별로 증가시키는 방법

public class ClimbStair {

    public int solution1(int stairCount, int[] dynamic) {
        dynamic[1] = 1;
        dynamic[2] = 2;
        for (int i = 3; i <= stairCount; i++) {
            dynamic[i] = dynamic[i - 1] + dynamic[i - 2];
        }
        return dynamic[stairCount];
    }

    @Test
    @DisplayName("계단 오르기")
    public void main() {
        int stairCount = 7;
        int[] dynamic1 = new int[stairCount + 1];
        int expectedAnswer1 = 21;
        int answer1 = solution1(stairCount, dynamic1);
        assertEquals(expectedAnswer1, answer1);
    }

}

---

돌다리 건너기

철수는 학교에 가는데 개울을 만났습니다.
개울은 N개의 돌로 다리를 만들어 놓았습니다.
철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.
철수가 개울을 건너는 방법은 몇 가지일까요?

• 입력설명
  첫째 줄은 돌의 개수인 자연수 N(3≤N≤35)이 주어집니다.
• 출력설명
  첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다.
• 입력예제 1
  7
• 출력예제 1
  34
• 풀이
  돌은 7개, 마지막 육지를 돌로 생각하면 총 8개의 돌

public class StoneBridge {

    public int solution1(int stoneCount, int[] dynamics) {
        dynamics[1] = 1;
        dynamics[2] = 2;
        for (int i = 3; i <= stoneCount + 1; i++) {
            dynamics[i] = dynamics[i - 2] + dynamics[i - 1];
        }
        return dynamics[stoneCount + 1];
    }

    @Test
    @DisplayName("돌다리 건너기")
    public void main() {
        int stoneCount = 7;
        int[] dynamics = new int[stoneCount + 2];
        int expectedAnswer1 = 34;
        int answer1 = solution1(stoneCount, dynamics);
        assertEquals(expectedAnswer1, answer1);
    }

}

---

최대 부분 증가 수열(LIS)

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.
예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면
2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.

• 입력설명
  첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다.
• 출력설명
  첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
• 입력예제 1
  8
  5 3 7 8 6 2 9 4
• 출력예제 1
  4
• 풀이
  dynamics는 inputs에 있는 수까지의 최대 증가를 기록한다.

public class MaxIncreaseNumbers {

    public int solution1(int[] inputs) {
        int[] dynamics = new int[inputs.length];
        int answer = Integer.MIN_VALUE;
        dynamics[0] = 1;
        for (int i = 1; i < inputs.length; i++) {
            int tempMax = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (inputs[j] < inputs[i] && dynamics[j] > tempMax) {
                    tempMax = dynamics[j];
                }
            }
            dynamics[i] = tempMax + 1;
            answer = Math.max(answer, dynamics[i]);
        }
        return answer;
    }

    @Test
    @DisplayName("최대 부분 증가수열")
    public void main() {
        int[] inputs1 = {5, 3, 7, 8, 6, 2, 9, 4};
        int expectedAnswer1 = 4;
        int answer1 = solution1(inputs1);
        assertEquals(expectedAnswer1, answer1);
    }

}

---

가장 높은 탑 쌓기(LIS)

입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다.
둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다.
각 벽돌은 입력되는 순서대로 1부터 연속 적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.

• 출력설명
  첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.
• 입력예제 1
  5
  25 3 4
  4 4 6
  9 2 3
  16 2 5
  1 5 2
• 출력예제 1
  10
• 풀이
  dynamic 배열의 값은 자신이 가장 높은 곳에 있는 경우의 최대 높이이다.

public class TallestTower {

    static class Tower implements Comparable<Tower> {
        int area;   // 넓이
        int height; // 높이
        int weight; // 무게
        public Tower(int area, int height, int weight) {
            this.area = area;
            this.height = height;
            this.weight = weight;
        }
        @Override
        public int compareTo(Tower tower) {
            return tower.area - this.area;
        }
    }

    public int solution1(Tower[] towers) {
        Arrays.sort(towers);
        int[] dynamics = new int[towers.length];
        dynamics[0] = towers[0].height;
        int answer = dynamics[0];
        for (int i = 1; i < towers.length; i++) {
            int tempHeight = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (towers[i].weight < towers[j].weight && dynamics[j] > tempHeight) {
                    tempHeight = dynamics[j];
                }
            }
            dynamics[i] = tempHeight + towers[i].height;
            answer = Math.max(answer, dynamics[i]);
        }
        return answer;
    }

    @Test
    @DisplayName("가장 높은 탑 쌓기")
    public void main() {
        Tower[] towers = {
                new Tower(25, 3, 4),
                new Tower(4, 4, 6),
                new Tower(9, 2, 3),
                new Tower(16, 2, 5),
                new Tower(1, 5, 2)
        };
        int expectedAnswer1 = 10;
        int answer1 = solution1(towers);
        assertEquals(expectedAnswer1, answer1);
    }

}

---

동전교환(냅색 알고리즘)

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가?
각 단위의 동전은 무한정 쓸 수 있다.

• 입력설명
  첫 번째 줄에는 동전의 종류개수 N(1<=N<=50)이 주어진다.
  두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
  각 동전의 종류는 100원을 넘지 않는다.
• 출력설명
  첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.
• 입력예제 1
  3
  1 2 5
  15
• 출력예제 1
  3
• 해설
  dynamics 배열을 금액의 크기 사이즈로 만든다.
  값은 i금액을 만드는데 드는 최소 동전의 갯수로 한다.
  총 동전의 갯수만큼의 반복문을 돌린다.
  최초 1원이 채워놓은 배열을 다음 2원이 돌면서 더 적은 수량으로 만들 수 있다면
  dynamics 배열의 값을 업데이트 한다.

public class ExchangeCoin {

    public int solution1(int[] coins, int targetCost) {
        Arrays.sort(coins);
        int[] dynamics = new int[targetCost + 1];
        Arrays.fill(dynamics, Integer.MAX_VALUE);
        dynamics[0] = 0;
        for (int coin : coins) {
            for (int j = coin; j <= targetCost; j++) {
                dynamics[j] = Math.min(dynamics[j], dynamics[j - coin] + 1);
            }
        }
        return dynamics[targetCost];
    }

    @Test
    @DisplayName("동전교환")
    public void main() {
        int[] coins1 = {1, 2, 5};
        int targetCost1 = 15;
        int answer1 = solution1(coins1, targetCost1);
        assertEquals(3, answer1);
    }

}

---

최대점수 구하기(냅색 알고리즘)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.
각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.
제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.
해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.

• 입력설명
  첫 번째 줄에 문제의 개수N(1<=N<=50)과 제한 시간 M(10<=M<=300)이 주어집니다.
  두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
• 출력설명
  첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.
• 입력예제 1
  5 20
  10 5
  25 12
  15 8
  6 3
  7 4
• 출력예제 1
  41
• 풀이
  dynamics 테이블을 만들고 사이즈는 제한시간 + 1로 한다.
  각 값에는 해당 시간까지 풀 수 있는 최대 점수이다.
  문제당 한번밖에 풀 수 없다는 점을 주의해야한다.
  뒤에서부터 순회해야 문제를 중복으로 푸는 문제를 해결할 수 있다.
  무한개면 앞에서 부터 순회하고 유한개라면 뒤에서 부터 순회해야한다.

public class MaxScore {

    public int solution1(int problemCount, int timeLimit, int[][] problems) {
        int[] dynamics = new int[timeLimit + 1];
        for (int i = 0; i < problemCount; i++) {
            for (int j = timeLimit; j >= problems[i][1]; j--) {
                dynamics[j] = Math.max(dynamics[j], dynamics[j - problems[i][1]] + problems[i][0]);
            }
        }
        return dynamics[timeLimit];
    }

    @Test
    @DisplayName("최대점수 구하기(냅색 알고리즘)")
    public void main() {
        int problemCount1 = 5;
        int timeLimit1 = 20;
        int[][] problems1 = {
                {10, 5}, {25, 12}, {15, 8},
                {6, 3}, {7, 4}
        };
        int expectedAnswer1 = 41;
        int answer1 = solution1(problemCount1, timeLimit1, problems1);
        assertEquals(expectedAnswer1, answer1);
    }

}

---

참고한 강의: https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84