파이썬- 다이나믹 프로그래밍 1 (피보나치)

목차

-인트로
-피보나치수열
-뒤에서 내려가기 : recursion
-뒤에서 내려가는 방식을 효율적으로 만들기 : memo
-앞에서 올라가기 : tublatioin
-정리

시작

1.다이나믹 프로그래밍이 뭐임?

다이나믹 프로그래밍은 계산 결과를 저장해 두었다가,
필요할 때 사용하는 알고리즘 기법입니다.
우리는 다이나믹 프로그래밍 기법과 비슷한 행동을 초등학교 때부터 했습니다.
초등학교 때 했던 3 자릿수 곱셈에 대해서 생각해봅시다.
머리가 좋으신 분들은 이를 암산하여 계산하겠지만,

대부분의 우리는 그렇지 못했습니다.
그래서 학교에서는 곱할 두 수를 이면지에 작성하고,
한 자리씩 계산하여 마지막에 결과를 취합하는 방법을 사용하였습니다.

이 방법은 메모지에 결과를 저장하였다 사용한다는 점에서 다이내믹 프로그래밍과 유사합니다.

2. 저장했다 사용하는 거면 쉬운 거 아님? 대충 하면 될 거 같은데.

다이나믹 프로그래밍은 이처럼 익숙한 방법이긴 하지만,
쉽지 않습니다... 그 이유는
아까 예시를 들었던 곱하기가 다이나믹 프로그래밍 문제로 출제되었다고 생각을 해봅시다.
그러면 우리는 아까 사용했던 곱하기 패턴을 발견하고,
이를 프로그램으로 구현해야 합니다.
여기서 문제는 발견한 곱하기 패턴이 코딩으로 구현했을 때 간결하면서도 효율적이 여야 합니다.
결국 하고 싶은 말은 문제에서 패턴을 발견하고 깔끔하고 효율적인 프로그램을 구현하는데 최적화가 쉽지 않습니다.
그래서 지속적이고 체계적인 수련이 필요합니다.

3. 이번 시간에 할 일.

피보나치수열에 대한 다이내믹 프로그래밍 문제를 풀기 위한 생각 방법부터 구현까지 다룰 것입니다.

피보나치수열

피보나치수열의 이름을 a [i]라고 부릅시다.
여기서 i는 피보나치의 i번째 값입니다.
피보나치수열은
fib [i] = fib [i-1] + fib [i-2], i = 0, 1, 2, 3,...... inf 그리고 fib [0] = 0 fib [1] = 1
의 관계를 가집니다.
이를 7까지 나열해 보면 아래와 같습니다.

fib[0]	fib[1]	fib[2]	fib[3]	fib[4]	fib[5]	fib[6]	fib[7]
0	1	1	2	3	5	8	13

1. 피보나치 패턴을 뒤에서부터 계산하기 : 피보나치 재귀적으로 구현하기

현재까지 피보나치수열의 패턴을 발견하였고,
이를 7번째까지 작성해 보았습니다.
이 상태에서 재귀적으로 피보나치 함수를 작성해 봅시다.
피보나치 함수는 0을 포함하는 자연수 i를 파라 매터로 받고,
a [i]를 리턴하는 함수입니다.

def fib(n): 
	if n == 0: 
		return 0 
	if n == 1:
		return 1 
	return fib(n-1)+fib(n-2)

 

note
아마도 간단하게 구현이 가능했다고 생각을 해야 합니다.
만약 여기서 기분이 찝찝하다면,
재귀 용법을 공부하고 다시 봅시다.

 

구현한 결과를 테스트해봅시다.

7과 17은 무지 빨리된다. 

하지만 40은 될 기미가 보이지 않습니다.
손으로 계산해도 이보단 빠를 것입니다.
무슨 문제 이길래 손 계산보다 느길 걸까요?
문제를 찾기 위해 그림을 그려봅시다.

리커션으로 구현한 알고리즘을 트리 형태로 나타내었습니다.
트리의 depth는 인풋 값으로 받은 n이고 depth마타 n개씩 node가 증가됩니다.
그래서 2**n번의 함수 호출이 이루어 지었다. 빅오 노테이션으로 O(2**n)입니다.
만약 n이 40이면 어떨까요?

1조번이 호출이 된다. 답이 없습니다.
아까 전에 손으로 한 것보다 느릴 거 같다고 했습니다.
왜 컴퓨터의 연산이 손으로 한것 보다 느린 걸까요?
그 이유를 알아보기 위해 그림을 분석해봅시다.

