[알고리즘] DP에 대하여

이번에는 DP(Dynamic Programing)에 대해 말해보려고 한다. 사전적으로 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 동적 계획법에 대해서는 딱히 내용은 없지만 할 말이 많아서 차근 차근 진행해 보려고 한다. 0. DP란? 위에서 서술한 것 처럼 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 간단하게 예시를 들어보자. 피보나치 수의 100번째 수를 구해야 한다고 해보자. 하지만 P(100)=P(99)+P(98)이기 때문에 우리는 피보나치 수의 100번째 수를 구하는 대신 99번째와 98번째 수를 구하는 것으로 대체할 수 있다. 이런 식으로 더 부분 문제에 대한 답을 구해 놓아 이를 통해 더 큰 문제의 답을 계산 하여 구하는 과정을 반복하여 최종 ..

이번에 다양한 테스트 시즌, 입학 시즌 등등의 이유로 코딩(PS)를 시작하려고 하시는 분들이 꽤나 있을 것 같다. 그러한 분들, 이번 신입생들 등을 위해서 내가 그나마 도움을 줄 수 있는 부분인 DP에 대해서 이야기를 풀어나가 보려고 한다. 전체적으로 DP 문제들에 대한 소개, DP 문제란? DP 문제 푸는 법 등에 대해서는 이 글에서 자세히 말을 했었다. 좋은 글이니 DP 공부를 하려면 한 번 읽어보는 것을 추천한다. 이번 글에서는 DP를 공부하는 법/DP를 잘해지려면? 과 같은 주제에 대해서 다뤄보려고 한다. 0. DP란? DP 문제를 푸는 법 위에서도 언급을 했지만 이 글에서 상당부분 잘 말해주고 있으니 참고하면 될 것 같다. 1. DP 문제의 특징 1.1 아이디어 & 생각 > 구현 일정 수준까지는..

완벽하다고 이야기하지는 못하겠지만, 거의 DP 원툴로 해온 사람으로서 그래도 나름 좋은 문제들이라고 생각한다. DP에 대한 기본 지식은 이전글에 나름 자세히 나와있다. DP 문제를 공부하는 법은 이 글에 나와있다. 문제 소개는 간단히 하고 스포는 최대한 안하려고 노력했다. 배치는 대충 난이도 순이다. DP를 처음 하신다고요? DP라는 것을 처음 접해보는 사람들을 위한 입문자용 문제 모음 - BOJ 2748 피보나치 수 2 유명하기 때문에 감을 잡기 쉽다. - BOJ 1463 1로 만들기 DP 태그의 첫 문제 - BOJ 9095 123 더하기 123 더하기 시리즈는 많고 대부분 나쁘지 않다! - BOJ 2579 계단 오르기 조금 비 직관적인 형태에서 DP식을 끄집어 내보자! - BOJ 11276 2xn 타..