[알고리즘] 동적 계획법/다이나믹 프로그래밍(DP) - 점화식

- 동적계획법 (DP 라고 많이 부름)
  - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
  - 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 
  - Memoization 기법을 사용함
    - Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
  - 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
    - 예: 피보나치 수열
- 분할 정복
  - 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  - 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    - 일반적으로 재귀함수로 구현
  - 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
    - 예: 병합 정렬, 퀵 정렬 등

 

[공통점과 차이점]
- 공통점
  - 문제를 잘게 쪼개서, 가장 작은 단위로 분할
- 차이점
  - 동적 계획법
    - 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
    - Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
  - 분할 정복
    - 부분 문제는 서로 중복되지 않음
    - Memoization 기법 사용 안함

 

동적 계획법이란?

• 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용할 수 있는 알고리즘 설계 기법
• 동적 계획법을 사용하면 불필요한 계산을 줄이고, 효율적으로 최적해를 찾을 수 있습니다.
• 다이나믹 프로그래밍(DP)라고도 불리며, 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정

조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

접근 방법

• Bottom Up 방법 : 작은 문제에서 큰 문제로 반복문 호출
• Top Down 방법 : 큰 문제에서 작은 문제로 재귀 호출

예시 1 - [피보나치수열]

0. 점화식

1. Bottom UP 방식

• 첫 번째와 두 번째 배열은 1이다.
• 세 번째는 첫 번째+두 번째, 네 번째는 두 번째+세 번째...
  

  def fibo(n):
  	fibList = [1,1]
  	for i in range(2,n+1):
  		fibList.append(fibList[i-2]+fibList[i-1])
  	return fibList[-1]​

2. Top Down 방식

• 중복 발생
• 이전 값 2개(n-1, n-2)를 계속 찾아나감. 첫 번째(0), 두 번째(1)에 도달하면 값(1)을 반환
• 시간 복잡도 : O(2^n)
  

  def fibo(n):
  	if n==0 or n==1:   #n==1 or n==2:
  		return 1
  	else:
  		return fibo(n-1) + fibo(n-2)​

3. Memoization 방식

• Top Down 단점 보완
• 배열 혹은 해시를 활용하는 것이 핵심
• 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법
• 시간 복잡도 : O(N)
  

  memo = {0:1, 1:1}
  def fibo(n):
  	if n in memo:
  		return memo[n]
  	else:
  		result = fibo(n-1) + fibo(n-2)
  		memo[n] = result
  		return result​

   
  

  #재귀. 상향식
  #재귀가 5,000번 이상 발생되면 sys 라이브러리의 setrecursionlimit() 함수 이용
  d = [0] * 100
  
  def fibo(x):
  	if x==1 or x==2:
  		return 1
  	if d[x] != 0:
  		return d[x]
  	d[x] = fibo(x-1) + fibo(x-2)
  	return d[x]
  
  print(fibo(숫자))​

  
  
  

  #반복문 (재귀보다 성능 좋음). 하향식. 제일 성능 좋은듯?
  
  d = [0] * 100
  
  d[1] = 1
  d[2] = 1
  n = 숫자
  
  for i in range(3,n+1):
  	d[i] = d[i-1] + d[i-2]
  
  print(d[n])​

예시 2 - [이웃하지 않는 숫자들의 합의 최댓값]

data = [3,4,5,6,1,2,5]

def solution(data):
	if len(data)==1:
		return data[0]
	result = [data[0], max(data[0],data[1])
	for i in range(2,len(data):
		result.append(max(result[i-1], result[i-2]+data[i])
	return result[-1]

 

---

점화식이란?

• 수열에서 n번째 항을 이전에 나온 항들로 나타낸 공식
• 인접한 항들 사이의 관계식

###점화식예시1
n=0   #1
n=1   #1
n=2   #2
n=3   #3
n=4   #5

###점화식예시2
  n 0 1 2 3 4
m 0 0 1 2 3 4
  1 0 1 3 6 10