DP & Divide and Conquer

1. 정의

• 동적 계획법
  • 입력 크기가 작은 부분 문제 해결 해당 부분 문제의 해를 활요해서 보다 큰 크기의 부분 문제를 해결
  • 상향식 접근법 최하위 해답 부터 위로
  • Memorization 기법 : 이전에 계산한 값을 저장 다시 계산하지 않도록 함
    • 예) 피보나치 수열
• 분할 정복
  • 문제를 나눌 수 없을 때까지 나누어 각각 풀면서 합병하여 문제의 답을 푸는 알고리즘
  • 하양식 접근법으로 상위 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수로 구현
  • 문제를 잘게 쪼갤 때 부분 문제는 서로 중복되지 않음
    • 예 : 병합정렬 퀵 정렬

2. 공통점과 차이점

• 공통점
  • 문제를 잘 쪼개서 가장작은 단위로 분할
• 차이점
  • 동적 계획법
    • 부분문제는 중복되어 상위 문제 해결시 재사용
    • memorization 기법 사용
  • 분할정복
    • 부분 문제는 서로 중복 되지 않음
    • memorization 기법 사용 안함

3. 동적 계획법 알고리즘 이해

피보나치 수열

→ 중복되는 값을 계산 하지 않고 저장 ~

recursive call 활용

def fibo(num):
	if num<= 1:
		return num
	return fibo(num-1) +fibo(num-2)

fibo(4) → fibo(3)+fibo(2) →fibo(2) +fibo(1)....

같은 걸 여러번 실행하게 된다.

Dynamic programming

def fibo_dp(num):
	cache = [O for index in range(num+1)]
	cache[0] = 0
	cache[1] = 1
	
	for index in range(2,num+1):
		cache[index] = cache[index-1] +cache[index-2]
	return cache[num];