[알고리즘] 다이나믹 프로그래밍

저희 스터디에서 학습 진도에 관해 제가 발표할 차례가 되어 발표 자료를 다음과 같이 만들었는데

그걸 가지고서 다이나믹 프로그래밍을 정리해보고자 합니다.

 

[피보나치 수열을 통한 개념 설명]

•  효율적인 알고리즘! 이라고 간단히 표현할 수 있겠다.
• 예시)

def fibo(x):
	if x=1 or x=2:
    	return 1
    return fibo(x-1) + fibo(x-2)

 

• fibo(6)을 호출해 봅시다.

 

• 중복되어 사용되는 코드가 보이시나요?

• 바로 이러한 중복된 코드 등을 줄임으로써 코드를 효율적으로 만드는걸 DP이라고 합니다.

---

[다이나믹 프로그래밍]

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답이, 그것을 포함하는 큰 문제에서 구한 작은 문제에 대한 정답과 같다.

 

위 두 조건을 만족할 때 다이나믹 프로그래밍을 적용할 수 있습니다.

 

위의 피보나치 상황에서는 다음의 '메모제이션' 을 통해 해결할 수 있습니다.

if d[x] != 0:
	return d[x]
d[x] = fibo(x-1) + fibo(x-2)
return d[x]

다음과 같이 리스트에 연산한 값을 저장해두면 한번 더 연산할 필요 없이 값을 호출하기만 하면 됩니다.

이걸 기억해두다라고 해서 '메모제이션'이라고도 하고, '캐싱'이라고도 한다.

 

 

위의 두 조건을 보고 퀵정렬을 떠올릴 수도 있다.

그러나 퀵 정렬의 경우에는 이미 푼 문제가 중복되지 않기 때문에 굳이 다이나믹 프로그래밍이 적용될 이유가 없다.

퀵정렬에서는 자리가 정해진 pivot을 더 이상 건드리지 않기 때문에 연산을 중복해서 하지 않는다.

 

• 메모제이션을 활용한 결과

함수 호출이 많이 심플해진 것을 알 수 있다.

---

[탑 다운 방식과 바텀 업 방식] 

 

1. 탑다운 방식

 

• 앞서 설명한 메모제이션이 탑 다운 방식의 한 예이다.
• fibo(6)을 해결하기 위해 fibo(5)와 fibo(4)를 조회하고, 만약 값이 저장되어 있다면 호출하고 저장되어 있지 않다면 다시 낮은 단계의 함수를 호출한다.
• 탑 다운 방식은 하향식 방식 이라고도 말한다.
• 주로 재귀를 통해 구현하기 때문에 재귀의 한계상 호출할 때마다 메모리에 적재되어 오버헤드가 발생할 수도 있는 문제가 있다.

 

2. 바텀 업 방식

 

• 바텀 업 방식이다. fibo(6)을 계산하기 위해 fibo(1), fibo(2), fibo(3) ... 아래 부터 차근차근 답을 도출해나간다.
• 바텀 업 방식은 상향식 방식이라고도 하는데, 이때 계산한 값들을 저장하기 위해 사용하는 테이블을 'DP 테이블'이라고 한다.
• 주로 반복문을 통해 구현한다.

 

---

[그 밖의 설명] 

 

참고한 책 ; 나동빈 (2020). <이것이 취업을 위한 코딩 테스트다 with 파이썬>. 서울시: 한빛미디어.