728x90 탐욕알고리즘1 [Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 탐욕(Greedy) 알고리즘 최적해를 구하는 데 사용되는 근시안적 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택하여 최종 해답에 도달 ex) 거스름 돈의 지폐/동전 개수 최소화 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없음 탐욕 알고리즘 동작 과정 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지 확인, 문제의 제약 조건을 위반하지 않는지 검사 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지 확인 해 검사 : 아직 전체 문제의 해가 완성되.. 2021. 8. 22. 이전 1 다음 728x90