그림을 보면 패턴이 보입니다.
번호 4가 2번 등장하고 3이 3번 등장합니다.
아까 구현한 fib() 함수는 이렇게 했던 계산을 다시 수행합니다.
만약 손으로 계산한다고 생각을 해봅시다.
그러면 우리는 fib(6)을 구하기 위해 fib(4)를 종이에 기록해 두었다가,
필요하면 결과를 다시 사용할 것입니다.
손으로 하면 빠를 것 같은 느낌은 연산했던 결과를 기록했냐 안했냐의 차이입니다.

그러면 우리가 구현했던 fib() 함수에 연산 결과를 저장했다 사용하는 방법을 적용하면.
빨라질까? 빠르면 얼마나 빨라질까요?
숫자마다 한 번씩만 계산하고 필요할 때마다 꺼내 쓰면,

이만 정도만 하면 됩니다.
만약 이 것이 명확하지 않는다면,

재귀 함수가 어떠한 순서대로 실행이 되고 종료가 되는지 명확하게 공부할 필요가 있습니다.

재귀함수에 대해 명확하지 않다면 클릭하자!. 클릭!

결과를 저장하는 방법을 사용한 경우  n*2번 함수 호출이 됩니다.

빅오 노테이션으로  O(n*2)의 시간복잡도를 가집니다.

 

그러면 구현해 봅시다.

memo = {0 :1 , 1: 1, 2: 2}
def fib(n, memo):
    if n in memo:
        return memo[n]
    result = fib(n-1, memo)+fib(n-2, memo)
    memo.setdefault(n, result)
    return memo[n]
    
print(fib(40, memo))

아까 될 기미가 보이지 않던 40이 순식간에 계산이 됩니다.

memo를 시용하기 전에는 O(2**n)의 시간복잡도에서 memo를 사용하여 O(2*n)의 시간복잡도로

변경이 되었기에 가능한 일입니다.

 

2. 처음부터 메모해 가면서 결과 얻기 :  tubulation

이전 챕터에서 사용한 재귀적인 방법으로 다이나믹 프로그래밍을 구현하는 방법은,

1. 일단 답이 나오게 구현한다.

2. 재귀함수 호출 tree를 그려본다.

3. 반복되는 패턴이 있는지 확인한다.

4. 반복되는 패턴이 있으면 memo 하여 사용하도록 구현한다.

였습니다.

 

그러면 재귀적으로 호출할 필요 없이.

for loop를 이용하여 앞에서부터 차근차근 계산하면 좋지 않을까요?이러한 방법을 tubulation이라고 합니다.

 

재귀적으로 사용을 하나 for loop를 사용하나 거기서 거긴데.

for loop가 함수호출 과정이 없기 때문에 좀 더 효율적입니다.

하지만 상황에 따라 for loop를 사용하기에 뇌정지가 오는 문제들이 있습니다.

그래서 그냥 그때그때 사용합시다.

 

for loop의 경우 점화식을 명확하게 발견했을 때 사용하기 좋습니다.

피보나치수열도 이에 해당이 됩니다.

그러면 for loop를 이용하여 구현하면 어떤지 해봅시다.

n = 7

fib = [ 1 for _ in range(n+1) ]

for i in range(2,n+1):
    fib[i] = fib[i-1] + fib[i-2]
    print("fib"+str(i)+'계산됨')
    print(fib)
    
    
    
----> 출력결과
fib2계산됨
[1, 1, 2, 1, 1, 1, 1, 1]
fib3계산됨
[1, 1, 2, 3, 1, 1, 1, 1]
fib4계산됨
[1, 1, 2, 3, 5, 1, 1, 1]
fib5계산됨
[1, 1, 2, 3, 5, 8, 1, 1]
fib6계산됨
[1, 1, 2, 3, 5, 8, 13, 1]
fib7계산됨
[1, 1, 2, 3, 5, 8, 13, 21]

깔끔하죠?

정리

 

재귀로 하든지 for 루프로 하든지 큰 차이는 없습니다.

상황에 따라 생각하기 쉬운 방법을 사용하면 됩니다.

 

재귀를 사용하는 경우

1. 일단 무지성으로 정답나 오게 만들기

2. 중복되는 부분을 확인하기 위해 tree 그리기

3. 중복되는 부분이 있으면 memo를 이용하여 업데이트 하기

이러한 사고 흐름으로 작성하면 됩니다.

for loop를 사용 하는 경우

1. 점화식 찾기

2. 점화식 정확한지 확인하기

3. 진짜 한 번 더 확인하기

4. for loop로 구현하기

로 하면 됩니다. 

개인적으로 for loop를 이용하는 경우.

잘못된 점화식을 사용하는 경우가 있어.

점화식이 명확히 맞는지 확인하는 프로세스가 있으면 좋을 것 같습니다.