[Algorithm/Greedy] About 그리디 알고리즘

그리디 알고리즘(greedy algorithm)이란?

• 알고리즘 설계 패러다임 중 하나로, 매 단계에서 '가장 좋아 보이는' 해답을 선택하는 알고리즘이다.
• 매 단계마다 전체적으로 최적인지는 판단하지 않고 현재 최적이라고 판단되는 결정을 함. 즉 과거(이전 선택)나 미래(앞으로의 선택)는 생각하지 않고, 오직 현재의 최대 만족만을 추구. (근시안적 선택)
• 그리디 방법은 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식이다.

 

 

Example) 지도

 

지도 서비스에서 두 지점의 최단 이동 경로 기능을 제공한다

이 때, 출발 지점에서 아직 방문하지 않은 가장 가까운 지점까지의 경로를 찾고, 이를 목적 지점에 다다를 때 까지 반복하여 경로를 구한다.

(다익스트라 알고리즘의 기본 개념)

 

• 그리디 접근 방식은 너무 단순하기 때문에 몇몇 알고리즘 문제에만 적용할 수 있다.
  • 그러나 이런 단순함은 문제 해결을 위한 첫 걸음이 될 수 있다.
  • 이를 통해 주어진 문제의 속성과 행동을 이해하고, 이후 다른 복잡한 방법을 이용해 문제를 해결할 수 있다.

그리디 알고리즘은 언제 적용할 수 있나요?

• 최적 부분 구조 속성과 그리디 선택 속성을 모두 만족해야 그리디 방법으로 최적의 솔루션을 구할 수 있다.
  • 최적 부분 구조(optimal substructure) : 주어진 문제 P에 대한 최적의 솔루션이 P의 부분 문제들의 최적의 솔루션으로 구성될 경우, 문제 P가 최적의 부분 구조를 갖는다고 말한다
    • 문제의 최적해가 부분제들의 최적해로부터 효율적으로 생성됨을 의미함
  • 그리디 선택 (greedy choice) : 주어진 문제 p에 대한 지역적 최적 솔루션을 반복적으로 선택하여 전체 최적 솔루션을 구할 수 있는 경우 문제 P가 그리디 선택 속성을 갖는다고 말한다.
    • 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것을 의미
• 위 속성을 확인할 수 있는 좋은 예시로는 크루스칼 최소 신장 트리 알고리즘이 있다.(다다음? 게시글에서 다룰 예정)

Ref) 코딩 테스트를 위한 자료 구조와 알고리즘 with C++

Ref) 알기 쉬운 알고리즘