다이나믹 프로그래밍(DP), 백트래킹(Backtracking)

다이나믹 프로그래밍(Dynamic Programming) : 큰 문제를 작은 문제로 나누어 푸는 방법으로 계산된 결과를 기록하고 재활용하며 문제의 답을 구할 수 있는 방식. 중간에 계산된 결과를 메모리에 저장하고 재활용 가능

 

분할 정복과의 차이

- 분할 정복은 부분 문제가 중복되지 않고, DP는 부분 문제가 중복되어 재활용을 한다

 

그리디 알고리즘과의 차이

- 그리디는 순간의 최선을 구하는 방식으로 근사치를 구할 수 있지만, DP는 모든 방법을 확인 후에 최적의 해를 구한다.

 

다이나믹 프로그래밍이 되기 위한 조건은 3가지가 있다고 한다.  

1. Simple subproblems 

큰 문제를 작은 문제로 나눌 수 있어야 합니다.  

2. Optimal substructure 

최적의 해를 찾는 구조를 만들 수 있어야 합니다.  

3. Overlapping problems  

작은 문제들이 중복되어야 합니다.  

이렇게 세 가지 조건을 만족해야 다이나믹 프로그래밍이라고 정의할 수 있습니다.

 

대표적 예시) 피보나치 DP

 

DP의 구현 방법으로는 Tabulation, Memorization 방식이 있다.

 

 Tabulation : 반복문을 이용하여 밑에서부터 값을 계산하는 상향식 접근(bottom-up approach) 방식으로 작은 하위 문제부터 풀면서 올라간다. 아래부터 모든 계산을 하면서 답을 찾음

 

Memorization : 위에서부터 계산하는 하향식 접근(top-down approach) 방식으로 쿤 문제에서 하위 문제로 확인해가면 진행한다. 계산이 필요한 순간에만 계산을 진행하며 답을 찾음. 재귀적으로 구현

 

아래 블로그에 다이나믹 프로그래밍에 대해 잘 정리되어 있다.

 

https://fomaios.tistory.com/entry/Algorithm-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EC%9D%B4%EB%9E%80

[Algorithm] 동적 계획법(Dynamic Programming)이란?

 

백 트래킹(Back tracking) : 모든 경의 수를 탐색하며 최적해를 구하는 과정에서 유망하지 않은 쪽은 더 이상 계산하지 않은 방법. 알고리즘 문제에서는 DFS와 섞여서 나오며, 재귀 함수를 잘 구현할 수 있어야 한다. 

 

ex 1) 정수형 n과 m 이 주어졌을 때, 1~n까지의 정수 중에서 중복 없이 m개를 고른 수열을 출력하시오

 

입출력 예시 : 
입력 n = 3 m = 2 

출력 {1,2} {1,3} {2,1} {2,3} {3,1} {3,2}

 

1,2,3 을 뽑는 순열과 같다.

   public static void permutation(int n, int m, int depth) {
        if (depth == m) {
            System.out.println(Arrays.toString(out));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                out[depth] = i + 1;
                permutation(n, m, depth + 1);
                visited[i] = false;
            }
        }
    }

permutation 함수를 재귀적으로 콜하면서 if(!visited[i])로 중복 값을 쳐내면서 값을 출력하고 있다.

 

ex 2) 숫자 5939은 5939, 593, 59 ,5 각각 소수이다.

n이 주어졌을 때 n 자리 수 중에 소수를 찾는 프로그램을 작성하시오

 

입출력 예시 입력 n = 3 . 출력 : 3자리 수의 모든 소수

 

풀이접근법 : 첫번째 자리에 올 수 있는 숫자는 2,3,5,7 이고 숫자를 덧 붙였을 때 올 수 없는 숫자들은 0,2,4,5,6,8 이므로 

모든 수를 계산할 때 해당 숫자가 왔을 때를 제외하고 계산한다.

 

   public static void backTracking(int prime, int len, int n) {
        if (len >= n) {
            result.add(prime);
            return;
        }

        for (int i = 0; i < 10; i++) {
            if (i % 2 != 0 || i != 5) {
                int primeCandidate = prime * 10 + i;
                if (isPrimeNum(primeCandidate)) {
                    backTracking(primeCandidate, len + 1, n);
                }
            }
        }
    }

    public static boolean isPrimeNum(int num) {
        for (int i = 2; i <= num / 2; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

ex 3) sols 배열에 5지 선다 문제의 정답들이 적혀있다. 

3번 연속 해서 같은 정답이 있는 경우가 없다는 것을 알아낸 후, 문제를 찍어서 풀때 5점 이상 받을 경우의 수를 출력

입출력 예시) sols : { 1,2,3,4,5, 1, 2, 3, 4,5}  결과 261622

 

풀이 접근법 : 연속해서 숫자 3개가 올 수 없고, 5점 이상을 받을 있는 경우의 수는 가령 내가 6번째 문제까지 풀었을 때 정답이 0이고, 남은 문제가 4개이므로 5점 이상은 도달 할 수 없으므로 계산을 다 해보지 않고 다음 경우로 넘어 간다.

 

 public static void backTracking(int[] sols, int[] submit, int correctCnt, int idx) {
        if (numOfProblems - idx + correctCnt < 5) {
             return;

        }

        if (idx == numOfProblems) {
            if (correctCnt >= 5) {
                cnt += 1;
            }
        } else {
            int twoInRow = 0;
            if (idx >= 2) {
                if (submit[idx - 1] == submit[idx - 2]) {
                    twoInRow = submit[idx - 1];

                }
            }
            for (int i = 1; i <= 5; i++) {
                if (i == twoInRow) {
                    continue;
                }

                submit[idx] = i;
                if (sols[idx] == i) {
                    backTracking(sols, submit, correctCnt + 1, idx + 1);
                }else{
                    backTracking(sols, submit, correctCnt, idx + 1);
                }
                submit[idx] = 0;
            }

        }
    }