동적 프로그래밍(Dynamic Programming)

목적

메모리를 사용해 배열 혹은 자료구조를 만들어 연산 결과를 담아 중복 연산을 줄인다.
중복 연산을 줄여서 수행 속도를 줄이는 것이다.
(어떤 교수님은 ‘기억하기 알고리즘’이라고도 한다고 합니다.)

문제를 알아보고 구분하는 방법

• DFS/BFS 로 풀 수 있지만 경우의 수가 너무 많은 경우
• 경우의 수에 중복적인 연산이 많은 경우

문제 해결 접근 방법

최대한 많은 문제들을 풀어보고 풀이들을 참고해 DP(Dynamic Programming)식의 사고방식을 습득해야 합니다.
‘어떻게 하면 뒤로 돌아가지 않을 수 있을까?’
=> ‘연산을 또 하지 않으려면 어떤 정보를 남겨야 할까?’ 를 고민해야 한다.