#Dynamic_programming

이전 포스팅에서 Dynamic_progrmming전략을 좀 더 효율적으로 짜기 위해서는? 

피보나치 수열을 예시로 보자. 현재 시점(n)의 피보나치 수열 값을 구하기 위해서는 n-1번째 수열 값과 n-2번째 수열 값만 필요하다. 리스트나 딕셔너리 형태로 구하고자 하는 시점의 모든 과거의 시점을 구하지 않고, n-1번째 시점과 n-2번째 시점의 값만 사용해서 구해보자. 이 때, current와 previous변수를 이용한다. 

 이런 방식으로 접근할 때, 사용하는 메모리는 고정되어 있기 때문에 공간복잡도 O(1) 가 된다. 모든 과거 시점의 값이 필요하지 않은 경우에 이를 응용하면 좋겠다. 

def fib(n): #n번째 피보나치 수열 구하기
#초기값은 다음과 같이 설정된다.
    pre = 0 
    cur = 1
    
    if n < 2: #n이 2보다 작다면, 1의 값을 가지게 된다.
    	return cur
    else:
    	for i range (1, n):
        	cur, pre = cur+pre, cur
            
            return cur
            
            
            

 

나도 여러 번 풀다가 알게된 사실인데, 위의 문제에서 cur와 pre를 업데이트 하는 경우에 cur+pre값을 먼저 업데이트하고 

cur값을 pre값으로 대체하는 경우 오류가 발생할 수 있다. 그런데, 위와 같이 한 줄로 작성하면(cur, pre = cur+pre, cur 부분

업데이트하는 순서를 고려하지 않고 각 시점에 알맞는 cur, pre값을 구할 수 있었다.