동적 프로그래밍(Dynamic Programming)

1. Dynamic Programming 이란? 

        - 알고리즘을 디자인 하기 위한 전략

        - 큰 문제를 작은 문제로 나누어 푸는 문제

        (동적 프로그래밍이란 이름 때문에 동적으로 이루어지는지 찾아볼 필요 x, 그저 멋있는 이름을 붙였다는 원작자)

 

1.1 Divide and Conquer (분할 정복)과 비슷?

: 작은 문제로 나누어 푼다는 점에서 비슷한 면이 있지만 결정적 차이점은 바로, 작은 문제가 중복을 일으키는지 아닌지 이다.

분할 정복은 단지 작은 문제로 나누어 푸는 것이기 때문에 작은 문제에 반복이 일어나지 않는 것이  특징이지만,

동적 프로그래밍은 작은 문제들이 반복되는 것(답이 바뀌지 않음) 을 이용해 풀어나가는 방법이다.

1.2 Dynamic Programming 방법 

- 모든 작은 문제들은 한번만 풀어야한다.

 작은 문제의 정답을 구하면 어딘가에 그 정답을 메모해 놓는다. 그리곤 그보다 큰 문제를 풀때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다.

 

1.3 Dynamic Programming 의 조건 

- 작은 문제들이 반복된다.

- 같은 문제는 구할때 마다 정답이 같다.

 위와 같은 조건을 만족하는 경우에만 동적프로그래밍을 사용할 수 있다. 

 작은 문제의 결과값이 항상 같다는 점을 이용해 큰 문제를 푸는 것이니 당연한 것이다. 

 

1.4 Memoziation?

: 앞서 말했듯, 동적프로그래밍에선 작은 문제들이 반복되고 이 작은 문제들의 결과값이 항상 같다. 

이러한 이점을 이용하여 한번 계산한 작은 문제를 저장해놓고 다시 사용 한다. => 이것을 Memoization

ex) 피보나치 수열

피보나치는 1,1,2,3,5,8 ... 의 수를 이루게 된다 

즉, " 다음수열 = 이전 수열 + 두 단계 전 수여의 합 "이라는 점화식을 갖는 순열

 

재귀함수로  풀게되면 간단히 풀 수 있지만 n이 증가함에 따라 호출되는 함수의 수가 기하급수적으로 증가하기 때문에 일정 수 이상의 순열을 구하기가 어렵다. 

또한 이렇게 피보나치를 재귀함수로 풀게될 경우, 위의 그림처럼 했던 작업을 또 하게 된다. 

이럴 때 위에서 살펴본 동적계획법의 조건 두가지를 상기해보면 이를 동적계획법을 이용해 풀 수 있다는 사실을 알 수 있다.

 

1. 작은 문제들이 반복된다. 

: F(5)를 구하기 위해 F(4), F(3)이 필요.

다시 F(4)를 구하기 위해선 F(3), F(2)가 필요.

그러므로 F(5), F(4) 둘다 F(3)이 필요함을 알 수 있다. 

=> 즉, 작은 문제가 반복되는 구조

 

2. 같은 문제는 구할때 마다 정답이 같다.

: 피보나치 수열의 경우 첫번째, 두번째 수열은 각각 1로 고정되어 있다. 

즉, 3번째 수열은 언제나 결과가 2이다. 또한 4번째 수열은 3번째, 2번째 수열을 이용해 구하므로 언제나 정답이 같다는 사실을 알 수 있다.

def memoization_fibo(n):
	memo[0] = 1
    memo[1] = 1
    
    if n < 2:
    	return memo[n]
        
    for i in range(2, n+1):
    	memo[i] = memo[i-2] + memo[i-1]
       
    return memo[n]
    
 
if __name__ == '__main__':
	n = int(sys.stdin.readline())
    memo = [0 for i in range(n+2)]
    print(memoization_fibo(n))

n번째 fibonacci 수열을 구하는 문제를 동적프로그래밍으로 푼 코드이다. 0,1번째 수열은 항상 1이므로 미리 배열에 저장하는 것.

그 후 2번째 수열을 구할땐 배열에 저장된 이 값을 이용하여 구하는 것. 

구한 2번째 수열의 결과 값을 배열에 다시 저장한다. 

그런 식으로 진행하며 입력받은 n번째 수열을 구하게 된다. 

 

2. Bottom-up 과 Top-down 

 

2.1 구현 방법

1) Bottom-up

: 작은 문제부터 차근차근 구해 나가는 방식

def fibonacci_bottom_up(n):
	if n <= 1:
    	return n
        
    fir = 0
    sec = 1
    for i in range(0, n-1):
    	next = fir + sec
        fir = sec
        sec = next
        
    return next
    
if __name__ == '__main__':
	n = int(sys.stdin.readline())
    	print(fibonacci_bottom_up(n))

 

2) Top-down 

: 재귀함수로 구현하는 경우가 대부분 Top-down 이다. 

큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결하게 된다. 

def fibonacci_top_down(n):
	if memo[n] > 0:
    	return memo[n]
        
    if n <= 1:
    	memo[n] = n
        return memo[n]
        
    else:
    	memo[n] = fibonacci_top_down(n-1) + fibonacci_top_down(n-2)
        return memo[n]
        
 if __name__ == '__main__':
 	memo = [0 for i in range(100)]
    	n = int(sys.stdin.readline())
    	print(fibonacci_top_down(n))

 

2.2 Top-down, Bottop-up 어느 것이 더 좋은가?

: 이 질문에 정답은 없다. 다만 Top-down 의 경우 소스의 가독성이 좋다는 대신 조금 어려운 단점이 존재한다. 

Bottom-up의 경우 풀기는 쉽지만 소스의 가독성이 저하될 수 있다. 

때문에 자신에게 편한 방법으로 풀어나가는 것이 좋다. 

 

출처:

요약 https://galid1.tistory.com/507