다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍

• 해결한 작은 문제로 큰 문제를 해결하는 문제 해결 방식이다.

• 통상적으로 메모리를 더 사용하여 시간 복잡도를 개선할 때 많이 사용된다.

• 시간 복잡도가 비효율적인 알고리즘이 있을 때 부분 문제의 반복이 발생하는 경우 적용하면 효과적이다.

• 다이나믹 프로그래밍 문제를 해결하기 위해 점화식을 찾는 것이 핵심적인 과정이다.

  * 점화식: 인접한 항으로 현재 값을 결정하는 관계식을 의미한다.
  → 일반적으로 최적 부분 구조를 만족한다는 특징 있음.

  다이나믹 프로그래밍 사용조건

• 두 조건을 만족할 때 사용가능하다.

1. 최적 부분 구조(Optimal substructure)

   • 큰 문제를 유사한 형태의 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결한다.(재귀함수, 피보나치 수열, 하향식 접근법)
   • 메모이제이션을 통해 해결한 문제를 기록함으로 성능 개선을 한다.(작은 문제를 기록함으로 큰문제를 해결한다.)

2. 반복되는 부분 문제(Overlapping sub-problem)

   • 동일한 작은 문제를 반복적으로 해결해야 한다.(샹항식 접근법, 타뷸레이션)

   메모이제이션 : 필요할 때 계산한다.
   타뷸레이션 : 필요한 값들을 미리 계산해두는 것, 미리 계산해 뒀다가 꺼내 사용한다.
   보통 코테에서는 메모이제이션을 사용한다.

점화식 최적 부분 구조

• 피보나치 수열 예시: [1,1,2,3,5,8,13,21,34,55,89,....]
• 피보나치 수열의 점화식: a𝘯 = a𝘯-₁ + a𝘯-₂ (a₁ = 1, a₂ = 1)
• 가장 작은 문제 ? fibonacci(1) = 1, fibonacci(2) = 1
• 작은 문제로 큰 문제를 해결 할 수 있나 ? f(n) = f(n - 1) + f(n - 2)
  이전 두 값을 저장해두면 다음 값을 알 수 있다.(규칙이 있으면 가능)

점화식의 기본적인 구성 요소

1. 초기항
2. 인접한 항과의 관계
   • 점화식은 재귀함수로 표현할 수 있다.
   • 재귀함수는 무한루프에 빠지지 않기위해서 종료조건이 있어야하 하는데, 이것이 점화식의 초기항과 같은 역할을 수행한다.

• 피보나치 함수를 재귀함수로 구현

a𝘯 = a𝘯-₁ + a𝘯-₂(a₁ = 1, a₂ = 1)

function fibo(x) {
if( x == 1 || x == 2) {

	return 1;  // 종료 조건이 없으면 무한루프
	}
return fibo(x - 1) + fibo(x - 2); // 실질적인 점화식 부분

}
console.log(fibo(4))

→ 이런경우 중복되는 부분 문제가 발생한다.(이미 구한 값을 불필요하게 반복계산)
→ 다이나믹 프로그래밍은 이 문제를 해결할 수 있도록 함.

피보나치 수열(하향식)

d = new Array(100).fill(0); 
// 한번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
// 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
function fibo(x) {

  if(x == 1 || x == 2 ) {   // 종료조건이 없으면 무한 루프
  
  return 1;  // 종료조건 : 1 or 2 일 때 1 반환 
  }
  // 이미 계산한 적 있는 문제라면 그대로 반환
if(d[x] != 0) {
	return d[x]       // 한번 해결한 문제는 여러 번 해결하지 않도록
}
  // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
  d[x] = fibo(x - 1) + fibo(x - 2);  // 실질적인 점화식 부분
  return d[x]
} 
console.log(fibo(99))

피보나치 수열(상향식)

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = new Array(100).fil(0);

// 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1;
d[2] = 1;
n = 99;

// 피보나치 함수 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for(let i = 3; i<= n; i++) {
	d[i] = d[i - 1] + d[i - 2];
}
console.log(d[n])

다이나믹 프로그래밍의 일반 형태

function dp() {
  
1️⃣ 종료 조건(언제 멈출지)
2️⃣ 이미 해결한 문제라면, 정답을 그대로 반환(메모리에 저장)
3️⃣ 점화식에 따라 정답 계산

}

문제 해결 접근 순서

1. 문제 이해
2. 점화식 찾아내기 → 일반적으로 가장 핵심적인 부분이다.
3. 구현 방식(상향식, 하향식) 결정하기
4. 점화식을 실제 코드로 구현하기

* 상향식 : 반복문을 이용해 초기 항부터 계산한다.
* 하향식: 재귀함수로 큰 항을 구하기 위해 작은(이전)항을 호출하는 방식이다.
→ 이미 구한 함수 값을 담는 테이블을 흔히 DP 테이블, 메모이제이션이라고 한다.

• 부분문제의 정답을 모아서 큰 문제를 해결하는 방식/ 큰 문제부터 호출하여 작은 문제를 재귀적으로 호출하는 방식으로 이해할 수 있다.
• 재귀함수가 많이 호출하는 경우 스텍오브플로우 문제가 발생할 수 있으니 상향식 접근방법 추천