이것이 코딩테스트다 | 다이나믹 프로그래밍

1. Dynamic Proogramming , 동적 계획법

• 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법

• 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘

• 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 해결하고자 하는 문제들의 중복 여부를 확인해보자!

• 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다.

예시 1. 피보나치 수열

• 파이썬에서는 이러한 수열을 리스트 자료형으로 처리한다.
• 수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문이다.

• f(4)를 구하려면 다음과 같이 함수 f를 반복해서 호출한다.
• f(2)와 f(1)은 항상 1이기 때문에 f(1)이나 f(2)를 만났을 때는 호출을 정지한다.

소스코드

# 피보나치 함수를 재귀 함수로 표현
def fibo(x):
	if x==1 or x==2:
    	return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

• 소스코드를 이런 식으로 작성하면 심각한 문제가 발생한다.
• f(n)함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문!
• 이 소스코드의 시간 복잡도는 O(2^n)의 지수 시간이 소요된다

• 그림에서 f(3)은 총 3번 호출 되었다.
• 즉, f(n)에서 n이 커지면 커질수록 반복해서 호출하는 수가 많아진다.

이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다.

이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.
다만 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

피보나치 수열은 이러한 조건을 만족하는 대표 문제이다.

이 문제를 메모이제이션(Memoization) 기법을 사용해서 해결해보자.

메모이제이션
다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
메모이제이션은 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 한다.
Top-Down 방식에 국한되어 사용하는 표현.


DP 테이블
Bottom-Up 방식에서 사용되는 결과 저장용 리스트

한 번 구한 정보를 리스트에 저장하면 메모이제이션이 구현된다.
다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구현한 정답을 그대로 리스트에서 가져오면 된다.

소스코드

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수 (Fibonacci Function)를 재귀함수로 표현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
	# 종료 조건(1 혹은 2일 때 1을 반환)
    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))

파이썬 프로그램을 실행해보면 99번째 피보나치 수를 구하도록 했음에도 불구하고 금방 정답을 도출하는 것을 알 수 있다.

정리

1) 다이나믹 프로그래밍
큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법.

2) 퀵 정렬
정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록해 분할 정복 알고리즘으로 분류된다

3) 다이나믹 프로그래밍과 퀵 정렬의 차이점
다이나믹 프로그래밍은 문제들이 서로 영향을 미친다.

퀵 정렬 예시

한 번 기준 원소(pivot)가 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다

다이나믹 프로그래믹 예시

한 번 해결했던 문제를 다시금 해결한다. 그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환한다.

• 다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이다.
  왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)을 푸는 데 사용되는 방식으로 이어지기 때문이다.
• 실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문한다
  

호출되는 함수 확인 (Top-down 방식)

d = [0] * 100

def pibo(x):
	print('f(' + str(x) + ')', end = ' ')
	
    if x==1 or x==2:
    	return 1
    
    if d[x] != 0:
    	return d[x]
    
    d[x] = pibo(x-1) + pibo(x-2)
    return d[x]

pibo(6)

결과

f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

호출되는 함수 확인 (Bottom-Up 방식)

d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

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