나름 긴 역사를 가진.. 포비아가 있다..
그건 바로 DP-포비아✨✨ (두둥.
그런 의미에서 다시 정리해보는 DP의 개념과 실전 문제 적용 !
이코테 DP를 학습하며 정리한 내용입니다.
Dynamic Programming, DP
"동적 계획법의 고안자인 벨만(Richard E. Bellman, 벨만-포드 알고리즘의 그 벨만 맞다.) 은 dynamic 이라는 단어가 멋있어서 이름으로 선택했다고 한다." - 출처 나무위키
네이밍 자체엔 별로 큰 의미가 없다. 있어 보이는 단어 선정한 게 왠지 웃기고 공감되서 가져왔다 (ㅋㅋ)
핵심은 ?
메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방식이다.
이미 계산된 결과는 별도의 메모리 영역에 저장하여 재활용한다. (= 캐싱)
이때 나오는 중요한 개념이 메모이제이션이다.
한번 계산한 결과는 메모리 공간에 메모해둔다는 말이다. 파이썬에서는 리스트를 활용해 기록할 수 있다.
DP로 해결하기 위한 조건 두 가지가 있다
1) 최적 부분 구조(optimal substructure)를 만족하는가 ?
=> 큰 문제를 작은 문제로 나눌 수 있다
2) 중복되는 부분 문제 해결할 수 있는가 ?
=> 동일한 작은 문제를 반복적으로 해결할 수 있다예시로 유명한 피보나치 수열을 들 수 있다.
피보나치 수열의 점화식은 fib(n) = fib(n-1) + fib(n-2)다.
큰 문제 fib(n)을 해결하기 위해 작은 문제인 fib(n-1), fib(n-2)를 활용한다.
그렇다면 중복되는 부분 문제는 뭘 의미하는걸까? 코드를 통해 알아보자.
피보나치 문제를 풀기 위해서 다양한 접근 방식이 있다. 그 중 하나는 재귀를 활용하는 것이다.
def fibo(x):
if x == 1 or x == 2: # 종료 조건
return 1
return fibo(x - 1) + fibo(x - 2)fibo(6)을 수행했을 때 호출되는 함수를 찍어보자. (직접 트리 그려서 함수 호출 순서를 따라가보면 좋다.)
잘 보면 fibo(2)는 무려 5번이나 호출된 게 보인다. 동적 계획법은 바로 이런 비효율적인 문제를 캐싱을 통해 해결해준다.
fibo(6)
fibo(5)
fibo(4)
fibo(3)
fibo(2) -> 1
fibo(1)
fibo(2) -> 2
fibo(3)
fibo(2) -> 3
fibo(1)
fibo(4)
fibo(3)
fibo(2) -> 4
fibo(1)
fibo(2) -> 5- DP를 활용한 피보나치 수열 (탑다운 방식)
# 한 번 계산된 결과를 저장한 dp 테이블
dp = [0] * 100
def fibo(x):
# 종료 조건
if x == 1 or x == 2:
return 1
if dp[x] != 0: # 이미 계산한 적 있는 문제
return dp[x]
dp[x] = fibo(x - 1) + fibo(x - 2) # 아직 계산하지 않은 문제
return dp[x]이때 함수 호출 스택을 따라가보자.
fibo(6) -> 처음 처리, fibo(5) 호출
fibo(5) -> 처음 처리, fibo(4) 호출
fibo(4) -> 처음 처리, fibo(3) 호출
fibo(3) -> 처음 처리, fibo(2) 호출
fibo(2) -> 1 반환
fibo(1) -> 1 반환
fibo(2) -> 1 반환
fibo(3) -> dp[3] 저장, 반환
fibo(4) -> dp[4] 저장, 반환메모이제이션을 활용하여 "중복되는 부분 문제"가 처리했기에 앞서 다룬 재귀 호출과 비해 많이 줄어들었다. 그렇다면 DP는 얼마나 시간 효율적으로 수행될까?
재귀 vs. DP 시간 복잡도 비교
재귀 호출을 활용하여 N의 피보나치 수를 구하는 경우, 각 노드별 두배씩 늘어나므로 지수 시간 복잡도를 가지게 된다. (참고로 지수 시간복잡도는 팩토리얼 시간과 함께 최악의 시간 복잡도에 꼽힌다.)
N이 100이면?
1,267,650,600,228,229,401,496,703,205,376
.. 이런 본 적도 없는 광공같은 수가 나온다. 아니, 나온다고 한다. 2의 100승이 뭔지 검색했다.
반면 DP는 한번 계산한 경우 더 깊게 들어가지 않으므로, 선형적으로 비례하는 시간 복잡도를 가진다. -> O(N)
1,267,650,600,228,229,401,496,703,205,376
vs.
100
..
🎇 효과는 굉장했다 ! 🎇
실전편
문제 풀 때의 사고 흐름은 어떻게 가져가는가?
초심자가 문제를 보자마자 '....DP다!'라고 떠올리진 않을테니, 어떤 흐름으로 접근하는 게 좋을지 살펴보자.
1) 그리디, 완전 탐색으로 풀 순 없는가?
가장 단순무식한 방법을 먼저 떠올려보자.
그리디/완전탐색/백트래킹을 활용할 수 있다고 하면, 이때의 시간복잡도가 어떻게 되는지 살펴볼 필요가 있다.
입력 조건을 고려했을 때 시간 제한에 맞게 해결할 수 없다면, 다른 대안(DP)를 한번 생각해보자.
2) 큰 문제를 작은 문제로 나누어볼 수 있을까?
이 경우, DP로 접근해볼 수 있다.
그렇다면 큰 문제와 작은 문제를 분리하여 점화식을 한번 세워보자
EX_개미전사
N개의 정해진 수의 식량 저장 창고가 있을 때, 최대한 많은 식량을 훔쳐야 한다. 다만, 최소 한칸 이상 떨어진 식량 창고여야 한다. (N은 100까지)
입력 :
- N = 4,
- [1, 3, 1, 5]
출력 :
- 8 (3, 5를 취한다)그리디, 완전탐색으로는 안되는가 ?
-
현재 취할 수 있는 가장 큰 식량을 우선적으로 취한다고 하면 ?
1 -> X -> 1 -> X => 2 (X)
안되겠다.
-
그렇다면 모든 경우의 수를 다 따져보는 건?
[X, X, X, X] [1, X, X, X] [1, X, 1, X] [1, X, X, 5]등등..
근접한 위치를 선정하지 못한다는 조건이 있더라도, 지수 시간 복잡도에 가까운 경우의 수를 보인다.
DP의 조건을 만족하는가 ?
즉, 최적 부분 구조를 가지는지(큰 문제를 작은 문제로 나누어볼 수 있는지) 봐야한다.
ㄴ 이걸.. 어떻게 알죠 ?!?
"해결해야 하는 문제 영역이 무엇인지" 정의할 필요가 있다.
"i번째를 선택했을 때 가장 많은 식량을 모았다는 것"을 문제 영역으로 설정했을 때, 이 문제에서는 큰 문제를 해결하기 위해 보다 작은 영역의 문제을 활용할 수 있다.
dp[i] = i번째 창고까지의 최적해라고 했을 때, 우리는 점화식을 세워볼 수 있다. i번째를 선택한 경우, i-1번째는 선택하지 못한다. 그리고 i-2번째까지의 최적해와 현재껄 선택할 수 있다. 결과적으로 다음과 같은 점화식을 세울 수 있다.
- dp[i] = max(dp[i-2] + a[i], dp[i-1]) (dp[i] = i번째 창고까지의 최적해)코드
def solution(n, store):
dp = [0] * n
dp[0] = store[0]
dp[1] = store[1]
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + store[i])
return dp[n-1]
n = int(input())
store = list(map(int, input().split()))
print(solution(n, store))앞으로 DP 공부는 어떻게 할 것인가 ?
DP는 다른 알고리즘과 다르게 접근 방식만 잘 생각해도 8~90%는 다 끝났다고 봐도 될 듯하다. 앞으로 DP 문제들을 훑으면서 점화식을 떠올리는 훈련을 하면서 자신감을 더 붙여봐야겠다👀
요 백준 DP 시리즈 틈틈이 풀어봅시다..
