[알고리즘] DP

DP

피보나치 수열로 재귀, DP 모두 비교해보기!

1. 재귀함수

• 자기 자신을 호출하는 함수로 반복적으로 호출을 함으로써 원하는 결과를 도출
• 피보나치는 O(2^N) 시간복잡도 걸림

public static int fibonacci_recur(int n) { //O(2^N)
        if (n <= 1) return n;
        else return fibonacci_recur(n - 1) + fibonacci_recur(n - 2);
    }

2. DP

1) DP의 핵심

1. 최적 부분 구조
   • '큰 문제의 최적해'가 '작은 문제의 최적해'를 포함하는 성질
2. 중복 부분 문제
   • '동일한 작은 문제를 반복적으로 해결'해야 하는 성질

💡 이 순서대로 해보자!
1. DP 방식을 적용할 수 있는지 확인하기: 최적 부분 구조, 중복 부분 문제인지 따져보기
2. 점화식 세우기 : 일반화 할 수 있는 수식 생각하기

 

2) DP의 종류

💡  메모이제이션(Memoization)이란?
‘중복 계산'을 피하기 위한 기법
⇒ 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때
저장된 결과를 이용하여 중복 계산을 피함으로써 성능을 향상 시킬 수 있음!

2) - 1 .Top-Down (탑다운 방식)

• 큰 문제를 해결하기 위해 작은 문제를 호출 하는 방식
• 재귀적으로 호출하여 문제를 해결하는 방식
• 장점
  • 작은 문제들의 겨로가값을 저장함으로써 동일한 계산을 반복하지않음 → 시간 복잡도 감소
• 단점
  • 스택 오버플로우 발생할 수 있음

public static long[] memo = new long[n + 1];

public static long fibonacci_dp_top(int n) { 
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        return memo[n] = fibonacci_dp_top(n - 1) + fibonacci_dp_top(n - 2);
    }

 

 

2) - 2.Bottom-Up (바텀업 방식)

• 작은 문제부터 차례대로 해결해 나가는 방식
• 장점
  • 부분 문제의 해를 저장하고 이를 활용하여 다음 문제를 해결함 → 시간 복잡도 감소
• 단점
  • 초기값을 설정줘야함
  • 작은 문제들의 결과값을 임시적으로 저장해 둘 공간이 필요

public static long fibonacci_dp_bottom(int n) {
        if (n <= 1) return n;
        memo[0] = 0;
        memo[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            memo[i] = memo[i - 1] + memo[i - 2];
        }
        return memo[n];
    }