[개념] 동적 프로그래밍 (동적 계획법)

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

하나의 문제를 작은 다누이로 쪼개어 해결,

결괄르 수집 및 병합하여 최종 결론을 만들어냄 

 

특징
- 한번 계산해서 해결한 것은 다시 해결하지 않기

=> 계산한 데이터를 저장한다. (리스트 등) "메모이제이션"

 

문제 특징

조건

1) 최적 부분 구조 : 큰 문제를 작은 문제를 나누기 
2) 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결 

=> 점화식으로 나타낼 수 있어야! (점화식->재귀함수)

 

문제형태 (키워드)

- 최대 구간의 합, shortedst, longedst, most.. 

 

 

풀이방식

1) top down : 재귀 이용하여 dp 채우기

2) bottom up : 반복(for)로 앞아서 채워 마지막 도출

 

 

문제 예시
- 피보나치 수열

- 배낭에 가치 높은 물건 넣기 (아이템 선택 vs 선택 안함)

 

문제풀이 팁

- dp list를 만든다. (가변수가 2개면 2차원 dp list 생성) // 이름을 dp라고 붙인 그냥 list

- 초기화를 -1로 한다. 

 

- 문제 접근 시,

1) 브루트포스로 푼다

2) 반복되는 작업을 정리한다. 

3) 하위문제로 쪼개어보고, 반복되는 단계 있는지 확인

- 변경되는 변수를 기준으로 최대 가치 기록 

 

- 값 할당 시,

1) 특정 idx 안 가져감 : 하위 배열의 가치 가져감 : dp[idx-1][가변]

2) 특정 idx 가져감 : value[idx] + dp[idx-1][가변-특정idx 가져감으로서 받는 패널티]

 

- 총액 크기만큼 배열 생성 (0 ~ 총액 크기)

- 최소 값을 구하는 문제는 초기 값을 inf로 (ex. float('inf'))

- (댓가를 주고 얻은 값 + 기존 값) 과 기존 값(사실, 이전 연산으로 지금까지 중 가장 최저인) 중 더 작은 값을 선택하는 방식

 

시간복잡도의 변화

O(2^n) -> O(n)

=> 지수승 -> 상수승

 

 

 

참고 

- 쓰면서 익히는  알고리즘과 자료구조

- 나동빈 유투브