[Algorithm] 동적 프로그래밍(Dynamic Programming) 기초 유형 모음

필자는 모든 문제를 Top-Down 방식으로 풀이했다.

계단 오르기

계단 오르기(S3)

 

동적계획법(DP)를 연습하는 데에 좋은 문제라고 생각이 되어 가져와봤다. 내용 자체는 어렵지 않지만, 조건을 제대로 만족하는 식을 작성해내지 못한다면 매우 어렵게 느껴질 수 있다.

 

규칙은 다음과 같다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

여기서 특히 2번 조건을 잘 고려하여 재귀호출 식을 작성해야 한다.

전체코드를 보기 보다는 핵심이 되는 재귀호출을 할 함수를 보자

코드

static int game(int curr) {
    // 기저 사례
    if (curr <= 1) return stairs[curr];
    if (curr == 2) return stairs[1] + stairs[2];

    // 메모이제이션 체크
    if (cache[curr] != -1) return cache[curr];

    // 실제 로직 부분
    int case1 = game(curr - 2);
    int case2 = stairs[curr - 1] + game(curr - 3);

    return cache[curr] = stairs[curr] + Math.max(case1, case2);
}

• game(int curr): curr번째 계단을 올라 얻을 수 있는 점수의 최댓값
• 기저 사례
  • 첫 번째 계단의 경우, 해당 계단의 점수를 그대로 반환한다.
  • 두 번째 계단의 경우, 첫번째 계단과 두 번째 계단을 모두 밟는 경우가 최대이므로 이를 더한 값을 반환한다.
• 실제 로직
  • 잘 생각해보면, curr번째 계단에 오르는 방법은 2가지뿐이다.
    1. curr-2번째 계단에서 한 번에 두 계단을 오르는 방법
    2. curr-3번째 계단에서 curr-1 번째 계단으로 한 번에 두 계단을 오르고, curr-1 번째 계단에서 한 칸을 오르는 방법
  • curr-1번째 계단에서 한 칸을 오를 때에는 재귀 호출을 하지 않는다는 점에 유의하자. 재귀 호출을 해버리면 문제의 조건 중 2번 조건을 만족하지 못하게 되어버린다.
  • 이렇게 구한 2가지 값 중 최댓값에 현재 계단의 점수를 더한 값이 현재 계단에서 얻을 수 있는 점수의 최댓값이다.

비슷한 유형 - 포도주 시식

[포도주 시식(S1)(https://www.acmicpc.net/problem/2156)

 

이 문제에서의 조건은 다음과 같다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

'계단 오르기 문제'와 굉장히 유사한 것을 확인할 수 있다. 단, 다른 점이라면 마지막 잔을 반드시 마셔야 한다는 조건이 없다는 것이다.

 

계단 오르기 문제에서는 마지막 계단을 반드시 밟아야 한다는 조건이 있기 때문에, 현재 계단에서의 최댓값을 구할 때 현재 계단을 반드시 밟는다고 가정하고 2가지 방법으로만 계산했다.

 

하지만, 포도주 시식 문제에서는 n번째 포도주까지 '보았을 때' 최대로 시식하는 방법은 n번째 포도주를 먹을 수도 있고 먹지 않을 수도 있다.

n번째 포도주를 먹는다면, 계단 오르기 문제와 똑같은 방법으로 포도주 양의 최댓값을 구할 수 있다.
n번째 포도주를 먹지 않는다면, 이전 포도주까지 보았을 때의 최댓값을 취해야 한다.

 

이를 코드로 옮기면 다음과 같다.

// curr번째 잔을 포함하여 마실 수 있는 최대 포도주의 양을 반환
static int drink(int curr) {
    // 기저 사례
    if (curr <= 1) return podoju[curr];
    if (curr == 2) return podoju[1] + podoju[2];

    if (cache[curr] != -1) return cache[curr];

    // 현재 curr번째 잔을 마실지, 마시지 않을지를 결정
    int drinkCurr = podoju[curr] + Math.max(drink(curr - 2), podoju[curr - 1] + drink(curr - 3));
    int noDrinkCurr = drink(curr - 1);

    return cache[curr] = Math.max(drinkCurr, noDrinkCurr);
}

---

연속 합

연속합(S2)

코드

public class BOJ1912 {

    static int[] arr, cache;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        cache = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            cache[i] = Integer.MIN_VALUE;
        }

        int ret = Integer.MIN_VALUE;

        for (int i = 0; i < N; i++) {
            ret = Math.max(ret, solve(i));
        }

        System.out.println(ret);
    }

    // i번째 원소를 포함한 최대 연속 부분합을 반환
    private static int solve(int idx) {
        if (idx == 0) return arr[idx];
        if (cache[idx] != Integer.MIN_VALUE) return cache[idx];

        return cache[idx] = Math.max(arr[idx], arr[idx] + solve(idx - 1));
    }
}

