7일차 DP 기초 🔥

DP란

DP는 Dynamic Programming의 약자로 동적 프로그래밍이라는 뜻을 가지고 있다.

• 핵심아이디어 : 큰 문제를 작은 문제로 쪼개고, 작은 문제의 해를 저장해서 큰 문제를 푸는 방식
• 핵심 키워드 :
  • 점화식 : “큰 문제 = 작은 문제들의 관계”를 수식으로 표현
  • 저장 : DP 배열에 계산 결과를 저장해서 재활용
  ➡️ DP문제는 부분 문제의 해를 저장하고 점화식으로 표현하여 큰 문제의 답을 찾아가야한다.

1차원 DP의 접근 방식

1. 배열 dp[i]를 정의한다.
2. 작은 문제에서 큰 문제로 확장되는 규칙을 찾음 (실제 해보는 것도 도움)
3. 점화식으로 dp[i]를 dp[i-1], dp[i-2], ... 같은 이전 값으로 표현.
4. dp[1], dp[2] 같은 가장 작은 케이스(초기값)를 손으로 계산

주의할 점 : 배열 크기와 초기값을 0으로 할지 1로 할지 주의해야한다.

그렇지만 dp 는 최대한 많이 풀어보는게 중요한 것 같다 !!

직접 문제 풀어보기

1463 1로 만들기

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : dp배열을 정의하고, 각 단계에서 나올 수 있는 경우의 수를 구해보자
  

9095 1,2,3 더하기

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : dp 배열의 크기 최솟값을 고민했음. 직접 입력해야하는 값들의 크기에 따른 dp 배열의 최소 크기를 고민했다.
  

2579 계단 오르기 ⭐️ 추천

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : dp배열을 정의하고, 각 단계에서 나올 수 있는 경우의 수를 구해보자
  

1520 내리막길

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 힙 + dp 문제
  dp 배열의 값을 순차적으로 업데이트 하는게 아니라 힙을 통해서 빠른 시간내에 최댓값을 찾고 접근하는 문제였다. 또 방문노드도 사용해서 이미 업데이트 한 인덱스는 접근하지 않도록 했다. 다익스트라 알고리즘에서 힙을 사용한 기억이 단서가 됐다.
  

정리하면서

더 많은 문제를 풀어본다면 오늘 내리막길 문제를 푼 것처럼 활용할 단서가 더 늘어날 것이라고 생각한다.
꾸준히 공부하고 싶어지는 하루였다
만족도 100
아주 행복함 !