그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘

지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘이다.  

 

지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다. 그래서 모든 경우의 수를 고려하는  완전 탐색이나 동적 계획법 알고리즘과 달리, 그리디 알고리즘은 매 선택이 그 순간에 대해서는 최적 여부만 고려하므로 최종 도출된 해가 최적이 아닐수도 있다.

 

그리디 알고리즘을 사용하면 좋은 경우

최적 부분 구조

문제의 최적해가 부분 문제의 최적해로 구성되는 경우에 그리디 알고리즘이 유용하다.

이런 경우에는 각 단계에서 최적의 선택을 하면 전체 문제의 최적해를 얻을 수 있다.

탐욕 선택 속성

각 단계에서 최적의 선택을 하는 것이 문제 전체에 대한 최적해를 구하는 데 필요한 조건이라면 그리디 알고리즘을 적용할 수 있다.

근사 알고리즘

문제가 NP-완전 등의 어려운 문제일 때, 그리디 알고리즘을 통해 근사적인 최적해를 구할 수 있는 경우가 있다.

 

그리디 알고리즘 시간복잡도

동전 거스름돈 문제 (Coin Change Problem)

가정

동전의 종류: 1원, 5원, 10원, 50원, 100원, 500원

거슬러 줘야 할 금액: 620원

 

그리디 알고리즘 접근

1. 가장 큰 단위의 동전부터 최대한 사용하여 거스름돈을 줄여나간다.
2. 현재 거스름돈보다 작은 단위의 동전 중 가장 큰 단위의 동전을 선택하여 거스름돈에서 차감한다.
3. 거스름돈이 0이 될 때까지 위 과정을 반복한다.

위 가정에 따라 그리디 알고리즘을 사용해 620원을 거슬러주는 경우를 생각해보자.

500원 동전 1개
100원 동전 1개
10원 동전 2개
총 동전 개수: 1 + 1 + 2 = 4개

 

시간 복잡도 분석

거스름돈을 구성하는 동전의 종류 수를 n이라고 하면, 그리디 알고리즘의 시간 복잡도는 O(n)이다.

각 단계마다 가장 큰 단위의 동전을 선택하는 단순한 계산만 수행하므로, 입력 크기에 비례하여 시간이 증가한다.

 

장단점 정리

장점:

• 간단하고 빠른 실행
  • 그리디 알고리즘은 각 단계에서 가장 최적의 선택을 하므로 알고리즘이 간단하고 실행 속도가 빠르다.
• 메모리 사용량이 적음
  • 보통 그리디 알고리즘은 간단한 계산만 필요로 하기 때문에 메모리 사용량이 적다.

 

단점:

• 최적해를 보장하지 않음
  • 그리디 알고리즘이 항상 최적해를 보장하지 않는 경우도 있다.
  • 지역적으로는 최적이지만, 전체적으로는 최적이 아닐 수 있다.
• 문제에 따라 적용 어려움
  • 일부 문제에는 그리디 알고리즘이 적용하기 어려울 수 있다.
  • 최적 부분 구조나 탐욕 선택 속성이 충족되지 않는 경우가 있다.
• 최적해가 아닌 근사적인 해를 제공한다.

 

마무리

그리디 알고리즘은 모든 경우를 고려하지 않고 그 순간에 최적의 해를 찾는 알고리즘이기 때문에 항상 최적해를 보장해주지는 않지만, 각 단계에서 최적을 선택하고 알고리즘을 마무리 하므로 O(n)의 시간 복잡도를 가져 실행 속도가 빠르다. 근사적인 해를 구해도 괜찮은 상황에서 메모리 사용량을 줄이고, 빠르게 값을 얻고 싶을 때 사용하면 좋을 알고리즘이다.