항해99 TIL-12

풀이 문제: 백준 2156 (포도주 시식)

알고리즘: DP

후기:

1. DP 처음이었다

Dynamic Programming (DP)

말로만 듣던 DP를 만났다

첫인상: 읽어도 읽어도 이렇게 이해가 안 된 알고리즘은 처음이다..

많은 글들에서 얘기하고 있어서 기억에 나는 키워드들 정리

• DP: 복잡한 문제를 작은 문제로 나눠서 푸는 방법
• 피보나치 수열이 대표적인 예시임
• 이미 계산한 값들을 저장해두어, 연산을 줄임 (효율적)
• DP의 2가지 유형
  1. Top-down (재귀 + 메모이제이션)
  2. Bottom-up (반복문 + 테이블)
• 핵심 개념 2가지
  1. Overlapping Subproblems
     • 동일한 작은 문제가 반복적으로 등장함
     • 계산한 결과를 저장해두고 다시 쓰면 효율적임
  2. Optimal Substructure
     • 전체 문제의 최적해가 부분 문제의 최적해를 이용해 구성됨