동적 계획법(DP)과 분할 정복 마스터하기

1. 동적 계획법과 분할 정복의 기본 개념

2. 피보나치 수열을 통한 동적 계획법과 분할 정복의 차이점 이해

 

 

1. 동적 계획법과 분할 정복의 기본 개념

 

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

 

 1) 정의

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

 

 2) 특징 - Memorization의 기법 활용

 : Memorization 기법이란 이전에 풀었던 문제의 정답이나 결과 값을 저장하여, 이후의 문제를 풀 때 다시 계산하지 않고, 미리 계산된 값을 불러와서 문제를 해결하는 방법입니다. 

 

가장 쉽게 설명하면 문제를 세부적으로 나누어서 해결할 때 이전에 계산했던 결과를 재활용하는 것입니다. 그래서 동적 계획법은 Bottom-up 방식의 문제 풀이라고 볼 수 있죠.

 

(2) 분할 정복( Divide and Conquer ) 

 

1) 정의

: 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

 

2) 특징 - 재귀함수를 활용한 Top-Down 해결 방식

 : 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식입니다. 그래서 하위 레벨의 문제들은 서로 중복 되는 Case가 없습니다. 

 

 

두 방식은 문제를 디테일하게 쪼개서 문제를 해결한다는 방식에서 공통점이 있지만, 문제를 해결하는 방향성과 그 특징에서 가장 큰 차이점을 보입니다. 

 

 

2. 피보나치 수열을 통한 동적 계획법과 분할 정복의 차이점 이해

 

피보나치 함수는 지난 포스팅에 설명하기도 했고, 너무나도 유명한 수열이니까 아래의 링크로 설명을 대체하도록 하겠습니다. 

 

피보나치 수열이란? (출처: 위키백과)

 

(1) 분할 정복 관점에서 피보나치의 수열의 해결

 

재귀함수를 활용하는 방법은 대표적인 분할 정복 방식의 문제 풀이 해결이죠. 

 

지난 시간 재귀함수에 대한 포스팅을 할 때 이미 간단한 알고리즘을 구성해 봤습니다. 그때 구성한 알고리즘은 아래와 같습니다. 

 

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

 

하지만 이러한 방식은 중복 계산을 많이 하기 때문에 시간과 메모리 공간의 자원을 낭비하게 되죠. 실제로 이러한 방식으로 백준의 피보나치 수열 문제를 풀게 되면 시공간 복잡도 초과로 정답 제출에 실패하게 됩니다. 

 

똑같은 문제를 이번에는 동적 계획법으로 풀어보도록 하겠습니다. 

 

(2) 동적 계획법 접근의 피보나치 수열 해결 

def fibo(n):
    
    history = [0 for i in range(n + 1)]
    history[0] = 0
    history[1] = 1
    
    for index in range(2, n + 1):
        history[index] = history[index - 1] + history[index - 2]
    
    
    return history[n]

 

이 코드에서 가장 핵심은 미리 저장 공간을 생성한 뒤 계산 결과를 저장 공간에 입력하는 것입니다. 

 

그래서 필요한 정수가 주어졌을 때는 처음부터 계산을 하는 것이 아니라 미리 계산된 결과를 바탕으로 필요한 계산만 하는 것이죠. 

 

이렇게 하면 정수가 주어질 때마다 계속 계산을 하는 것이 아니라 한 번 계산하고, 저장하면 끝인거죠.