[09강] 그리디 알고리즘

---

안녕하세요 Gliver 입니다.

이번 글에서는 그리디 알고리즘에 대해 알아보겠습니다.

 

목차

1. 그리디 알고리즘
2. 실제 문제에서 그리디 알고리즘

 

 

접근 방식과 알고리즘

접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다.

 

접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고

알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다.

 

구체적인 예를 들어 설명해보겠습니다.

 

에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고

그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다.

 

에라토스테네스의 체 알고리즘은 언제 쓰면 될까요?

→ 소수(prime number)를 판별할 때 쓰면 됩니다.

 

그리디 알고리즘은 언제 쓰면 될까요?

→ 매 순간에서 가장 최선의 선택을 하여 답이 나올 때 쓰면 됩니다.

 

어떠신가요?

에라토스테네스의 체 알고리즘 같은 경우는 소수(prime number)를 판별할 때 쓰면 되는 반면

그리디 알고리즘의 경우는 "매 순간에서 가장 최선의 선택을 하여 답이 나올 때가 언제인데?" 라는 의문이 들 것입니다.

 

따라서,

에라토스테네스의 체 알고리즘과 같이 쓰이는 상황이 구체적인 알고리즘을 알고리즘이라 생각하고

그리디 알고리즘과 같이 쓰이는 상황이 구체적이지 않은 알고리즘을 접근 방식이라 생각하시면 됩니다.

 

접근 방식에 가까운 알고리즘은 대표적으로

브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 등이 있습니다.

 

이러한 접근 방식에 가까운 알고리즘 문제는

알고리즘을 쓸 수 있도록 상황을 해석하는 능력(문제해결능력)이 중요하게 작용합니다.

 

 

 

1. 그리디 알고리즘

그리디(Greedy)는 탐욕적인 이라는 뜻으로

매 순간에서 가장 최선의 선택을 한다는 의미입니다.

[그리디 알고리즘]

그리디 알고리즘은 매 순간에서 가장 최선인 선택을 하여 답을 구하는 알고리즘입니다.

 

그리디 알고리즘을 성공적으로 사용하려면 다음과 같은 조건을 만족해야 합니다.

매 순간에서의 최선의 선택 = 문제에서의 최적해

최적해란 문제에서의 정답을 의미합니다.

 

그리디 알고리즘은 접근 방식에 가까운 알고리즘이므로

2가지 구체적인 상황을 예로 들어 설명하겠습니다.

Case1) 그리디 알고리즘 사용 가능

[문제]
동전 1원, 2원, 4원을 가지고 N원을 만들어야 한다.
최소한의 동전의 개수로 N원을 만드는 경우를 출력하는 프로그램을 적성하시오. 답이 여러 가지인 경우 아무 경우나 출력하시오.
(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)
시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.

이 문제는 그리디 알고리즘을 사용하여 풀 수 있습니다.

 

최소한의 동전의 개수로 N원을 만들어야 하기 때문에

동전의 우선순위는 4원 > 2원 > 1원 입니다.

 

따라서,

4원을 쓸 수 있을 때까지 쓰고, 그 후에 2원을 쓸 수 있을 때까지 쓰고, 마지막으로 1원을 쓰면 됩니다.

예시) N=11인 경우

현재 만들어야 할 수 : 11
11은 4를 2번 쓸 수 있으므로 4를 2번 씁니다.

현재 만들어야 할 수 : 3
3은 2를 1번 쓸 수 있으므로 2를 1번 씁니다.

현재 만들어야 할 수 : 1
1은 1을 1번 쓸 수 있으므로 1을 1번 씁니다.

따라서, 11은 1을 1번, 2를 1번, 4를 2번 사용하는 경우가 문제의 최적해입니다.

 

위 풀이는 각 상황에서 가능한 큰 수의 동전을 사용하였고

이것이 문제의 최적해와 일치했습니다.

 

위 풀이를 코드로 구현하면 다음과 같습니다.

 

 

 

Case2) 그리디 알고리즘 사용 불가능

[문제]
동전 1원, 3원, 4원을 가지고 N원을 만들어야 한다.
최소한의 동전의 개수로 N원을 만드는 경우를 출력하는 프로그램을 적성하시오. 답이 여러 가지인 경우 아무 경우나 출력하시오.
(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)
시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.

이 문제는 그리디 알고리즘을 사용하여 풀 수 없습니다.

 

이 문제를 Case1) 의 그리디한 풀이를 사용한다면

N=6일 때, 동전을 3개 사용한 4+1+1 의 결과를 도출하게 됩니다.

하지만, 동전을 2개 사용한 3+3이라는 더 좋은 경우가 존재합니다.

따라서, Case2) 문제에서는 매 순간에서의 최선의 선택 = 문제에서 최적해 를 만족하지 못합니다.

 

이렇게 그리디 알고리즘이 실패하는 경우는

수학적으로 접근하거나 DP(Dynamic Programming) 알고리즘을 고려해볼 수 있습니다.

 

결론적으로 말하면, 이 문제의 가장 좋은 해답은 시간 복잡도가 O(N)인 DP 알고리즘을 이용한 풀이입니다.

하지만, 저희는 아직 DP를 배우지 않았기 때문에 이 문제의 DP 풀이는 DP 알고리즘 에서 다루겠습니다.

 

이번 글에서는 수학적 사고 과정을 통한 브루트 포스 알고리즘으로 문제를 해결해보겠습니다.

 

1원의 동전을 사용한 횟수를 a

3원의 동전을 사용한 횟수를 b

4원의 동전을 사용한 횟수를 c 라고 하면

1a + 3b + 4c = N 을 만족하는 a, b, c의 순서쌍이 답의 후보가 되고

그중에서 a+b+c 가 최소인 경우를 출력하면 답을 구할 수 있게 됩니다.

 

사실, 이 풀이는 답은 맞지만 시간 복잡도가 O(N³)이므로 시간 초과가 나는 풀이입니다.

 

위 풀이를 코드로 구현하면 다음과 같습니다.

 

 

 

 

 

2. 실제 문제에서 그리디 알고리즘

실제 문제에서 그리디 알고리즘을 어떻게 이용할 수 있을까요?

 

그리디 알고리즘은

매 순간에서의 최선의 선택 = 문제의 최적해 를 만족하는지 판단하는 게 중요합니다.

 

또 필요에 따라서

매 순간에서의 최선의 선택 = 문제의 최적해 가 되도록 문제를 재해석 하는 능력도 필요합니다.

 

예를 들어 선형 배열이 주어지고

정렬을 하지 않은 상태에서는 그리디 알고리즘 사용이 불가능하였으나

정렬을 하고 나서는 매 순간에서의 최선의 선택 = 문제의 최적해 조건을 만족하여

그리디 알고리즘을 이용하여 문제를 풀 수도 있습니다.

 

정리하자면, 문제의 상황을 다양하게 재해석해보고

그 재해석한 상황에서 매 순간에서의 최선의 선택 = 문제의 최적해 인지를 확인해봅시다.

만약, 재해석을 해봐도 그리디 알고리즘을 사용할 수 없다면 다른 풀이를 떠올려야 합니다.

 

[관련 문제]

백준 : 거스름돈 (5585번)

백준 : 보물 (1026번)

백준 : ATM (11399번)

 

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차 : https://gliver.tistory.com/7