DP를 공부하는법 & DP 문제 팁

이번에 다양한 테스트 시즌, 입학 시즌 등등의 이유로 코딩(PS)를 시작하려고 하시는 분들이 꽤나 있을 것 같다. 그러한 분들, 이번 신입생들 등을 위해서 내가 그나마 도움을 줄 수 있는 부분인 DP에 대해서 이야기를 풀어나가 보려고 한다.

전체적으로 DP 문제들에 대한 소개, DP 문제란? DP 문제 푸는 법 등에 대해서는 이 글에서 자세히 말을 했었다. 좋은 글이니 DP 공부를 하려면 한 번 읽어보는 것을 추천한다. 이번 글에서는 DP를 공부하는 법/DP를 잘해지려면? 과 같은 주제에 대해서 다뤄보려고 한다.

0. DP란? DP 문제를 푸는 법

위에서도 언급을 했지만 이 글에서 상당부분 잘 말해주고 있으니 참고하면 될 것 같다.

1. DP 문제의 특징

1.1 아이디어 & 생각 > 구현
일정 수준까지는 '아이디어가 90% 이상이다'라고 말할 정도로 구현난이도가 다른 문제에 비해 월등히 쉽고, DP식을 잘세우기만 하면 된다.

1.2 DP 문제인지 알아채기
DP에 대한 감을 익혔다면, 어느 레벨의 DP 문제까지는 그 문제를 DP로 풀어야겠다는 감이 굉장히 빠르게 들것이다.

2. 그럼 어떻게 공부하나요?

2.1 DP가 무엇인지 확실히 알기

DP는 정말 뻗어나가기 쉽고, 문제도 다양하고, 굉장히 특이하며, 사용방법이 많다.
그만큼 DP는 DP가 무엇인지, 어떤식으로 해결해야하는지 확실히 깨달으며 시작해야 한다고 생각한다.
여기서 2*n 타일링, 1,2,3 더하기, 1로 만들기 등을 머리 싸매고 고민을 해보자.
정말 오래 고민하고 안되겠으면 풀이를 보자.
풀이를 정말 자세히, 꼼꼼히 보면서 감탄을 해보자.

적어도 나는 와!! 이걸 이렇게 풀 수가 있구나! 이것이 DP구나! 라는 생각을 했었다.
이것이 DP에 빠지게 되는 계기이며, DP의 세계로 내딛는 첫걸음이 될것이다.

2.2 다양한 형태 경험해보기

위에서 말했던 것처럼 DP식을 세우는 방법은 정말 다양하다. 
물론 처음 보는 유형을 언젠간 풀어야 하지만, 시험이나 대회에서 세울 DP식이 경험해 본 형태인것과 아닌것은 엄청난 차이가 있다.
따라서 굉장히 다양한 유형의 DP식을 세워보는 것을 추천한다.
이 글 에서도 좋은 다양한 DP문제를 많이 알려주고 있다.
주위 사람들에게 좋은 문제를 추천해 달라고 하는 법도 있다.

2.3 많이 풀어보기

DP 식을 세우는 능력은 하면 할 수록 늘게 되어있다. 
당연히 많이 접하고 많이 풀면 다양한 형태도 경험해 볼 수 있게 된다. 
추천하는 방식은 백준의 DP문제 모음 페이지에서 쭉 풀거나, solved.ac의 dp태그로 검색해서 쭉 푸는 방식이 있다.
DP는 DP임을 빠르게 알 수 있기 때문에 DP문제라는 것을 알고 시작해도 문제의 효율이 좋다.
대회나 시험에서 언젠간 꼭 쓸때가 있으므로, 꾸준히 많이 푸는 것을 추천한다.

DP문제의 가장 큰 장점은 노트북 앞에 있지 않아도 풀 수 있다는 것이다.
오래 머리를 굴리고 짧게 키보딩을 하는것이 특징이자 장점이다.
만약 정말 좋아하고, 단기간에 실력을 높이고 싶다면 DP문제를 언제나 머릿속에서 고민해보자.
본인도 지하철 타고 다니면서 항상 문제를 고민하면서 실력이 많이 향상되었던 것 같다.

2.4 배워야 한다!

DP는 생각 & 아이디어가 대부분이다.
따라서 풀이를 보는 순간 그 문제를 푸는 가치는 쭉 떨어지게 된다.
하지만 지금까지 고민해온 방향을 떠올리며, 어떤 식으로 생각을 해야하는 지, 이런 형식의 문제는 어떻게 풀어야 하는지에 대한 방향성을 잡을 수도 있다.
DP문제에서 풀이는 보는 것은 굉장히 조심해야 한다.

따라서 내가 문제 풀 때 내 실력을 잘 알고 나를 도와줄 수 있는 사람이 있는 것은 굉장히 큰 도움이 된다!

3. 문제를 푸는 팁들

그래도 많이 풀면서 경험해본 것을 토대로 사소하게 써보려고 한다.

3.1 최종 문제, 목표 기억하기.

결국 작은 문제로 나눠서 풀어내는 이유가 그 결과들을 이용해 최종 문제의 답을 얻기 위해서다. 최종으로 얻어내고자 하는 값을 확실히 하고 의식할 수록 DP식을 세우기 편해 질 것이다.

3.2 상태와 값.

어떤 DP값은 보통 어떤 상태의 어떠한 값을 담아낸다. (1부터 i까지)(나올 수 있는 최대값) 이런식으로 말이다. 두 가지 키워드에 집중을 해보자!! 상태는 문제를 해결해 나가면서 나올수 있는 상태들. 값은 최종 결과 값과 관련있는 값. 보통은 이렇지만 때에 따라 잘 설정해야한다.

3.3 관계

결국 DP 값들이 의미가 있으려면 그 DP 값 사이의 관계식이 잘 서있어야 한다. 확실하게 이미 얻은 값으로 다음 값을 얻는 것이 맞는지, 그 관계를 얼마나 따져야 하기 때문에 시간복잡도가 어떻게 되는지에 집중을 해보자.

DP는 정말 어렵습니다... 꾸준히, 열심히 해야 그만큼 성과를 내기 좋은 문제들이죠. 그래도 착실히 해나가면 확실히 빛을 발하는 곳은 있을것이라고 장담합니다.. 모두 화이팅 하세요!!