[코딩테스트] 다이나믹 프로그래밍 개념

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

다이나믹 프로그래밍

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
• 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다

1. Overlapping Subproblem : 겹치는 작은 문제
2. Optimal Substructure : 최적 부분 구조

Overlapping Subproblem

• 피보나치 수
• F₀ = 0
• F₁ = 1
• F_n = F_n-1 + F_n-2 (n≥2)
• F_n-1 = F_n-2 + F_n-3
• F_n는 큰문제, F_n-1과 F_n-2는 작은문제
• 큰 문제를 작은 문제로 나눠서 풀고, 작은 문제의 정답을 이용해서 큰 문제를 해결해야 한다.
• 즉 큰 문제와 작은 문제를 같은 방법으로 풀 수 있고, 문제를 작은 문제로 쪼갤 수 있어야 함.

Optimal Substructure

• 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
  • ex) 서울->대전->대구->부산이 가장 빠른 길이라면, 대전->부산을 가는 가장 빠른 길은 대구를 거쳐야 한다.
  • 문제 : N번째 피보나치 수를 구하는 문제
  • 작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제
  • 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.
• 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
  • 10번째 피보나치 수를 구하기 위해 구한 4번째 피보나치 수 = 5번째 피보나치 수를 구하기 위해 구한 4번째 피보나치 수

Overlapping Subproblem + Optimal Substructure

• 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.
• Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.
• 따라서 정답을 한 번 구했으면 정답을 어딘가에 메모 = 배열에 저장 = Memoization

• 피보나치 수

  int memo[100];
  int fibonacci(int n){
  	if(n<=1){
  		return n;
  	} else {
  		if(memo[n]>0){
  			return memo[n];
  		}
  		memo[n] = fibonacci(n-1) + fibonacci(n-2);
  		return memo[n];
  	}
  }
  

1. 모든 문제를 풀어야 한다.
2. 모든 문제는 1번만 풀어야 한다.
   시간복잡도 문제의 개수 x 문제 1개를 푸는 시간 = 피보나치 : N x 1 = O(N)

• Top-down : 큰 문제를 작게 쪼개는 것 반복, 가장 작아졌을 때 return 되며 위의 문제 풀림, 재귀함수
• Bottom-up : 가장 작은 문제(F₀, F₁)로 그 다음(F₂)를 구하고… 이렇게 풀다보면 가장 큰 문제를 풀 수 있게 됨, 반복함수

문제 풀이 전략

• 점화식을 구해야 한다. 문제를 푸는데 필요한 재귀식(F_n = F_n-1 + F_n-2)

1. 점화식의 정의
   D[N] = N번째 피보나치 수
2. 문제를 작게 만들 수 있는 방법을 찾기
   N번째 피보나치 수는 N-1번째와 N-2번째를 더해서 만든다.
   D[N] = D[N-1]+D[N-2]
3. Top-Down, Bottom-up 방식 둘 중 편한 방식으로 문제 해결 (시간복잡도는 같다)