why
DP.. 너무 못한다..
이쯤 되니깐 수학을 잘했던 것은 순전히 운이 아니었나 싶다.
스트레스도 너무 받고,, 머리도 안굴러가고...
냅다
찾음
다른 분들의 조언을 보기로 했다는 것..
DP
- 간단한 여러 개의 문제로 나누어 푸는 방법
- 어떤 항을 구하기 위한 전 항들을 완벽히 구할 수 있고, 그 항들을 이용해 정의에 맞는 현재 항이 깔끔하게 정의될 때 문제이다.
과정
푸는 과정은 크게 두 가지로 나뉠 수 있다!
아이디어&생각 / 구현
1. 문제 탐색하기
DP 일수록 이해와 관찰
DP식을 잘 세우는 것이 중요한데 그 정당성은 내가 문제에서 관찰한 사실로부터 나온다.
2. DP식 세우기
문제의 특징에 따라
dp[i]=i
dp[i][j]=i~ 등 다양한 방식으로 세울 수 있다.
재능과 경험에 따라 좌우 된다.. (..)
3. 검증 및 구현
DP식이 맞는지, 시간 복잡도는 괜찮은지 검증하기
➡️ 풀이를 보면서 감탄하면서 감 익히기 🤣
➡️ 노트북 앞에 앉아있지 않아도 풀 수 있는 문제. DP를 언제나 머릿속에서 고민해보기..
팁
- 최종 문제, 목표 기억하기
작은 문제로 풀어내는 이유는 최종 답을 얻기 위해서이다. 목표를 확실히 의식하는 것이 DP식을 세우기 편하다. - 상태와 값을 잘 설정하기
상태는 문제를 해결하면서 나올 수 있는 것들
값은 최종 결과 값과 관련있는 값 - 관계식이 잘 서있어야 한다.
시간 복잡도 유의하기
[참고]
터벅터벅 개발(은좋은)자 로그