🔸DP(Dynamic Programing)란?
- 동적 계획법이라고도 불리며, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
- DP는 정해진 구조를 그대로 구현하는 자료구조가 아니라, 수행시간을 단축할 수 있는 기법이다.
직관적으로 DP 알고리즘을 나타낼 때는
- 기억하기 알고리즘
- 기억하며 풀기 알고리즘
으로 기억하는게 좀 더 설명하기 쉽다.
🔸다이나믹 프로그래밍을 왜 사용할까?
- 메모리를 사용해서 중복 연산을 줄이기 위해
- 즉, 또 하나의 배열 또는 자료구조를 만든다는 의미이다.
- 중복 연산을 줄여서 수행 속도를 개선하기 위해
- 연산된 결과를 배열에 담아, 한 번 계산한 연산은 또 하지 않는다.
🔸다이나믹 프로그래밍 구분 방법
- 특정 유형에만 국한되지 않고, 다양한 유형의 문제를 최적화 할 때 고려될 수 있는 알고리즘이다.
- DFS / BFS 로 풀 수 있지만, 경우의 수가 너무 많은 문제
- DFS 로 풀 수 있는 경우의수는 대략 500만개
- 만약 그 이상이면 DP를 사용해야한다.
- 경우의 수들의 중복적인 연산이 많은 문제
- 최적의 값만 남겨놓고, 안 될 조합들은 미리미리 버린다.
🔸문제해결 접근방법
- 최대한 많은 문제를 풀어보고, DP식의 사고방식을 습득 해야한다.
- DP는 30분정도만 생각해보고, 풀이를 참고해서 구현만 해보는 방식을 추천
- 30분 동안은 어떻게 하면 뒤를 돌아가지 않을 수 있을까를 중점으로 고민
- 중복 연산을 하지 않으려면, 어떤 정보를 남겨야하는지
- 어떤 식으로 정보를 누적해야 되는지
DP라는 알고리즘은 큐(Queue)나 스택(Stack)과 같이 정형화된 알고리즘이 아니다. 그래서 DP유형의 문제는 모두가 풀기 어렵기 때문에 꾸준히 많은 문제를 풀어보는게 좋다.
동적 계획법이라고 하며, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
💬 참고문서
초보개발자