[C++] 다이나믹 프로그래밍(Dynamic Programming)

안녕하세요! 테크지니어22입니다.

오늘은 다이나믹 프로그래밍에 대해서 알아보도록 하겠습니다.

 

다이나믹 프로그래밍(DP)이란?

- 여러 하위 문제들로 풀고 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

- 일반적으로 시간복잡도는 O(n^2) or O(n x m)형태로 나타남.

 

언제 자주 사용되는가? 

- 최적화문제(최대,최소) -> n이 커서 백트래킹이나, 완전탐색 등으로 구할 수 없는 경우 유용

- 중복되는 부분 문제

 

어떻게 사용하는가?

1. 전체 문제를 하위 문제로 쪼개고 이를 이용하여 전체 문제로 해결가능한 지 파악하기
2. 테이블 정의하기
   1. 1차원으로 최대한 정의를 해보기
      (관점을 달리하기 혹은 비틀어보기)
   2. 어렵거나 추가 정보가 요구되면 2차원 정의 해보기
3. 점화식 찾기
4. 초기값 설정하기
5. DP 배열 채우기
   1. 탑다운 방식->재귀 사용
   2. 바텀업 ->반복문

 

꿀팁

- 다른 알고리즘으로 도저히 안되고, 시간복잡도 해결도 어렵다면 하위문제로 나눠보기

- 하위문제가 보통 선택지로 나눌 수 있음. 이 선택지는 한정되어 있음. 보통 2~3개 선택지

- 테이블 정의는 본인에게 유리하게 정의할 수 있음 -> 유연함이 필요.

- 공통적으로 dp[i]를 i일까지 최대수익이라는 정의보다는 i일 원소를 포함하는 i일까지 최대수익처럼 기준을 더 상세히 정의하는게 더 유리 

 

참고문제

- https://techgineer22.tistory.com/11

[백준/C++] 알고리즘 1003번 - 피보나치 함수

 

- https://techgineer22.tistory.com/12 

[백준/C++] 알고리즘 1932번 - 정수 삼각형

- https://techgineer22.tistory.com/13

[백준/C++] 알고리즘 11727번 - 2×n 타일링 2

- https://techgineer22.tistory.com/14

[백준/C++] 알고리즘 2193번 - 이친수

- https://techgineer22.tistory.com/16

[백준/C++] 알고리즘 1912번 - 연속합

- https://techgineer22.tistory.com/17

[백준/C++] 알고리즘 11055번 - 가장 큰 증가하는 부분 수열

- https://techgineer22.tistory.com/18

[백준/C++] 알고리즘 11053번 - 가장 긴 증가하는 부분 수열

- https://techgineer22.tistory.com/20

[백준/C++] 알고리즘 9146번 - 파도반 수열

- https://techgineer22.tistory.com/21

[백준/C++] 알고리즘 10844번 - 쉬운 계단 수

- https://techgineer22.tistory.com/22

[백준/C++] 알고리즘 14501번 - 퇴사1