1. DP 온라인 강의

DP를 풀기 위한 스탭들을 정리해보려 한다.

우리가 문제를 풀 때는 DP인걸 모를 수 밖에 없다.
자연스러운 사고과정은 완전 탐색으로 접근해보는 것이다. 완전 탐색으로 문제를 풀다가 이거.. 계산할게 너무 많은데..? 라는 생각이 들면 DP를 한 번 떠올려보자. DP로 풀기로 했다면 다음과 같은 과정들을 통해 문제를 풀어보자.

1. 가짜 문제를 정의한다.

점화식을 만드는 과정인데 일단 문제에서 원하는 답으로 dp 테이블을 정의해보자.
ex) dp[i] = i번째 블럭에서 나올 수 있는 경우의 수

2. 정의한 가짜 문제로 정답을 알아낼 수 있는지 확인한다.

dp 테이블로 원하는 정답을 알아낼 수 있다면 다음 스탭으로 넘어가자

3. 테이블 초기화 데이터를 고려하자

dp[1] 과 같은 초기 데이터를 어떤것으로 초기화 할 수 있을지 생각해본다. 아주 작은 케이스이기 때문에 쉽게 떠올릴 수 있을 것이다.

4. 특정 케이스로 파티션을 나눈다.

특정 케이스에서 나올 수 있는 경우의 수를 조사한 후 특정 규칙에 따라 파티션을 한다. 이후 관찰하며 점화식을 뽑아보자.

1, 2, 3, 4번 스탭동안 이상한 점이 생긴다면 가짜 문제 정의를 잘못한 것이므로 1번으로 다시 돌아가서 생각해보자.

5. 만든 점화식으로 코드를 작성한다.

2. 카카오 자기소개서

나름 AI 냄새를 빼려고 노력하였다. 자기소개서 쓰는 것은 항상 힘들구나..ㅠㅠ