다이나믹 프로그래밍이란?

• 동적 계획법
  • 문제를 해결하면서 얻게 되는 중간 결과물을 이용해서 문제를 효과적으로 풀어가는 방법
  • 하나의 문제를 여러개의 작은 문제로 나누고 작은 문제를 해법을 재사용하여서 큰 문제를 효과적으로 푸는 방법을 말한다.
  • 작은 문제 답을 구해서, 큰 문제를 해결한다
    • 작문 문제의 해법을 재사용하여 큰 문제를 효울적으로 해결한다
    • 이미 했던 계산은 반복하지 않는다.
• 동적계획법 적용할 수 있는 문제 유형
  • 문제가 더 작은 문제로 쪼개질 때
  • 작은 문제의 솔류션으로 더 큰 문제의 솔루션을 구할 수 있을때
  • 그리고 이 작은 문제들이 겹쳐서 이를 저장하고 사용하여 계산의 수를 많이 줄일 수 있을 때

피보나치 수열

• 피보나치 수열 : 어떤 수열의 항이 앞의 두항의 합과 같은 수열을 말함

Memoization 방식

• 한 번 계산했던 결과를 메모리 공간에 그록해두었다가 필요할 때 가져와서 쓰자
• 믄 문제에서 하위 문제로 접근해서 하위 문제에 대한 정답을 계산했는지 안했는지 확인해가면서 문제를 푸는 방식
• 답을 재활용하기 때문에 중복 계산을 방지할 수 있는 기법

Tabulation 방식

• 하위 문제의 정답을 이용해 더 큰 문제의 정답을 풀어나가는 방법
• 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식

탐욕(Greedy) 알고리즘

• 최적의 해 또는 근사 해를 구하는데 사용하는 방법
  • 문제를 여러단계로 나누고 각 단계에서 최적의 수를 찾아낸 후 각 단계에서 판단한 최족의 수를 모아 문제의 최종 답을 찾는 알고리즘
• 탐욕 알고리즘
  • 모든 경우의 수를 계산하는 데 시간이 오래 걸리거나 방법이 복잡한 경우 간단한 방법으로 비교적 빠르게 최적의 해/근사 해에 결과를 얻고자할 때 주로 사용
• 모든 경우의 수를 확인하는 방법 : 무차별 대입법, 부르트-포스 방법
  • 시간이 오래걸려도 정답을 확실히 찾을 수 있다.
• 대표적인 예시
  • 외판원 문제 -> 여러 도시를 최소 비용으로 단 한번씩만 방문하는 이동 경로를 찾는 문제
• 탐욕알고리즘 언제 적용?
  • 최적의 해를 계산하는데 시간이 오래걸리는 문제의 경우 탐욕알고리즘 사용하면 적당히 빠르면서 괜찮은 근사해를 찾을 수 있다.
• 탐욕알고리즘, DP -> 문제가 탐욕알고리즘을 적용해야하는건가?
  • 문제 : 경우의 수가 기하급수적으로 늘어나면
• 탐욕 알고리즘으로 찾은 경로는 최적의 경로보다 대략 25% 정도 더 많은 비용이 든다.
  • 탐색 비용은 훨씬 짧게 소요된다.