[Python] 이것이 코딩테스트다 with 파이썬 - 다이나믹 프로그래밍 (DP)

해당 문제 및 해설은 "이것이 코딩테스트 다 with 파이썬" 책을 기준으로 요약 및 정리하여 작성하였습니다.

 

이것이 코딩테스트다 with 파이썬 구입처

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

---

 

중복되는 연산을 줄이자

 

우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

다만, 어떤 문제는 메모리 공간을 약간 더 활용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.

대표적인 방법이 동적 계획법 이라고도 불리는, '다이나믹 프로그래밍 (Dynamic Programming)' 이다.

 

다이나믹 프로그래밍 은 2 가지 방법이 있다. ( 탑 다운, 바텀 업 )

다이나믹 프로그래밍 을 위해 자주 사용되는 메모리제이션 기법 까지 작성 예정이다.

 

다이나믹 프로그래밍 대표적인 예시 - 파보나치 수열을 구현해보자.

 

피보나치 수열 - 1

 

파보나치 함수 소스코드 - 1

 

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

print(fibo(4))

 

문제점

 

f(n) 함수에서 n 이 커지면 커질 수록 수행 시간이 기하 급수적으로 늘어 난다.

아래 그림을 보면 동일한 함수(f(3)) 가 반복적으로 호출되는 것을 알 수 있다.

 

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

 

피보나치 수열 - 2

 

다음 조건을 만족할 때 다이나믹 프로그래밍을 사용할 수 있다.

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

그렇다면 메모리제이션 기법을 사용해보자.

 

메모리제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 

메모리제이션은 값을 저장하는 방법이므로 캐싱 이라고도 한다.

 

피보나치 수열 소스코드(재귀적) - 2

 

# 한 번 계산된 결과를 메모리제이션 하기 위한 리스트 초기화

d = [0] * 100

# 피보나치 함수 를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)

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))

 

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

 

그렇다면 다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 어떻게 될까?

 

바로 O(N) 이다.

한 번 구한 결과는 다시 구해지지 않는다. 실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문한다.

 

피보나치 수열 - 3

 

 

호출되는 함수 확인 

 

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)

 

큰 문제를 해결하기 위해 작은 문제를 호출한다 하여, 탑다운 방식 이라고 말한다.

반면에, 단순히 반복을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업 방식 이라고 한다.

 

피보나치 수열 소스코드(반복적) - 3

 

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화

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)

 

사실 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다.

단순히 재귀 함수를 비효율적인 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있다면, 즉 메모리제이션을 적용할 수 있다면 코드를 개선하는 방법도 좋은 아이디어 이다. 앞서 다루었던 피보나치 수열의 예제처럼 재귀 함수를 작성한 뒤에 나중에 메모리제이션 기법을 적용해 소스코드를 수정하는 것도 좋은 방법이다.

 

한 마디로 일단 풀고, 효율성이나 시간 초과 걸리면 수정하자. 아예 못 푸는 아쉬운 경우만 없도록 하자!