230527 Today I Learned

오늘 TIL에는 동적계획법에 대해 정리해보고자 한다.

피보나치수열

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

• 일반적으로 피보나치 수열은 위처럼 재귀로 값을 구한다.
  하지만 이렇게 되면 중복연산이 많아져 매우 비효율적이다.
  시간복잡도로 O(2^n)

• 이미 했던 연산을 반복하는 걸 막기 위해 처음 진행되는 연산은 기록하고, 이미 진행된 연산은 기록되어있는 값을 가져오는 동적계획법이 고안되었다.

동적계획법

최적화 이론의 한 기술. 특정 범위까지의 값을 구하기 위해 다른 범위까지의 값을 이용해 효율적으로 값을 구하는 알고리즘 기법
최적부분구조를 지닌 중복된 하위 문제들을 분할 정복으로 풀어야 하는 문제 해결 패러다임.

• 어떤 문제를 풀기위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식

• 간단하게 답을 재활용하는 것. 구체적 알고리즘보단 문제해결 패러다임에 가깝다.

Top-down / Memoization

위에서 부터 내려와서 큰 문제부터 작은 문제로 분할하며 푸는 방식
동일한 문제를 반복해야할 경우 미리 값을 저장해두고 활용한다.

public class A_DP_피보나치 {

  static long[] memo;
  
  static long fiboTopDown(int n) {
//    저장된 값이 있으면 반환
    if (memo[n] != 0) return memo[n];
//    0과 1은 미리 값 세팅
    if (n<=1) {
      memo[n] = n;
//      수열을 계산해서 메모이제이션
    } else {
      memo[n] = fiboTopDown(n-1) + fiboTopDown(n-2);
    }
    return memo[n];
  }

  public static void main(String[] args) {
    int n = 10;
//    배열 초기화
    memo = new long[n+1];
    System.out.println(fiboTopDown(n)); // 55
  }

Bottom-up / Tabulation

작은 문제부터 해결해 나가면서 아래에서부터 순차적으로 올라가는 방식.

public class A_DP_피보나치 {

  static long fiboBottomUp(int n) {
    long[] dp = new long[n+1];

    dp[0] = 0;
    dp[1] = 1;

//    바텀업으로 for문으로 아래부터 쌓아서올라감
    for (int i = 2; i<=n; i++) {
      dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
  }

  public static void main(String[] args) {
    int n = 10;
    System.out.println(fiboBottomUp(n)); // 55
  }

• bottom-up과 top-down 방식 둘 다 각 항을 한번씩만 계산하고 저장된 값을 쓰기 때문에 시간 복잡도는 O(n)으로 해결된다.