개발하는데 다 이유가 있겠지

다이나믹 프로그래밍(DP : Dynamic Programming)

동적 계획법

목적

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장
• 한 번 해결한 문제는 다시 해결하지 않음
• 메모리를 사용해서 중복 연산을 줄임
  • 배열 or 자료구조를 만듬
• 중복 연산을 줄여서 수행 속도를 개선
  • 연산한 결과를 배열에 담음
  • 기억하며 풀기(기억하기 알고리즘)

판단 기준

1. 최적 부분 구조(Optimal Substructure)
   • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음
2. 중복되는 부분 문제(Overlapping Substructure)
   • 동일한 작은 문제를 반복적으로 해결

방식

1. 탑 다운(Top-Down) : 하향식 -> 재귀로 구현
   • 메모이제이션(Memoization) : 한 번 계산한 결과를 메모리 공간에 메모하는 기법
   • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
   • 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함
2. 바텀 업(Bottom-Up) : 상향식 -> 반복문
   • 결과 저장용 리스트를 DP 테이블이라고 부름

시간 복잡도

• O(2^n)

---

그리디 알고리즘(Greedy Algorithm)

미래를 고려하지 않고 현재 시점에서 가장 좋은 선택을 하는 알고리즘
현재 내릴수 있는 최선의 선택에만 집중

특징

• 현재의 최적 해 != 전체의 최적 해 (보장되지 않음)
• 100% 최적 해를 고려하지 않는 경우에 사용

조건

1. 현재의 선택이 미래의 선택에 영향을 주지 않음
2. 부분의 최적 해가 모이면 전체의 최적 해가 됨

전략

1. 최적 부분 구조(Optimal Substructure)
   • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음

예제 문제

---

Knapsack Problem(배낭 문제)

n개의 물건과 배낭이 있을 때, 각 물건에는 가치와 무게가 존재
각 물건은 1개씩만 있고, 배낭에는 담을 수 있는 최대 용량이 존재
이러한 조건에서 배낭의 최대 용량을 초과하지 않으면서 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제

종류

Fraction Knapsack Problem : 물건을 쪼갤 수 있는 문제
0-1 Knapsack Problem : 물건을 쪼갤 수 없는 문제

점화식

# n = 개수 / w = 무게 / val = 가치
NS(n, w) = max(
                NS(n-1,w-w[n])+val[n],  # n번째가 가방에 있는 경우
                NS(n-1,w)                # n번째가 가방에 없는 경우
                )