목록Greedy (1)

KKanging

[알고리즘] greedy 알고리즘 (탐욕 알고리즘)

greedy 알고리즘이란 매 선택의 순간마다 순간 (local)에 최적인 답을 선택하여 전체 최적해를 구할거라고 기대를 하는 알고리즘이다 순간마다의 최적이라고, 그 순간들을 수집한 최종적인 해답이 최적해를 보장하지는 않는다 (하지만 최적해를 보장하는 예는 계산 속도가 엄청 빠르다) -greedy 알고리즘을 적용하기 좋은 조건 → greedy 알고리즘은 항상 최적해를 보장하지는 않지만 최적해를 보장하는 2가지 조건이 있다 탐욕적 선택 속성: 앞의 최적해 선택이 이후의 최적해 선택에 영향을 주지않는다.즉, 탐욕적 선택으로 전체 문제의 최적해를 반드시 구할 수 있다는 것을 보여야 한다. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. -greedy 알고리..
cs/알고리즘 2023. 8. 6. 00:43
이전 Prev 1 Next 다음