다이나믹 프로그래밍

들어가면서..

다이나믹 프로그래밍 알고리즘을 배우면서 개념과 패턴, 어떻게 응용될 수 있는지
기록해본다.

개념

복잡한 문제를 여러 하위 개념 즉, 작은 단위로 나누어서 해결하는 알고리즘이다.

패턴

피보나치 수열

7개의 계단을 한번에 최대 두칸씩 이동할 수 있을 때 몇개의 경우의 수가 존재하는가

예를 들어 첫번째 계단은 한 번
두번째 계단은 1+1, 2 두번
세번째 계단은 1+1, 2, 1+2 세번
네번째 계단은 1+1,1+2+1,1+1+2,2+1+1,2+2 다섯번
...
일곱번째 계단은 21번의 경우의 수가 존재

위 문제의 규칙성을 보았을 때 피보나치 수열을 적용할 수 있다.

예를 들어, 세번째 계단의 경우의 수는 이전에 구해진 첫번째 계단의 경우의 수 + 두번째 계단의 경우의 수와 같다.

그리고, 메모이제이션을 사용할 수 있다.

fibo[i] = fibo[i-2]+fibo[i-1];

최대 부분 증가 수열

최대 부분 증가 수열은 주어진 수열에서 증가하는 부분 수열 중 가장 긴 수열을 의미한다.

문장으로 들으면 대체 이게 뭔소리일까..?라는 생각이 든다.

이해가 쉽게 예를 들어보겠다.

예를 들어, 주어진 수열이 [4, 1, 5, 2, 3]라고 가정해보겠다.

위의 예시에서는 [1,2,3]이 가장 긴 최대 부분 증가 수열이 된다.

그 이유는 아래와 같다.

수열의 첫번째 값은 4인데 그 이후에 오는 요소들에서 더 작은 값이 존재한다.

가장 작은 값이 맨 앞으로 와야 최대 부분 수열이 만들어지므로

1이 맨 앞에 위치하게 된다. 그 이후로 작은 값인 2 그 이후로 작은 값인 3이 최대 부분 수열에 추가되어

[1,2,3]이 된다.

또 다른 예시를 들어보겠다.

예를 들어, 주어진 수열이 [2, 7, 5, 8, 6, 4, 7, 12, 3] 일 때

[2, 5, 6, 7, 12]인 길이가 5인 최대 부분 증가수열을 만들 수 있다.

가장 작은 값이면서 선택되었을 때 가장 긴 최대 부분 수열을 갖게 해주는 2가 맨 앞에 오는 요소가 된다.

그 이후에 7이 나오는데 만약 7이 선택되게 되면 그 이후에 8과 12 밖에 선택하지 못하므로

최대 부분 수열이 될 수 없다.

그 이후에 오는 5를 선택하면 6,7,12를 선택할 수 있게 된다.

그러면 이런 의문이 들 수 있다. 5보다 작은 4를 선택하면 안될까?

4를 선택해보자. 4 이후에 오는 값이 12 밖에 없으므로

2, 4, 12 밖에 선택하지 못하므로 5를 선택하는게 최대 부분 수열이 된다.

따라서 2, 5가 선택되고 그 다음 값인 6과 7,12가 선택되어

2,5,6,7,12라는 최대 부분 수열이 생성된다.

어떻게 응용될 수 있는가?

피보나치 수열일 때

import java.util.Scanner;

public class 돌다리건너기 {
    static int[] dy;

    public int solution(int n){
	
        dy[1] = 1;
        dy[2] = 2;

        for(int i = 3; i <= n+1; i++){
            dy[i] = dy[i-2] + dy[i-1];
        }
		
        // 땅에 착지하는 경우까지 세야하므로 n+1의 경우의 수를 return
        return dy[n+1];
    }
    public static void main(String[] args) {
        돌다리건너기 T = new 돌다리건너기();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        dy = new int[n+2];

        System.out.println(T.solution(n));
    }
}

최대 부분 증가 수열일 때

import java.util.Scanner;

public class 최대부분증가수열 {
    static int[] dy;

    public int solution(int[] arr) {
        int answer = 0;
        dy = new int[arr.length];
        // 첫번째 최대 부분 수열을 반드시 1이므로
        dy[0] = 1;

        for (int i = 1; i < arr.length; i++) {
            int max = 0;
            for (int j = i - 1; j >= 0; j--) {
                // 최대 부분 수열을 구하는 과정
                // max는 나의 인덱스 이전에 최대로 나올 수 있는 경우의 수를 가지고 있게 됨.
                if (arr[j] < arr[i] && dy[j] > max) max = dy[j];
            }

            // i번째에서 가지는 최대 부분 수열 값
            // + 1하는 이유는 dy[i] 번째를 포함하고 있지 않기 떄문임
            dy[i] = max + 1;
            answer = Math.max(answer, dy[i]);
        }

        return answer;
    }

    public static void main(String[] args) {
        최대부분증가수열 T = new 최대부분증가수열();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        System.out.println(T.solution(arr));
    }
}