다이나믹 프로그래밍과 분할정복

다이나믹 프로그래밍

• 입력 크기가 작은 부분 문제들을 해결한 후 해당 부분 문제의 값을 활용하여 보다 큰 크기의 부분 문제를 해결하고 최종적으로는 전체 문제를 해결하는 알고리즘
• 상향식 접근법으로 가장 최하위 답을 구한 후 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
• Memoization 기법을 사용한다.
  • Memoization : 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
• 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용된다.
  • ex) 피보나치 수열

분할 정복

• 문제를 나눌 수 없을 때까지 나누어 각각 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하양식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식
  • 재귀함수로 구현
• 문제를 잘게 쪼갤 때 부분 문제는 서로 중복되지 않는다.
  • ex) 병합정렬, 퀵 정렬

공통점과 차이점

공통점

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

차이점

• 다이나믹 프로그래밍
  • 부분 문제는 중복되어 상위 문제 해결시에 재활용된다.
  • Memoization 기법을 사용한다.
• 분할 정복
  • 부분 문제는 서로 중복되지 않는다.
  • Momoization 기법을 사용하지 않는다.

피보나치 수열

방법 1. 재귀 호출 방법

    public int solution(int n) {
        if (n <= 1) {
            return n;
        }
        return solution(n - 1) + solution(n - 2);

    }

방법 2. 다이나믹 프로그래밍

    public int dynamic(int n) {
        final int[] cache = new int[n + 1];
        cache[0] = 0;
        cache[1] = 1;

        for (int i  = 2; i < n + 1; i++) {
            cache[i] = cache[i - 2] + cache[i - 1];
        }

        return cache[n];
    }