다이나믹 프로그래밍 DP 알고리즘 파이썬 코딩테스트 (11)

 

 

 

목차

 

 

서론

지난 포스팅에서는 그리디 Greedy 문제인 로프 문제를 포스팅했다. 풀긴 풀었지만 고전했기에 아쉬웠던 문제였다. 아무튼 오늘은 DP 문제를 풀어보고자 한다. DP는 다이나믹 프로그래밍의 약자로 풀네임은 Dynamic Programming이요 한국어로는 동적 프로그래밍이다. 참고한 관련 강의는 여기로 가면 되고, 내 코딩테스트 일정을 보려면 여기로 가면 된다. 딴말이지만 포스팅이 늘어가면서 뭔가 링크도 점점 많아지는 느낌이다. 기분탓인가??

 

---

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

다이나믹 프로그래밍(DP)의 정의는 여러개의 하위 문제를 먼저 풀고, 그 결과를 쌓아 올려 문제를 해결하는 알고리즘이다. 쉽게말하면 점화식을 사용하면 된다. 이전 재귀 개념을 할 때의 피보나치 개념을 들어보자. 단순 재귀로하면 숫자가 커질수록 계산식이 엄청 늘어난다. 각 항마다 새로 계산하기 때문에 그 가지수가 어마무시해지는 것이다. 하지만 DP를 이용한다면 아래 사진과 같이 미리 배열에 계산 결과(=중간 계산)를 넣음으로써 불필요한 계산 문제로 인한 시간 문제를 해결할 수 있다. 과정은 크게 세가지로, 1. 테이블 정의 2. 점화식 찾기 3. 초기값 정하기로 이루어져 있다. 코딩테스트 수준에서는 점화식만 찾고 이후에 초기값만 구하면 반복문으로 해결이 된다고 한다. 

 

---

 

끝으로

 하지만 점화식을 이끄는 과정이 어렵기에, 쉬운 문제를 많이 다뤄보며 익숙해지는 것이 우선이다. 그렇기에 이후 포스팅에서는 다양한 문제를 풀어보겠다. 풀 문제 리스트는 다음과 같다. BOJ1463, BOJ9095, BOJ2579, BOJ1149, BOJ11726, BOJ11659, BOJ12852. 강의에 나와있는건 이건데 내가 어디까지 풀 수 있을지는 모르겠으나 아마 다 풀지 않을까 싶다. 아무튼 다음 포스팅에서는 BOJ1463에 대해서 풀어보도록 하겠습니다.