• solve(int idx): idx번째 원소를 포함한 최대 연속 부분합을 반환하는 함수
• 각 idx에 대해 solve를 호출해줌으로써 모든 경우의 최대 연속 부분합을 cache 배열에 메모이제이션 해둔다.

---

LIS(Longest Increasing Subsequence)

가장 긴 증가하는 부분 수열(S2)

DP의 대표적인 유형으로, 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 유형이다.

코드

public class BOJ11053 {

    static int N;
    static int[] arr, cache;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        cache = new int[N];
        Arrays.fill(cache, -1);

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int ret = 0;
        for (int i = 0; i < N; i++) {
            ret = Math.max(ret, lis(i));
        }

        System.out.println(ret);
    }

    static int lis(int start) {
        if (cache[start] != -1) return cache[start];

        int ret = 1;
        for (int next = start + 1; next < N; next++) {
            if (arr[start] < arr[next])
                ret = Math.max(ret, 1 + lis(next));
        }

        return cache[start + 1] = ret;
    }
}

• lis(int start): start에서 시작하는 부분 증가 수열 중 최대의 길이
• 실제 로직
  • start 이후의 next 인덱스를 반복하며, arr[start] < arr[next]인 경우를 찾는다
    • 즉, 현재 원소(arr[start])보다 큰 값만 LIS에 포함 가능
  • 그중 lis(next) + 1의 최댓값을 갱신

최적화

최적화라고 하기에는 조금 애매한 부분이 있지만, main 함수에서 반복문을 돌리며 lis를 호출하고 최댓값을 갱신하는 부분을 약간의 코드 변경으로 제거할 수 있다.

 

-1번째 인덱스를 가상으로 만들어주는 것이다. 코드로 보자.

public class BOJ11053 {

    static int N;
    static int[] arr, cache;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        cache = new int[N + 1];
        Arrays.fill(cache, -1);

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(lis(-1) - 1);
    }

    static int lis(int start) {
        if (cache[start + 1] != -1) return cache[start + 1];

        int ret = 1;
        for (int next = start + 1; next < N; next++) {
            if (start == -1 || arr[start] < arr[next])
                ret = Math.max(ret, 1 + lis(next));
        }

        return cache[start + 1] = ret;
    }
}

• -1을 전달할 경우, 모든 시작 위치를 자동으로 시도할 것이다.
  • 기존 코드의 main 함수에 있떤 반복문을 lis에서 사용하도록 옮긴 것
• -1을 처리할 수 있도록 다음의 내용들을 변경해줒어야 한다.
  • start로 -1이 전달될 수 있으므로 cache[]에 접근 시 cache[start] 대신 cache[start + 1]을 사용
  • cache[] 사이즈 1 증가
  • lis 내부 반복문에서 start == 1 조건도 추가
  • lis(-1) 호출 후, 그 결과에 1을 뺀 값이 정답(-1은 우리가 가상으로 추가한 입력이기 때문)

---

LCS(Longest Common Subsequence)

LCS(G5)

 

LCS란 최장 공통 부분 수열이라는 의미로, 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
ex) ACAYKP와 CAPCAK의 LCS는 ACAK

 

기본적으로 LCS는 투 포인터를 사용하여 두 수열의 각 요소를 하나씩 확인하며 구하는 것이 일반적이다. 각 포인터를 index1, index2라고 하고 로직을 살펴보자.

1. 각 포인터로 바라보고 있는 요소가 서로 같다면, LCS는 해당 문자를 포함하고(길이 1 증가) 두 포인터 모두 다음으로 이동하여 계속 탐색한다.
2. 같지 않다면, 다음 2가지 선택지 중 더 긴 LCS 값을 선택한다
   • A[index1]를 무시하고 B[index2]와 비교 (index1 + 1, index2)
   • B[index2]를 무시하고 A[index1]와 비교 (index1, index2 + 1)
