Python 56 - 그리디 유형 정리 ( 알고리즘 )

그리디 알고리즘이란 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘입니다. 현재 상황에서 가장 좋아 보이는 것만 선택하기 때문에, 정확한 답을 도출하지 못하더라도 그럴싸한 답을 도축하는 데에 도움이 됩니다. 하지만 코딩테스트에서는 대부분 '최적의 해' 를 찾는 문제가 출제되기 때문에 그리디 알고리즘의 정당성을 고민하면서 문제 해결방안을 떠올려야 합니다. 그리디 유형의 문제 특징은 다양한 알고리즘에서 두루 사용되고 있다는 점인데, 예를 들어 뒤에서 배울 다익스트라 최단경로 알고리즘 과 크루스칼 알고리즘은 모두 그리디 알고리즘에 속합니다. 반면 그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아닙니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해' 를 찾을 수 없을 가능성이..

2021.06.17