[JS] 동적 계획법 (Dynamic Programming)

✨ 동적 계획법

• 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식
• Greedy나 Back tracking처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미한다.
• Dynamic Programming(DP)라고도 부른다.
  • 동적 계획법이 어렵게 느껴지는 원인 중 하나
  • Dynamic하지 않고 Programming과도 관련이 없다.
• 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다.
• 두 가지 방법론이 있다.
  • 메모이제이션 (Memoization)
  • 타뷸레이션 (Tabulation)

 

---

✨ 메모이제이션 (Menoization)

• 하향식 접근법 (작은 문제들의 결과를 저장해 뒀다가 필요할 때 꺼내 쓰는 방법)
• 동적 계획법에서 작은 문제들의 결과는 항상 같다.
• 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다.

 

예시) 피보나치 수열

백트래킹같은 동적 계획법을 소개할 땐 흔히 피보니치 수열로 예시를 든다.

 

백트래킹을 이용한 피보니치 수열 구현은 중복되는 연산이 너무 많다.
이미 한번 결과를 구한 함수도 중복해서 연산을 하기 때문에 구해야하는 수열이 뒤에 있을 수록 시간이 오래걸리게 된다.

따라서 이미 해결한 문제는 기록해주자! = 메모이제이션

 

 

피보나치 수열의 가장 작은 문제는?

담은 피보나치 수열의 첫 번째와 두 번째이다.

fibonacci(1) = 1

fibonacci(2) = 1

 

우리는 이미 정답이 1이란 걸 알고 있다.

이 다음으로 검증해야할 것은 작은 문제로 큰 문제를 해결할 수 있는가 이다.

 

규칙이 있으면 가능하다!

f(n) = f(n - 1) + f(n - 2)

이전 두 값을 더해주면 다음 값을 알 수 있음

이런식으로 메모이제이션을 계속 해나가면서 다음 수열을 구할 수 있다.

 

 

---

✨ 타뷸레이션

• 상향식 접근법
• 필요한 값들을 미리 계산해두는 것
• 메모이제이션은 필요할 때 계산한다면 (Lazy evaluation), 타뷸레이션은 미리 계산해둔다 (Eager evaluation)
• 보통 코딩 테스트에선 메모이제이션을 쓰는 경우가 많다.

 

예시) 피보나치 수열

다음과 같이 미리 값들을 구해두고 꺼내쓰는 것이 타뷸레이션

 

---

 

✨ 동적 계획법 문제 접근 방법

• 동적 계획법 유형은 키워드만으로 동적 계획법 문제임을 알기 어렵다.
• 그렇기 때문에 문제 유형을 알 수 없다면 다음을 확인하자.
  • 가장 작은 문제를 정의할 수 있는가?
  • 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는가?
• 위 두 가지가 가능하다면 동적 계획법 문제이다.
• 간혹 메모리를 너무 사용하여 통과 못하는 경우도 있다.
  • 이런 경우엔 백트래킹을 이용할 수 있지만 보통 코딩 테스트에서 자주 나오진 않는다.

 

---

 

✨ 관련 문제 풀이

https://lazyhysong.tistory.com/entry/JS-DP-%EB%8B%A8%EC%96%B4-%ED%8D%BC%EC%A6%90

[JS] DP - 단어 퍼즐