목록근사알고리즘 (1)
On the journey of
[알고리즘] Greedy Algorithm[그리디; 탐욕법]
탐욕법(탐욕 알고리즘)이란 건 기본적으로 최적해를 구하는 데에 사용되는 근사적인 방법이다. 여러 경우 중 하나를 결정해야 할 때마다(=선택의 기로에 설 때마다) 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 방식인데, 지역적으로는 최적일지 몰라도 전역적으로는 최적이라는 보장이 없는 게 일반적인 상황이다. 때문에 탐욕 알고리즘은 지역적으로 최적이면서 전역적으로도 최적인 문제들이어야 사용 가능하다. 이런 알고리즘이 가지고 있앞어야 하는 전제는, 각 선택이 다음 선택에는 전혀 무관한 값(all 독립)이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미로 해석할 수 있다. 이를 조건으로 바꾸게 되면, 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영..
코딩테스트/Python
2023. 9. 15. 08:16