[C++] ICPC 25W 9회차 - dp

dynamic programming

: 큰 문제를 부분문제로 쪼개어 푸는데, 여러 번 나오는 부분문제를 기억해서 최적화하는 기법

 

• 메모이제이션

• 피보나치 수열: 단지 이미 계산한 값을 들고있는 것으로 호출의 양을 엄청나게 줄이는 것을 알 수 있다.
• dp - 메모이제이션 : 여러 번 나오는 부분 문제를 기억한다.
  • 사용법
    1. 값을 저장해둘 테이블 만들기
    2. 테이블을 식별할 수 있는 값으로 초기화해두기;
    3. 내가 지금 풀어야 하는 문제의 답이 테이블에 존재하면 사용하기
• dp - 분할정복 : 문제를 바로 해결 가능하면 해결함. 지금 바로 해결 불가하면 문제를 잘게 쪼갠 후 조립
  • 문제 정의
    1. 부분문제 정의
    2. 내가 정의한 부분문제로 주어진 문제를 해결 가능한지 보이기
    3. 내가 정의한 부분문제를 해결 가능한지 보이기