[2025 1학기 알고리즘 스터디] 남윤찬 #2주차

이번 2주차는 DP(Dynamic Programing)입니다. 일단 문제 블로깅에 앞서 DP가 뭔가 간단하게 요약해봤습니다.

 

DP로 푸는 조건 및 방식

dp(dynamic programming)은 복잡한 문제를 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 여러 블로그를 찾아보았는데 공통적으로 있는 말로는, dp라는 명칭을 고안한 Richard Bellman이 멋있어서 이렇게 지었다고 한다ㅋㅋ.

아무튼 dp는 재귀적으로 문제를 푸는 방식인데, 여기에 메모이제이션(Memoization)을 하는 방식이다. 점화식을 세워 재귀로 탐색을 하다보면 중복되는 값이 있을텐데, 이것을 피하며 문제를 풀어나가는 것이 dp이다.

 

DP로 푸는 조건 및 방식

dp가 적용되려면 두 가지 조건이 필요하다.

    겹치는 소문제 - 큰 문제를 작은 문제로 나눌 수 있는 경우

    최적 부분 구조 - 작은 문제에서 구한 값이 큰 문제에도 포함되는 경우

        → 내 시선엔 점화식을 성립시킬 수 있는 문제인가 정도로 보인다.

그리고 dp로 풀어나가는 방법에도 두 가지가 있다

    Top-Down: 주로 재귀로 풀어나가며 재귀 함수의 호출이 초기 조건(보통 0)까지 닿은 결과가 재귀 함수에 맞물리며 재활용 된다.

    Bottom-Up: 메모이제이션을 적극 활용하여 초기값(dp[0])부터 차례대로 값을 채워나간다.

dp의 가장 핵심은 내가 보고있는 문제가 dp로 푸는 문제인지 아는 것이고, 그 뒤는 점화식과 메모이제이션, 초기값을 잘 정하고 구현하며 테스트케이스를 적용시켜나가야 한다.

---

 

1로 만들기

import java.util.Scanner;

public class Main {

    static Integer[] nums;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        
        System.out.println(make1(n, 0));
    }
    static int make1(int n, int count) {
        if (n < 2) {
            return count;
        }

        return Math.min(make1(n/2, count+1+(n%2)), make1(n/3, count+1+(n%3)));
    }

}

 ㄴ> Not DP

import java.util.Scanner;

public class Main {

    static Integer[] nums;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        // 0~n까지 1로 만들려면 필요한 횟수를 메모이제이션 할 배열의 크기
        nums = new Integer[n+1];
        // 0과 1은 더 할 필요 없으므로 0
        nums[0] = nums[1] = 0;

        System.out.println(make1(n));
    }
    static int make1(int n) {
        if (nums[n] == null) {
            if (n % 6 == 0) { // 2, 3 모두 나눌 수 있을 때
                nums[n] = Math.min(make1(n-1), Math.min(make1(n/3), make1(n/2))) + 1; // 세 가지 경우 중 최소일 때보다 n이 카운트+1
            } else if (n % 3 == 0) { // 3으로 나눌 수 있을 때
                nums[n] = Math.min(make1(n/3), make1(n-1)) + 1; // 두 경우 중 최소일 때보다 n이 카운트+1
            } else if (n % 2 == 0) { // 2로 나눌 수 있을 때
                nums[n] = Math.min(make1(n/2), make1(n-1)) + 1; // 두 경우 중 최소일 때보다 n이 카운트+1
            } else { // 1을 빼야 할 때
                nums[n] = make1(n-1) + 1; // 1뺀 값보다 n이 카운트+1
            }
        }
        return nums[n];
    }

}

 ㄴ> DP

DP문제이다. DP라는 문제를 어떻게 접근해야할지 너무 어려웠는데, 실버 dp 문제도 이렇게 헤매면 나는 어쩌나;; 일단 dp에 대한 감이 너무 안잡혀서 방법을 찾아본 결과, 크게 두 가지(dp와 일반 재귀) 풀이를 알 수 있었다.

먼저 dp를 하지 않는 재귀 방법으로는 메서드가 호출될 때마다 연산 횟수를 갱신하면서 나아간다. n이 1이 되기 전까지 count를 누적하다가 1이 되면 count를 반환하여 재귀를 탈출한다. 재귀로 하면 n과 count의 값이 아래와 같이 바뀌어 간다.

하지만 dp는 모든 경우의 수를 타고 들어간다. 2로 나누어 떨어질 때, 3으로 나누어 떨어질 때, 둘 다 가능할 때, 또는 둘 다 안될 때를 모두 비교해 각 상황에서 발생하는 경우의 수를 모두 탐색하며 기록하고 결과를 도출해낸다. dp가 흘러갈 때 메모이제이션 되는 배열을 살펴보면 아래처럼 진행된다.

