[알고리즘] DP(Dynamic Programming, 동적 계획법)란?

예전 공부 자료 뒤적이다 찾은 작년 스터디 자료!ㅎㅎ

노션에 숨겨져 있다 보니 찾기 힘들어서 여기에도 옮겨놓는다.

1. DP(Dynamic Programming, 동적 계획법)란??

• 큰 문제를 작은 문제로 나누어서 푸는 방법

💡 분할 정복(Divide and Conquer) vs DP
    둘 다 큰 문제를 작은 문제로 나누는 거 아닌가요?
    ⇒ 분할정복은 작은 문제 중복 불가, DP는 가능!

• 이름에는 아~무 의미가 없다!ㅎ
  Richard Bellman이 1950년대에 그냥 멋있어서 이름을 이렇게 붙였다고,,
• 쉽게 말해서 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

---

2. DP 사용 조건

1. 겹치는 부분 문제가 있을 때(Overlapping Subproblem)
   • 큰 문제를 작은 문제로 나눌 수 있는 경우
2. 최적화 부분 구조 (Optimal Substructure)
   • 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일한 경우
   • 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP 를 사용할 수 있다 !

---

3. DP는 왜 쓰지?(재귀 vs DP)

3-1. 겹치는 부분 문제가 있을 때(Overlapping Subproblem)

• 재귀를 사용하면 로직이 반복되면서 비효율적으로 계산된다..
• 재귀의 대표적인 예 : 피보나치 수열
• 피보나치 수열? ⇒ 첫번째 및 두번째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (n >= 2)

 

• 1 1 2 3 5 8 13 21 ...
• 재귀함수 방식

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.

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

 

 

 

• DP 사용한 풀이(메모이제이션)

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
 //일단 초기 배열이 [0, 1]에서 시작하여 배열의 요소를 누적해 나가는 방법
 //이미 구한 건 배열의 요소로 저장한다. (런타임이 초과 방지)

 let newArr = [0, 1]; //0번째 1번째 요소는 고정시켜두고

  let fib = (n) => { //함수 한개를 선언해주고
    if (newArr[n] !== undefined){
      return newArr[n]; //이미 있는 건 그대로 리턴
    }
    newArr[n] = fib(n - 1) + fib(n - 2); //없는 건 새로 만들어서 저장!!!*****
    return newArr[n];
  };

  return fib(n);
}

• 요소가 없는 경우: 새로 만들어서 그 값을 배열에 넣어주기(-->피보나치 수열을 '메모'하는 캐시 배열을 만들어서 값을 채워주는 것)

⇒ 메모이제이션을 하지 않으면, O(대략 피보나치 n번째까지의 총합)만큼의 시간에 값을 구하게 된다. 대략 O(2n제곱) 만큼의 시간복잡도가 걸린다.

⇒ 메모이제이션을 하면 대략 O(3n)만큼의 시간에 값을 구하게 된다.

3-2. 최적화 부분 구조 (Optimal Substructure)

• 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면,
  • 서울 -> 대전 -> 대구 -> 부산
• 대전에서 부산을 가는 가장 빠른 길은? 대구를 거쳐야 한다.
  • 만일 대전에서 부산을 가는 가장 빠른 길이 울산을 거쳐야 한다면?
  • 서울 -> 대전 -> 울산 -> 부산이 되는 것이 맞다.
  • 작은 문제의 정답을 이용하여 큰 문제의 정답을 구할 수 있음
• DP 최적화의 핵심
  • 각 작은 문제는 한 번만 풀기
  • 최적화 부분 구조를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.
  • 정답을 한 번 구했으면, 어딘가에 메모해놓는다.(배열 사용) ⇒ Memoization

4. DP 구현 방법

4-1. 메모이제이션(Memoization)

• 연산은 한 번만!
• 1) 한 번 구한 결과를 메모리에 저장해두고 ⇒ 어딘가에 메모해놓기 때문에 Memoization이라고 한다!
• 2) 같은 식을 다시 호출하면 저장해둔 결과를 그대로 가져오는 기법

💡 Tabulation?
Bottom-up인 경우에는 메모이제이션이 아닌 Tabulation(표 작성이라는 의미!)이라고 한다.
반복문을 이용해서 dp[0]부터 하나씩 채우는 과정을 “table-filling”,
이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라고 한다.
기본적으로 결과값 기억해서 재활용한다는 점에서 메모이제이션과 크게 다르지 않다.

4-2. Top-down

• 큰 문제부터 문제를 쪼개가며 작은 문제로 만들고 다시 합쳐가며 원래 문제를 푸는 방식
• 재귀로 구현
• 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
• 메모이제이션은 이 경우에만 사용된다
• 과정
  1. 큰 문제를 작은 문제로 나눈다
  2. 작은 문제를 푼다
  3. 푼 작은 문제를 바탕으로 큰 문제를 푼다

4-3. Bottom-up

• 작은 문제들을 모아서 큰 문제를 만들어 쌓아 올려가는 방식(작은 문제부터 차례로 풀기)
• Bottom-up은 주로 반복문을 사용해서 구현함

// bottomUp(6) 을 호출하면 fiboData[2] 부터 차근 차근 데이터를 구한다
int bottomUp(int n) {
    fiboData[0] = 0;
    fiboData[1] = 1;

    for (int i=2; i<=n; i++)
      fiboData[i] = fiboData[i - 1] + fiboData[i - 2];

    return fiboData[n];
}

🤔 Top-down과 Bottom-up의 시간차이?

• 모름!
• Bottom-up 방식은 모든 문제를 풀고 Top-down은 그렇지 않은 경우가 있기 때문에,,
• 재귀로 풀었을 때 Stack Overflow가 났다면 다이나믹 프로그래밍을 잘못 구현했을 확률이 높다.

🤔 Top-down과 Bottom-up은 서로 대체 가능한가?

🙆🏻가능! 대부분 Top-down으로 풀 수 있는 문제는 Bottom-up으로도 풀 수 있다.

다이나믹 프로그래밍 문제풀이 전략

1) DP로 풀 수 있는 문제인지 확인

• 조건 충족하는지 확인

2) 문제의 변수 파악

• 현재 변수에 따라 결과 값 찾아서 전달하고 재사용해야 한다 → 문제 내 변수 개수 파악 필요!
  • 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 변수는 n 하나
  • 문자열 간의 차이를 구할 때는 문자열의 길이, Edit 거리 등 2가지 변수

3) 변수 간 관계식 만들기(점화식)

• 난이도 UP ⇒ 점화식의 정의를 조금 변경

4) 메모하기(memoization or tabulation)

5) 기저 상태 파악하기

• 가장 작은 문제의 상태를 파악하기
• 직접 손으로 몇 가지 풀어보는 경우가 많다.
• 파악한 기저 문제를 배열 등에 저장하면 된다.

6) 구현하기

• Bottom-Up(Tabulation 방식)
• Top-Down(Memoization 방식)

---

📚 참고자료

https://velog.io/@jakeseo_me/자바스크립트로-알고리즘-정리하기-9-다이나믹-프로그래밍

알고리즘 - Dynamic Programming(동적 계획법)

---

👾이번 주 문제

• N으로 표현(Level 3)
• 사칙연산(Level 4)