[Python] 효율적인 문제해결을 위한 Memoization

알고리즘 문제를 풀이할 때 보다 효율적인 방법을 찾기 위해,

피보나치 수열을 통해 재귀와 DP의 차이를 효율성 측면에서 알아보겠습니다.

재귀를 통한 피보나치 수열 구현

def fibonacci(n):
    print("실행")
    if n == 0: return 0
    elif n == 1: return 1
    else: return fibonacci(n-1) + fibonacci(n-2)

실행 결과는 다음과 같습니다.

fibonacci(5) #5번째 피보나치 수열 값 구하기
실행
실행
실행
실행
실행
실행
실행
실행
실행
실행
실행
실행
실행
실행
실행
결과: 5, 시간경과: 0.0009913444519042969 #결과

피보나치 수열의 5번째 값을 구할 때, 함수가 15번 실행됨을 알 수 있습니다.

fibonacci(5)의 값을 구하기 위해서는 fibonacci(4)과 fibonacci(3)의 값을 알아야 하고, 이때 fibonacci(4)의 값을 구하기 위해서는 fibonacci(3)과 fibonacci(2)의 값을 알아야하고... 즉, 정답을 구하기 위해서는 가지를 치듯이 경우가 확장됩니다.

이렇듯 재귀를 통한 구현은 논리는 옳지만, 효율성이 떨어진다는 문제가 있습니다.

정답을 구하는 과정에서 함수가 비효율적으로 많이 호출된다는 것입니다.

입력값 n이 큰 숫자일수록 시간복잡도와 오버헤드가 너무 커서 시간초과가 날 수 있습니다.

 

DP - 메모이제이션(Memoization)을 사용한 구현

fibonacci(n)의 값을 구하기 위해서는 fibonacci(n-1)와 fibonacci(n-2)의 값을 알아야 합니다.

재귀는 이를 구하는 과정에서 이미 연산했던 결과를 여러 번 다시 연산을 합니다.

하지만 그럴 필요없이, 이미 n-1과 n-2의 경우의 값을 저장해두었다면 연산을 중복하여 수행할 필요가 없습니다.

이러한 논리를 활용한 기법이 메모이제이션(Memoization)입니다.

def fibonacci(n):
	print("실행")
    fibo = [0,1] #배열에 피보나치 수열 값을 순서대로 저장
    for i in range(2,n+1): #n번째에 도달할 때까지 연산
        fibo.append(fibo[i-1] + fibo[i-2]) #i번째 수열을 계산하여 배열에 삽입
    return fibo[n]

이 코드의 핵심은 자료구조를 통해 이전의 결과를 저장하는 것에 있습니다.

n이 2 이상일 때부터 피보나치 연산을 수행한 결과를 fibo 배열에 저장합니다.

그 다음 경우를 구하기 위해서는 fibo 배열의 n-1번째와 n-2번째의 값을 참조하기만 하면 됩니다.

실행 결과는 다음과 같습니다.

fibonacci(5) #5번째 피보나치 수열 값 구하기
실행
결과: 5, 시간경과: 0.0 #결과

함수가 단 한번 실행되었고, 시간 경과가 재귀에 비해 빠르다는 것을 알 수 있습니다.

 

재귀적 구현 vs DP - 메모이제이션 구현

n에 큰 값을 주어 시간복잡도 차이를 더 확실하게 알아보겠습니다.

def fibonacci(n): #재귀적 구현
    if n == 0: return 0
    elif n == 1: return 1
    else: return fibonacci(n-1) + fibonacci(n-2)
    
import time
start = time.time() #시간 측정
answer = fibonacci(36)
end = time.time() - start
print(answer, '시간:', end)

36 #input
14930352 시간: 6.740533113479614

재귀적 구현에서 n = 36일 때, 실행 시간은 약 6.7초가 걸립니다.

 

def fibonacci(n): #dp - 메모이제이션
    fibo = [0,1]
    for i in range(2,n+1):
        fibo.append(fibo[i-1] + fibo[i-2])
    return fibo[n]
    
import time
start = time.time() #시간 측정
answer = fibonacci(36)
end = time.time() - start
print(answer, '시간:', end)

36 #input
14930352 시간: 0.0

메모이제이션 구현에서 n = 36일 때, 실행 시간은 약 0초가 걸립니다.

 

추가적으로 n = 100일 때 재귀적 구현은 오랜 시간 실행되며 결과가 나오지 않지만 (결과를 기다리다 중단했습니다)

메모이제이션 코드는 0초만에 결과값으로 354224848179261915075을 출력했습니다.

---

이를 통해서 문제를 풀 때 단순히 코드로 풀이 논리를 구현하는 것에서 그치지 말고,

보다 빠르고 효율적인 문제 풀이법을 찾는 것이 더 중요함을 알 수 있습니다.

저도 직관적으로 재귀로 구현했다가 문제에서 시간초과로 틀리는 경우가 매우 많습니다...

이후 DP를 통한 문제풀이를 더 정리하여 이어서 올리도록 하겠습니다.