Advanced Algorithm - 동적 계획법(DP) & 분할정복(Divide&Conquer)

1. 정의

1) 동적 계획법(Dynamic Programming, DP)

- 정의: 하나의 큰 문제를 해결하기 위해, 큰 문제를 작은 문제들로 나누어 부분적으로 해결한 후 그로부터 파생된 값인 해를 이용하여 최종적으로 전체 문제를 해결하는 방식의 알고리즘 

 

- 상향식 접근법: 가장 최하위 문제의 해답을 구한 후, 이를 이용하여 상위 문제를 풀어나가는 방식 

 

- 메모이제이션(Memoization) 기법: 프로그램 실행 시 이전에 계산한 값을 저장하여 동일한 연산/계산에 대해서 다시 수행하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 

 

- 왜 이런 기법들을 사용하는가? 

→ 큰 문제를 작게 쪼개어 풀다보면 중복되는 부분이 발생한다. 동일한 연산에 대해서는 1번의 연산을 수행하여 저장하는 방식을 통해 이를 재활용하고 전체적인 수행 및 연산시간을 절약하기 위함이다. ex) 피보나치 수열 

 

 

 

2) 분할 정복(Divide and Conquer)

- 정의: 상위 문제를 나눌 수 없을 때까지 분할하여 각 하위 문제를 풀고 다시 합병하여 상위 문제의 답을 얻는 방식의 알고리즘

 

- 하향식 접근법: 상위 문제의 답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식. 즉, 상위 문제의 답을 구하기 위해 이전에 수행해야 하는 절차를 수행하는 방식이다.(재귀함수로 구현)

 

- 문제를 쪼갤 때, 부분 문제의 중복이 없음

ex) 병합 정렬, 퀵 정렬, etc. 

 

 

 

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

[공통점]

- 큰 문제를 작게 쪼개어 가장 작은 단위로 분할한다.

 

[차이점]

- 동적 계획법: 부분 문제에 중복이 발생, 상위문제 해결 시 재활용 → 메모이제이션 기법 사용
- 분할 정복: 부분 문제에 중복 없음 → 메모이제이션 기법 사용 안함

---

2. 예시를 통한 동적 계획법의 이해 

 

- 위의 예시는 피보나치 수열이다. 두번째 사진은 피보나치 수열을 동적 계획법으로 풀어낸 것이다. 

 

f(6) = f(5) + f(4) 

f(5) = f(4) + f(3)

f(4) = f(3) + f(2) 

 

- 위의 식처럼 상위 값을 구하기 위해 하위 값을 계산하는 방식이다. 이를 바탕으로 f(1)부터 f(6)까지 모든 값에 대하여 동적 계획을 실행한다면 두번째 사진과 같이 트리구조로 표현할 수 있으며, 부분 문제에서 중복되는 연산이 발생하는 것을 볼 수 있다. ex) f(3), f(2), f(1) 

---

3. 동적 계획법 코드구현 

a) 재귀함수(recursive call)를 이용한 풀이법

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

 

[계산 결과] 

 

문제점)

재귀 함수를 사용하면 발생하는 문제점은 부분 문제에 대한 중복 연산이 있다는 것이다. 위의 코드를 바탕으로 설명하자면, 

f(4) = f(3) + f(2)

f(3) = f(2) + f(1)

f(2) = f(1) + f(0)

이와 같이 중복되는 연산이 수행되며, 연산에 필요한 시간이 증가한다.

 

 

 

b) 동적 계획법(DP)을 이용한 풀이법

def fibo_dp(num):
    cache = [0 for index in range(num+1)] #메모이제이션을 위한 list comprehension
    cache[0] = 0 #f(0)의 값을 저장 
    cache[1] = 1 #f(1)의 값을 저장
    
    for index in range(2,num+1): #0과 1은 저장되어 있으니 2부터 시작
        cache[index] = cache[index-1] + cache[index-2] #메모이제이션 기법 사용
    return cache[num]

 

 

[계산 결과 및 연산 과정]

- 위의 연산 관정을 보면 알 수 있듯이, 재귀함수와는 다르게 중복된 연산이 발생하지 않는다.

- 중복되는 계산을 반복수행하지 않기 위해서 List를 사용하였고 기존에 저장된 값을 이용해 다음 수열을 계산하는 방식을 사용하였다. 즉, 메모이제이션 기법을 사용한 것이다. 

 

 

 

* 파이썬 comprehension의 이해를 위한 링크 

 

www.fun-coding.org/PL&OOP5-2.html

파이썬 특수 문법(데코레이터, 이터레이터등): 파이썬 Comprehension - 잔재미코딩