제출 결과를 보면 dp는 일반 재귀 방식에 비해 메모리도 많이 차지하고 시간도 오래 걸려 효율적이지는 못하다. 하지만 오래걸리더라도 항상 최적해를 구할 수 있는 게 dp이다.

 

계단 오르기

import java.util.Scanner;

public class Main {

    static Integer[] nums;
    static int[] stairs;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        
        nums = new Integer[n+1];
        stairs = new int[n+1];

        for (int i = 1; i <= n; i++) {
            stairs[i] = scanner.nextInt();
            // System.out.print(stairs[i] + " ");
        }
        // System.out.println();
        nums[0] = stairs[0]; // 시작 부분
        nums[1] = stairs[1]; // 첫 번째 계단
        if (n >= 2) {
            nums[2] = stairs[1] + stairs[2];
        }

        System.out.println(steping(n));
    }
    
    static int steping(int num) {
        if (nums[num] == null) { // 점화식: (두 칸 갔을 때의 합, 한 칸 갔을 때 + 세 칸 갔을 때의 합) 중 큰 것
            nums[num] = Math.max(steping(num-2), steping(num-3) + stairs[num-1]) + stairs[num];
        }
        // for (Integer i : nums) {
        //     System.out.print(i + " ");
        // }
        // System.out.println();

        return nums[num];
    }

}

점화식 세우기에서 애를 많이 먹었다. 감이 잘 안잡혀서 다른 글을 참고했다.. dp는 감잡기가 어렵다는 게 이런 말인듯하다.

일단 점화식 자체는 위처럼 세우면 된다. 세 번 연속해서 밟을 수 없다는 것은, 한 칸을 가고 나면 반드시 두 칸을 가야한다는 것으로 볼 수 있다. 그렇다면 비교할 것은 두 칸을 갔을 때, 그리고 한 칸을 가고 두 칸을 갔을 때인 것이다. 또한 마지막 계단을 반드시 밟아야하기 때문에 마지막인지 판단하기보다, 마지막에서 시작해서 내려가면서 null이 아닐 때를 찾는 방식을 사용했다.(큰 부분에서 점점 내려갔으니 이것이 Top-Down이겠지요?)

메모이제이션 배열의 변화를 살펴보면 아래와 같다.

 

가장 긴 증가하는 부분 수열

import java.util.Scanner;

public class Main {

    static Integer[] memo;
    static int[] nums;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        memo = new Integer[n];
        nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 모든 수에 대해 작은 수가 있는지 탐색
        for (int i = 0; i < n; i++) {
            seq(i);
        }

        int max = memo[0];
        for (int i : memo) {
            max = Math.max(max, i);
        }

        System.out.println(max);
    }
    static int seq(int num) {
        if (memo[num] == null) {
            memo[num] = 1;

            for (int i = num-1; i >= 0; i--) { // num부터 0까지 탐색
                if (nums[i] < nums[num]) { // num보다 작은 수가 있으면 그 자리에 memo
                    memo[num] = Math.max(memo[num], seq(i) + 1);
                }
            }
        }

        return memo[num];
    }

}

 ㄴ> Top-Down

import java.util.Scanner;

public class Main {

    static Integer[] memo;
    static int[] nums;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        memo = new Integer[n];
        nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 모든 수를 탐색
        for (int i = 0; i < n; i++) {
            memo[i] = 1;

            // 0부터 i까지 탐색
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && memo[i] < memo[j]+1) {
                    memo[i] = memo[j] + 1;
                }
            }
        }
        
        int max = memo[0];
        for (int i : memo) {
            max = Math.max(max, i);
        }

        System.out.println(max);
    }

}

ㄴ> Bottom-Up

dp는 결국 직접 푼 게 없어버렸지만.. 얼마나 어려울지는 알 수 있었던 거 같습니다…

일단 이 문제는 모든 수를 찾아다니며 자기보다 작은 수가 앞에 몇 개 있는지 메모이제이션 하며 푸는 문제였습니다. 그래서 O(n^2)이 걸리게 되더군요. (이진탐색하는 방법도 있다고 하지만 일단 dp니까..)

바텀업을 할 때 0부터 i까지 탐색하는 부분이 탑다운에서 재귀로 표현되는 부분입니다. 0~i까지 찾냐(Bottom-Up), i에서 재귀로 타고 내려가 0까지 도달하냐(Top-Down) 차이인 것입니다.

탑다운을 할 때 memo 배열은 다음과같이 변합니다.

---

dp는 꾸준히 감을 잡는 방법을 찾아나가야할 거 같습니다..