그리디 알고리즘(Greedy Algorithm)

안녕하세요, 오늘은 그리디 알고리즘에 대해서 알아보려고 합니다. 그리디 알고리즘은 많은 알고리즘 중에서 매우 직관적이고 효율적인 방법을 제공하는 알고리즘입니다. 복잡한 문제를 해결하는 데 있어서 현재 상황에서 가장 좋아 보이는 선택을 하는 방법을 취합니다.

그리디 알고리즘(Greedy Algorithm)이란?

그리디 알고리즘은 각 단계에서 가장 최적이라고 생각되는 결정을 하도록 설계된 알고리즘입니다. 이러한 방식은 전체적인 최적화를 보장하지는 않지만, 각 단계에서의 지역적인 최적화를 통해 문제를 단순화하고 빠르게 해결할 수 있는 장점이 있습니다.

 

대표적 그리디 알고리즘 예제

[거스름돈]

거스름돈이 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정

손님에게 거슬러 줘야 할 돈이 N원일때 거슬러 줘야 할 동전의 최소 개수를 구해라

(단, 돈 N은 항상 10의 배수이다.)

 

[문제 접근]

1260원을 거슬러 줘야 할때,  동전을 최소로 주려면 큰 화폐단위부터 주면 된다.

500원 2개, 100원2개, 50원 1개, 10원 1개로 6개 줄 수 있음

 

[코드]

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin
print(count)

[시간 복잡도]

거슬러 줄 수 있는 동전의 개수가 K 일때, 시간 복잡도는 O(K)이다.

 

그리디 알고리즘 장점과 단점

그리디 알고리즘의 주요 장점은 간단하고 직관적인 해결책을 제공한다는 것입니다. 각 단계에서 최적의 선택을 하면 되므로, 복잡한 계산이나 깊은 생각 없이도 해결책을 찾을 수 있습니다.

그러나 그리디 알고리즘의 단점은 지역적인 최적해가 반드시 전체적인 최적해가 될 수 없다는 것입니다. 즉, 모든 상황에서 그리디 알고리즘이 최적의 해결책을 제공하지는 못합니다. 따라서 그리디 알고리즘을 사용할 때는 문제의 성격과 그리디 알고리즘의 특성을 잘 이해하고 있어야 합니다.

결론

그리디 알고리즘은 복잡한 문제를 간단하게 해결하는 강력한 도구입니다. 그러나 그리디 알고리즘이 항상 최적의 해를 제공하지는 않으므로, 문제의 특성과 그리디 알고리즘의 성질을 잘 이해하고 적용해야 합니다. 그리디 알고리즘이 적절하게 사용될 수 있는 문제는 많으며, 이에 대한 이해를 높이면 많은 문제를 효율적으로 해결할 수 있을 것입니다.

다음 포스팅에서는 그리디 알고리즘의 다양한 예제와 그 해결방법에 대해 자세히 알아보겠습니다. 감사합니다!