🏀 개요
다이나믹 프로그래밍을 공부하고자 한다. 사용 목적과 방식 등을 중점으로 알아볼 예정.
참고 :
동빈나 유튜브 채널을 기반으로 정리한 것으로, 유튜브 링크를 첨부 하겠습니다.
동빈나 유튜브 링크
💡 접근 방식
- 사용 목적
메모리를 사용하여 수행시간을 비약적으로 증가시킬 수 있다.
- 최적 부분 구조 :
큰 문제를 작은 문제로 나누고 그 답을 모아서 해결 가능, 작은 문제의 답을 메모리에 올리는 방식
- 중복 되는 부분 문제:
작은 문제를 해결하는 과정 중 중복 계산이 발생할 수 있다. 이러한 부분을 미리 메모리에 올려서 중복 수행을
방지
- How?
- 탑 다운 방식:
재귀 함수 기반으로 진행 가능, 예를 들어 피보나치의 경우 각 계산의 결과를 메모리에 저장
if d[x] != 0 : return d[x] # 사전에 계산된 부분을 사용하겠다는 것을 의미.- 보텀 업 방식:
대부분의 DP 문제는 보텀 업 방식으로 접근, 먼저 값들을 세팅하고 이를 기반으로 값을 진행.
반복문을 이용해서 사용.
d[1] = 1
d[2] = 1
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]- 참고 사항:
그리디, 구현, 탐색 으로 먼저 접근해보고, 예외 케이스 등 다양한 케이스가 필요할 때 DP를 고려하자.
성능 이슈가 있을 경우 재귀 함수는 탑다운 방식으로 성능 향상이 가능하고, 반복문의 경우 보텀 업 방식으로
성능 향상이 가능하니 이를 고려해서 고민하자.
🔧 예제 문제
DP 테이블 값은 최적화 대상, 문제에서 알고자 하는 목적을 의미한다.
DP 테이블 값을 미리 세팅 -> 각 값의 어떤 경우의 수에서 선택 되었는지 체크 -> 경우의 수 기반으로 점화식 -> 구현
이런 방식으로 접근 가능
단, array 형태로 주면 바로 직관적으로 DP 테이블을 생각할 수 있지만, 특정 값을 주면 DP 테이블을 어떻게 생성할 것인지도 추가적으로 고려해야 한다.
각 계산에 대한 구조를 체계화 하는 것 등 다양한 방식으로 생성할 수 있다.
동빈나의 유튜브에 예제 문제 총 4가지도 이 접근 방식을 연습하는데 좋았다. 이 부분은 유튜브에서 설명이 되어 있기 때문에 추가로 문제를 더 풀 예정이다.
Max Array Sum 문제 바로가기
# Complete the maxSubsetSum function below.
def maxSubsetSum(arr):
dp = [0] * len(arr)
dp[0] = arr[0]
dp[1] = max(dp[0], arr[1])
for i in range(2,len(arr)):
dp[i] = max(dp[i-1], dp[i-2] + arr[i], arr[i], dp[i-2])
return dp[-1]유튜브에 있는 개미 식량창고 문제랑 비슷하게 접근했다.
i번째 입장에서는 dp[i-1], dp[i-2] + arr[i] 2가지의 케이스가 가능한데, 본인 자신이 합한 경우보다 클 경우와 본인 자신이 음수일 경우를 대비해서 arr[i],dp[i-2] 를 추가적으로 고려해줬다.
즉 경우의 수 총 4가지로 선정하고, 그 중 max가 되는 값들을 dp에 추가하여 최종적으로 반복문이 끝났을 때, 인접하지 않는 구성요소로 이루어져 있는 subset 중 최대 합을 구할 수 있다.
Abbreviation 문제 바로가기
