코딩이 모래?

Greedy 알고리즘 : 목적을 달성하기 위해 현재의 정보만으로 각 단계에서 가장 좋은 선택을 반복해서 답을 구성하는 방법 탐욕 선택 속성 최적 부분 구조 위의 특성을 가지는 문제들을 해결하는데 강점이 있음 즉, 한 번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 수간의 최적해가 문제에 대한 최적해여야 한다는 의미 예시 1️⃣ : 최소 개수의 동전 Q. 1원, 10원, 50원, 100원 동전이 있을 때, 최소 개수의 동전으로 371원을 거슬러 주고 싶다. 어떤 동전들을 몇 개씩 사용해야 할까? 이 질문의 답으로 우리는 100 * 3 + 50 * 1 + 10 * 2 + 1 * 1 = 371 위와 같은 계산으로 3 + 1 + 2 + 1 = 7 개의 동전들로 최소 개수가 이루어짐을 알았을 것이다. 이..

알고리즘 2022. 7. 1. 20:12