[알고리즘] 동적 프로그래밍

1. 동적프로그래밍

문제를 더 작은 조각으로 나눈 다음에 앞에 위치한 조각을 기억하는것을 통해서

해야하는 작업의 양을 줄이는 방식으로 문제를 푸는 접근법이다.

 

사용 조건

최적 부분구조가 존재하는지, 반복되는 하위 문제가 있는지를 확인하고 사용할 수 있다.

문제에 어떤방식으로든 중첩되는 하위 문제들이 있어야 한다.

이 말은 한문제를 더 작은 문제들로 나눌수 있고 그 조각들중 일부가 재활용이 가능하다는 말이다.

 

최적부분 구조

하위 문제의 최적 해답을 통해서 더 큰 범주의 문제의 최적 해답을

구성할 수 있는 경우 해당 문제가 최적 부분 구조를 가진다고 한다.

예시) 피보나치 수열은 5번째의 수를 찾기 위해 4번째수와 3번째수를 이용한다.

 

2. 피보나치

function fib(n) {
  if (n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

피보나치 수열은 위와 같이 코드를 짤수 있다.

피보나치 수열은 각각의 값을 구하기 위해 전의 값들을 계속 계산해야 한다.

위 피보나치 코드의 시간복잡도는 O(2^n)으로 굉장히 나쁘다.

피보나치 수열은 중첩되는 하위 문제들이 존재하기 때문에 동적프로그래밍의 좋은 예시이다.

 

3. 동적프로그래밍

예전의 값을 기억했다가 어떻게든 저장을 해서 각 하위 문제를 풀때 다시 확인하면 복잡한 계산을 건너뛸수 있다.

(1) 메모이제이션(memoization)

보통 배열이나 객체인 데이터를 저장할 구조를 만든 다음에 하위 문제를 풀고 그 값을 저장해 둔다.

function fib(n, memo = []) {
  if (memo[n] !== undefined) return memo[n];
  if (n <= 2) return 1;
  let res = fib(n - 1, memo) + fib(n - 2, memo);
  memo[n] = res;
  return res;
}

위 코드로 시간복잡도를 O(n)까지 줄일 수 있다.

동적 프로그래밍의 핵심은 한문제를 풀때 그 문제를 더 작은 하위 문제들로 나누고

각각을 한번 이상 풀어야 할때 앞에서 계산한 값을 저장해서 같은 하위문제를 다시 풀지 않는것이다.

 

(2) 타뷸레이션(tabulation)

보통 루프와 같이 순환을 통해서 작업을한다.

가장 작은 하위 문제를 푼 다음에 그 결과를 테이블에 저장한다.

function fib(n) {
  if (n <= 2) return 1;
  let fibNums = [0, 1, 1];
  for (let i = 3; i <= n; i++) {
    fibNums[i] = fibNums[i - 1] + fibNums[i - 2];
  }
  return fibNums[n];
}

(3) 두 접근법의 차이점

메모이제이션은 재귀를 사용했기 때문에 공간적 제약을 받는다.

만약 10000번째의 피보나치 수열을 알고싶을때 메모이제이션 방법을 사용하게 된다면

콜스택 사이즈를 초과했다는 오류를 볼수 있다.

하지만 타뷸레이션은 재귀를 사용하지 않기 때문에 공간적 제약을 받지 않는다.

따라서 타뷸레이션은 원활하게 코드를 실행할 수 있다.

4. 프로그래머스 문제

프로그래머스

이전의 값들을 기억해서 계속 사용해야 하는 문제이다.

이 문제는 동적프로그래밍으로 접근이 가능하다.

function solution(land) {
    const length = land.length
    for(let i = 1 ; i<length; i++){
        land[i][0] += Math.max(land[i-1][1],land[i-1][2],land[i-1][3])
        land[i][1] += Math.max(land[i-1][0],land[i-1][2],land[i-1][3])
        land[i][2] += Math.max(land[i-1][0],land[i-1][1],land[i-1][3])
        land[i][3] += Math.max(land[i-1][0],land[i-1][1],land[i-1][2])
    }
    return Math.max(...land[length-1]);
}