CS 정리/알고리즘, 자료구조

JAVA DP(동적 계획법)

문쿼리 2025. 5. 6. 22:07

DP는 큰 문제를 작은 문제로 나누고, 그 작은 문제의 해답을 재사용하여 전체 문제를 푸는 방식

비효율적인 중복 계산을 줄일때 효율적임

비슷한 계산을 반복할 것 같을 때 의심하고 적용해보는 전략

 

1. 경로 수 "몇 가지 방법?"
ex) 타일링, 계단 오르기

2. 최댓값/최솟값 "최대 이득/점수?"
ex) 배낭, 땅따먹기

3. 조합 최적화 "어떻게 조합해야 최선?"
ex) 숫자 변환, 동전 교환

4. 부분 문제 반복 "부분 계산 중복"
ex) 피보나치, 문자열 비교

 

점화식
dp[n]=dp[n−1]+dp[n−2]

 

문제 풀이

  • 땅따먹기
    https://school.programmers.co.kr/learn/courses/30/lessons/12913
    문제 키포인트
    1) 브루트포스, 그리드 사용하지말자
    2) 테스트 케이스 생각해보고 가능한 동작방식 고민할 것
    3) 동작 방식에서 중복연산이 있다면, 붙잡지 말고 DP로 넘어가자 (기억 연산법)
  • 높이뛰기
    https://school.programmers.co.kr/learn/courses/30/lessons/12914
    문제 키포인트
    1) 테스트 케이스 생각은 했으나 동작방식 고민해도 답이 안나온다
    2) 피보나치 수열 외우자 그냥 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 처럼 앞자리 더하는 수열!
    3) f(n) = f(n-1) + f(n-2)
  • N으로 표현
    https://school.programmers.co.kr/learn/courses/30/lessons/42895
    문제 키포인트
    1) 테스트 케이스 생각은 했으나 동작방식 고민해도 답이 안나온다22
    2) 사칙연산의 누적해를 set으로 담아서 contains한다
    3) 누적해는 3중 for문을 쓸것 땅따먹기에서 유사한 중첩연산이 있음