jun-wiki

View My GitHub Profile

Posts (Latest 10 updated) :
Read all
Contents:
  1. 다이나믹 프로그래밍
    1. 🔷 핵심 개념
      1. 🔹 중복되는 하위 문제 (Overlapping Subproblems)
      2. 🔹 최적 부분 구조 (Optimal Substructure)
      3. 🔹 하위 문제의 결과 저장 (Memoization / Tabulation)

다이나믹 프로그래밍

복잡한 문제를 작은 하위 문제로 나누고,

그 결과를 재사용해 문제 해결하는 기법이다

최적화 이론의 한 기술

🔷 핵심 개념

🔹 중복되는 하위 문제 (Overlapping Subproblems)

  • 큰 문제를 풀기 위해 같은 하위 문제를 반복해서 계산하게 되는 구조

  • 이 중복 계산을 피하기 위해 결과를 저장(메모이제이션)

🔹 최적 부분 구조 (Optimal Substructure)

  • 전체 문제의 최적해부분 문제들의 최적해로 구성

  • 작은 문제를 잘 풀면 큰 문제도 최적의 해

🔹 하위 문제의 결과 저장 (Memoization / Tabulation)

  • 하위 문제의 계산 결과를 저장해두고 다시 사용할 수 있어야 한다.

    • 메모이제이션: 필요할 때 계산하고 저장 (Top-Down)

    • 테이블 기반: 미리 계산해서 저장 (Bottom-Up)