동적 계획법과 분할 정복

동적 계획법과 분할 정복

동적계획법 (DP 라고 부름)
입력 크기가 작은 부분 문제들을 해결 한 후, 해당 부분 문제의 해를 활용해서 큰 크기의 부분 문제를 해결하므로써 전체 문제를 해결하는 알고리즘

 

• 동적 계획법
  • 상향식 접근법 : 가장 최하위 해답을 구한 후 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
  • Memoization 기법 사용
    • 이전에 계산한 값을 저장해 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
  • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됨
    • 피보나치 수열
• 분할 정복
  • 문제를 나눌수 없을 때까지 나누어서 각각 풀고 병합하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법 : 일반적으로 재귀함수로 구현
  • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
    • 병합 정렬, 퀵 정렬

 

공통점과 차이점

공통점

• 문제를 잘게 쪼개서 가장 작은 단위로 분할

차이점

• 동적 계획법
  • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
  • Memoization 기법 사용
• 분할 정복
  • 부분 문제는 서로 중복되지 않음
  • Memoization 기법 사용 안함

 

동적 계획법 알고리즘 이해

피보나치 수열 : n 을 입력 받아 아래와 같이 계산됨

출처 피보나치수열 Fibonacci Sequence과 함금비율 1.618 (tistory.com)

함수를 fibonacci 라고 하면,
fibonacci(0):0
fibonacci(1):1
fibonacci(2):1
fibonacci(3):2
fibonacci(4):3
fibonacci(5):5
fibonacci(6):8
fibonacci(7):13
fibonacci(8):21
fibonacci(9):34

 

출처 https://shoark7.github.io

 

 

recursive call 활용

public class Factorial {
    public int factorialFunc(int data) {
        if(data <= 1) {
            return data;
        }
        
        return factorialFunc(data - 1) + factorialFunc(data - 2);
    }
}


Factorial fObject = new Factorial();
fObject.factorialFunc(10);    // 55

 

동적 계획법 활용

public class Dynamic {
    public int dynamicFunc(int data) {
        Integer[] dp = new Integer[data + 1];
        dp[0] = 0;
        dp[1] = 1;
        
        for(int i = 2; i < data + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[data];
    }
}


Dynamic dp = new Dynamic();
dp.dynamicFunc(10);    // 55

 

 

 

 

 

 

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스