[알고리즘] 동적 계획법 (Dynamic Programming)

[알고리즘] 동적 계획법 (Dynamic Programming)

다이나믹 프로그래밍은 하나의 큰 문제를 여러개의 작은 문제들로 나눠서 해결하는 방식입니다.

 

그렇기 때문에 다이나믹 프로그래밍을 이용하여 문제를 해결하려면 2 가지 조건을 만족해야 합니다.

- 부분 반복 문제 (Overlapping Subproblem)

다이나믹 프로그래밍은 전체 문제를 여러개의 작은 문제들로 나눈 다음 그 결과값들을 이용해 전체의 답을 도출해냅니다.

 

그렇기 때문에 동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능합니다.

- 최적 부분 구조 (Optimal Substructure)

최적 부분 구조는 전체 문제의 최적해가 부분 문제들의 최적해로 이루어진 경우를 말합니다. 그렇기 때문에 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일합니다.

 

최적 부분 구조 조건은 탐욕법에도 해당하는 조건입니다.

개념과 설명

오늘은 피보나치 수열을 예로 들어 다이나믹 프로그래밍을 학습해 보도록 하겠습니다.

 

 

피보나치 수열은 다음과 같이 앞의 두 항의 합이 뒤의 항이 되어있는 수열입니다.

 

n 번째 피보나치 수를 구하는 함수를 fib(n) 이라고 정의할 때, 이는 다음과 같이 나타낼 수 있습니다.

 

fib(n) = fib(n-1) + fib(n-2)

 

우리는 이러한 식을 간단한 재귀 함수로 표현할 수 있을 것입니다.

 

아래는 피보나치 수열을 재귀함수로 이용해 작성한 코드입니다.

 

 

피보나치 수열의 개념만 이해한다면 재귀함수로 구현하는건 그닥 어렵지 않은 일입니다.

 

하지만 위 함수가 한번 실행될 때마다 같은 함수가 새롭게 두번씩 호출될 것이고, 그 과정에서 분명히 중복되는 호출들이 있을 것입니다.

 

만약 5 번째 피보나치 수를 구한다고 했을 때, 그 과정을 트리로 그려본다면 아래 그림과 같을 것입니다.

 

위 그림에서 확인할 수 있는 사실은 2가지 입니다.

 

첫번째는 시간복잡도 입니다. 피보나치 수열을 재귀함수로 구현하면 위와 같은 트리 형태의 연산이 실행되기 때문에 시간복잡도는 O(n^2) 입니다.

 

두번째는 중복 호출입니다. 5번째 피보나치 수열을 구하는 과정에서도 중복 호출되는 함수가 여러 개 있는 것을 확인할 수 있었습니다.

Memoization

위 특징들을 더 개선할 수 있는 방향은 중복 호출되는 함수들의 리턴값을 기억하고 있다가 해당 값이 필요할 경우 다시 함수를 호출할 필요 없이 필요한 값을 가져다가 사용하는 것입니다.

 

이렇게 한번 실행된 함수의 결과를 저장해두었다가 사용하는 방식으로 중복 호출을 줄이는 것을 Memoization 이라고 합니다.

 

 

위는 Memoization 을 활용해 다시 구성한 피보나치 수열 메소드입니다.

 

fib_array 에 연산에 필요한 가장 앞쪽의 값 두개인 1 을 넣어주고 1번째 피보나치 수 부터 구해나가는 방식입니다.

 

해당 방식의 시간복잡도는 코드에서도 간단하게 알아볼 수 있듯이 O(n) 입니다.

 

재귀로 구현한 방식은 값이 높은쪽부터 시작해 점차적으로 내려오는 Top-Down 방식이고, Memoization 을 이용해 구현한 방식은 값이 낮은쪽부터 시작해 점차적으로 올라가는 Bottom-Up 방식입니다.