[이것이 코딩테스트다] 18일차 - 다이나믹 프로그래밍(DP)

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 8 다이나믹 프로그래밍

우리는 컴퓨터의 연산속도, 메모리 공간을 최대한으로 활용할 수 있는 프로그램을 작성해야한다. 

 

다이나믹 프로그래밍은

• 큰 문제를 작게 만들고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
• 메모리공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법

다이나믹 프로그래밍 조건

1. 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 한다.

 

다이나믹 프로그래밍은 메모이제이션 방법을 활용하여 작은 문제의 정답을 저장하고 이를 다음 연산에 활용한다 

메모이제이션(=캐싱)은 한 번 구한 결과를 메모리 공간에 메모해두고 호출시 메모한 결과를 그대로 가져오는 기법이다.

 

다이나믹 프로그래밍 방식

• 탑다운(Top-Down) 방식 : 재귀함수를 활용하여 소스코드를 작성, 큰문제를 해결하기 위해 작은 문제를 호출
• 보텀업(Bottom-Up) 방식 : 반복문을 이용하여 소스코드를 작성, 작은 문제부터 차근차근 답을 도출

다이나믹 프로그래밍의 전형적인 형태는 코텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부른다.

탑다운 방식(재귀함수로 구현)으로 문제를 풀이할때 시스템상 재귀함수의 스택 크기가 한정되어 있어 큰 수를 입력할 경우 'recursion depth' 와 관련된 오류가 발생할 수 있다. 가능하다면 탑다운 방식보다 보텀업 방식으로 소스코드를 구현하는 것을 권장한다 

 

 

 

기존의 알고리즘으로 해결하기 어려운 문제 중 다이나믹 프로그래밍으로 해결할 수 있는 문제 예시

• 피보나치 수열

출처: 이것이 취업을 위한 코딩테스트다 209p

1,2번째 피보나치 수 = 1, n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수

## 재귀함수로 구현
def fibo(x):
	if x ==1 or x==2:
    	return 1
    return fibo(x-1) + fibo(x-2)
    
print (fibo(4))

이때 n값이 커진다면 계산 횟수가 기하급수적으로 늘어나는 단점이 있다 

이 소스코드의 시간복잡도는 O(2^n)이다 

출처: 이것이 취업을 위한 코딩테스트다 211p

n=6일때 함수 호출과정이다 동일한 연산이 여러번 수행되고 있다 

 

다음은 탑다운방식(재귀함수로 구현, 메모이제이션 방법)으로 구현한 피보나치 수열 소스코드이다

## Top Down Fibonacci Function

d = [0]*100 ## Memoization을 위한 리스트 초기화

def fibo(x):
	if x == 1 or x == 2:
    	return 1
    ## 이미 전에 계산한 적이 있다면 그 값을 반환
    if d[x] != 0:
    	return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]
    
print (fibo(99))

출처: 이것이 취업을 위한 코딩테스트다 213p

다음과 같이 소스코드를 작성할 시 색칠된 노드방 방문하게 되며 이때 시간복잡도는 O(N)이다.

 

재귀함수 이용시 함수를 다시 호출했을때 메모리상에 적재되는 일련의 과정을 따라야하므로 오버헤드가 발생할 수 있다.

따라서 재귀함수 대신 반복문을 사용하여 DP의성능을 더 좋게 할 수 있다.

보텁업 방식은 동일한 원리를 적용하되 단순히 반복문을 사용항 문제를 해결한 것이다. 

 

아래는 보텀업 방식으로 구현한 피보나치 수열 소스코드이다

## Bottom Up Fibonacci Function

d = [0] *100

d[1] = 1
d[2] = 2
n = 99

for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print (d[n])

 

코딩테스트 문제가 다이나믹 프로그래밍 문제임을 파악할 수 있는 방법은 다음이다 

1. 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래걸린다 -> 문제를 해결할 때 사용할 수 있는 중복되는 과정이 있으면 DP로 풀이 가능
2. 메모이제이션을 사용할 수 있다