Greedy(탐욕) 알고리즘

하나의 문제를 단 한번만 풀도록 하는 알고리즘

최적의 상황을 찾아 해답을 얻는 방법입니다(근사 알고리즘)

1. 선택 절차: 현재 상태에서의 최적의 해답을 선택합니다
2. 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사합니다
3. 해답 검사: 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다

탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 합니다.

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.

완전탐색

DP 동적 계획법

Dynamic Programming 은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식입니다

Dynamic Programming의 원리

주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식

계산한값을 메모이제이션해서 저장한 뒤 필요할때 꺼내쓴다