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

그리디 알고리즘이란 

현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘입니다.

 

현재 상황에서 가장 좋아 보이는 것만 선택하기 때문에, 정확한 답을 도출하지 못하더라도 그럴싸한 답을 도축하는 데에 도움이 됩니다. 하지만 코딩테스트에서는 대부분 '최적의 해' 를 찾는 문제가 출제되기 때문에 그리디 알고리즘의 정당성을 고민하면서 문제 해결방안을 떠올려야 합니다.

 

그리디 유형의 문제 특징은 다양한 알고리즘에서 두루 사용되고 있다는 점인데, 예를 들어 뒤에서 배울 다익스트라 최단경로 알고리즘 과 크루스칼 알고리즘은 모두 그리디 알고리즘에 속합니다.

 

반면 그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아닙니다.

 

대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해' 를 찾을 수 없을 가능성이 다분합니다.

 

하지만 문제에서 '가장 큰 화폐단위부터' 와 같이 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해준다면 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로, 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됩니다. 같이, 탐욕적으로 문제에 접근 했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적입니다.

 

반면, 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야합니다.

 

거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다.

 

대부분의 그리디 알고리즘 문제에서는 이처럼 문제풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있어야 합니다.

 

 

 

아래 게시글 4개는 본인이 기본적인 그리디 유형의 주요 알고리즘이론과 실전문제에 대하여 설명한 것들입니다.

Python 52 - 당장 좋은 것만 선택하는 그리디 ( 알고리즘 )

 

Python 52 - 당장 좋은 것만 선택하는 그리디 ( 알고리즘 )

 

Python 52 - 당장 좋은 것만 선택하는 그리디 ( 알고리즘 )

Python 53 - 큰 수의 법칙( 알고리즘 )

Python 53 - 큰 수의 법칙( 알고리즘 )

Python 54 - 숫자 카드 게임( 알고리즘 )

Python 54 - 숫자 카드 게임( 알고리즘 )

Python 55 - 1이 될 때까지( 알고리즘 )

Python 55 - 1이 될 때까지( 알고리즘 )

 

 

 

 

 

 

 

작성자 : 엄코딩 eomcoding