3. index1 또는 index2가 수열의 끝에 도달했다면, 더 이상 LCS를 찾을 수 없으므로 0을 반환하여 종료한다.

코드

public class BOJ9251 {
    static String A, B;
    static int[][] cache;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        A = br.readLine();
        B = br.readLine();

        cache = new int[A.length()][B.length()];
        for (int i = 0; i < A.length(); i++) {
            for (int j = 0; j < B.length(); j++) {
                cache[i][j] = -1;
            }
        }

        System.out.println(lcs(0, 0));
    }

    static int lcs(int index1, int index2) {
           // 기저 사례
        if (index1 == A.length() || index2 == B.length()) return 0;
        // 메모이제이션
        if (cache[index1][index2] != -1) return cache[index1][index2];

        // 현재 문자가 일치하는 경우
        if (A.charAt(index1) == B.charAt(index2)) return cache[index1][index2] = 1 + lcs(index1 + 1, index2 + 1);
        // 현재 문자가 일치하지 않는 경우
        return cache[index1][index2] = Math.max(lcs(index1, index2 + 1), lcs(index1 + 1, index2));
    }
}

• lcs(int index1, int index2): A의 index1과 B의 index2에서의 LCS 길이

---

배낭 문제(Knapsack Problem)

평범한 배낭(G5)

 

배낭 문제 역시 DP로 유명한 문제이다. 배낭에 넣을 수 있는 최댓값이 주어지고, 해당 한도를 넘지 않도록 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 문제이다.

즉, 조합 최적화 문제이다!

 

배낭 문제는 짐을 쪼갤 수 있느냐, 없느냐로 분류된다. 짐을 쪼갤 수 있는 문제를 'Fraction Knapscak Problem'이라 하고, 짐을 쪼갤 수 없는 문제를 '0/1 Knapsack Problem'이라 한다.

두 문제에서 적용되는 알고리즘 역시 서로 다른데, 전자의 경우 그리디 알고리즘이 사용되고, 후자의 경우 DP를 사용한다.

 

이번 문제는 짐을 쪼갤 수 없는 문제이므로 DP로 해결할 수 있다.

코드

public class BOJ12865 {

    static int N, K;
    static Item[] items;
    static int[][] cache;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        items = new Item[N];
        cache = new int[N][K + 1];
        for (int i = 0; i < N; i++) {
            Arrays.fill(cache[i], -1);
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            items[i] = new Item(weight, value);
        }

        System.out.println(knapsack(N - 1, K));
    }

    // 0부터 curr번째까지의 아이템을 고려하면서, 수용 가능 무게가 k일 때 얻을 수 있는 최대 가치를 반환
    static int knapsack(int curr, int k) {
        if (curr < 0) return 0;
        if (cache[curr][k] != -1) return cache[curr][k];

        int ret = knapsack(curr - 1, k); // 현재 물건을 담을 수 없는 경우(이전 값 탐색)
        if (items[curr].weight <= k) // 현재 물건을 담을 수 있는 경우
            ret = Math.max(ret, knapsack(curr - 1, k - items[curr].weight) + items[curr].value);

        return cache[curr][k] = ret;
    }

    static class Item {
        int weight;
        int value;

        public Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }
}

• knapsack(int curr, int k): 0부터 curr번째까지의 아이템을 고려하면서, 수용 가능 무게가 k일 때 얻을 수 있는 최대 가치를 반환
• 기저 사례
  • curr == -1인 경우, 즉 더 이상 고려할 아이템이 없을 때, 최대 가치는 0
• 실제 로직
  • 현재 아이템을 선택하지 않는 경우 -> 단순히 이전 아이템까지 고려한 최적의 값을 그대로 가져옴 -> knapsack(curr - 1, k)
  • 현재 아이템을 담을 수 있는 경우 -> 현재 아이템의 무게가 남은 용량 k보다 작거나 같은 경우
    • => 현재 아이템을 선택할 수도, 선택하지 않을 수도 있음
    • 이 경우, 두 가지 선택 중 더 큰 값 선택