다이나믹 프로그래밍 설명 - 이코딩, 파이썬 알고리즘 인터뷰 참고-I am yumida

박유미 2021. 12. 27. 17:13

2021. 12. 27. 17:13

오늘은 이코딩 강의와 '파이썬 알고리즘 인터뷰' 책을 참고해 다이나믹 프로그래밍을 설명하겠습니다.

파이썬 알고리즘 인터뷰 - 교보문고

95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트 | [이 책의 구성] [1부 코딩 인터뷰] 1장, ‘코딩 인터뷰’에서는 코딩 테스트에 대한 소개와 어떻게 하면 시험을 잘 치를 수 있을지, 문제 풀이

www.kyobobook.co.kr

다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘입니다.

다이나믹 프로그래밍은 문제가 아래의 조건을 만족할 때 사용할 수 있습니다.

- 최적 부분 구조: 큰 문제를 부분 문제로 나눌 수 있고 문제의 최적 해결 방안은 부분 문제에 대한 최적 해결 방안으로 구성됩니다.

- 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결할 수 있습니다.

다이나믹 프로그래밍은 상향식(Bottom up)과 하향식(Top down)으로 구성됩니다.

피보나치 수열을 구하는 코드를 다이나믹 프로그래밍의 상향식, 하향식 방법으로 나타내보겠습니다.

def fib(n):
    dp=[0]*(n+1)
    dp[1]=1
    
    for i in range(2,n+1):
    	dp[i]=dp[i-1]+dp[i-2]
    return dp[n]

상향식 방법론은 작은 하위 문제부터 차례대로 정답을 풀어나가며 큰 문제의 정답을 만듭니다.

위의 코드를 참고해, 상향식 방법론으로 5번째 피보나치 수 구하는 방식을 자세히 설명하겠습니다.

처음에 dp[0], dp[1]을 설정합니다. 이것은 곧 0번째 피보나치 수, 1번째 피보나치 수 입니다.
dp[2]=dp[1]+dp[0]로 dp[2]를 구합니다. 이것은 곧 2번째 피보나치 수입니다.
for문 안에서 2와 같은 연산을 반복하면, dp[3], dp[4], dp[5] 까지 구할 수 있습니다. 이들은 곧 3, 4, 5번째 피보나치 수입니다.
마지막에 dp[5]를 반환하면서 계산을 마칩니다.

피보나치 수열에서의 상향식 방법론은 5번째 피보나치 수를 구하기 위해 0부터 4번째 피보나치 수를 차례대로 계산했습니다.

상향식 방법론은 데이터를 테이블 형태로 만들면서 문제를 풀이한다고 하여 타뷸레이션 방식이라고도 합니다.

def fib(n):
    dp=[0]*(n+1)
    if n<=1:
    	return n
    if dp[n]:
    	return dp[n]
    dp[n]=fib(n-1)+fib(n-2)
    return dp[n]

하향식 방법론은 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어나갑니다.

위의 코드를 참고해, 하향식 방법론으로 5번째 피보나치 수 구하는 방식을 자세히 설명하겠습니다.

5번째 피보나치 수, fib(5)를 구하기 위해 0으로 구성된 크기 6의 리스트 [0,0,0,0,0,0]를 생성합니다.
이후 dp[5]=fib(4)+fib(3)을 연산해 dp[5]를 반환하면, fib(5)를 구할 수 있습니다.
fib(4)를 구하기 위해 dp[4]=fib(3)+fib(2)를 연산하고 dp[4]를 반환합니다.
fib(3)을 구하기 위해 dp[3]=fib(2)+fib(1)을 연산하고 dp[3]을 반환합니다.
이를 통해 dp[5]=fib(4)+fib(3)을 연산할 수 있습니다.
3,4 과정을 반복하면 fib(0), fib(1)을 연산해야 하는 순간이 올 것입니다.
여기서 fib(0), fib(1)은 0, 1번째 피보나치 수로 각각 0과 1 값입니다.
3,4 과정을 반복하면 fib(0)~fib(5)를 구할 수 있습니다.
하지만 dp[4]=fib(3)+fib(2), dp[5]=fib(4)+fib(3)과 같이 fib(3)이 두 번 연산되는 경우가 생깁니다.
이런 불필요한 계산을 방지하고자, fib(3)을 계산할 때, dp[3]이 존재하면 dp[3]을 반환하기로 했습니다.
이렇게 계산을 한다면, dp[3]=fib(2)+fib(1)을 두 번 하지 않아도 됩니다.
결과적으로 5번째 피보나치 수인 fib(5)가 연산됩니다.

피보나치 수열에서의 하향식 방법론은 5번째 피보나치 수를 구하기 위해 4번째부터 0번째 피보나치 수를 차례대로 계산했습니다.

하향식 방법론은 기존 재귀 풀이와 거의 동일하면서도 이미 풀어봤는지 확인하여 재활용하는 효율적인 방식으로, 메모이제이션 방식이라고도 합니다.