08. 동적 계획법 (Dynamic Programing) 과 분할정복 (Divide and Conquer)

동적 계획법 (Dynamic Programing, DP)

- 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분문제의 해를 재활용해서 보다 큰 크기의 부분문제를 해결
  최종적으로 전체 문제를 해결하는 알고리즘

- 상향식 접근법으로 가장 최하위의 해답을 구한 후 이를 저장하고, 해당 결과값을 이용해서 상위문제를 풀어나가는 방식

- Memorization (메모제이션) 이란 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체
 실행속도를 빠르게 하는 기술

- 문제를 잘게 쪼갤 때, 부분문제는 중복되는 경우 재활용 된다 - 예) 피보나치 수열

* 요약
1. 작은 문제 부터 먼저 해결하여 값을 저장한다.
2. 점차 큰 크기의 문제 부분을 해결하는 데 중복된 작은 문제는 계산하지 않고 캐싱된 곳에서 값을 가져온다

 

재귀용법을 이용한 방식
재귀용법으로 하는 경우 중복되는 곳도 실행하여 해를 구한다

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

 

동적 계획법을 이용한 방식
중복되는 곳은 계산하지 않고 바로 값을 리턴하지만 캐시라는 저장공간을 미리 만들어야 한다

 

def fiboDp(num):
    cache = [0 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]

 

분할 정복 (Divide and Conquer)

- 문제늘 나눌 수 없을 때 까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘 (퀵 정렬, 병합 정렬)

- 하향식 접근법으로, 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식 (일반적으로 재귀함수 사용)

- 문제를 잘게 쪼갤 때, 부분문제는 서로 중복되지 않는다

동적 계획법과 분할정복의 공통점과 차이점

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