[알고리즘] 그리디 알고리즘/ 탐욕법 (Greedy algorithm)

📕그리디 알고리즘이란 ?

---

그리디 알고리즘은 코딩테스트에 자주 나오는 단골 문제이면서,

알고리즘 문제에 널리 사용되는 알고리즘이다. 

그리디 알고리즘은 무엇일까? 

 

그리디 알고리즘의 정의는 다음과 같이 말할 수 있다.

"A greedy algorithm always makes the choice that looks best at the moment"

 

그리디 알고리즘은 '지금 당장 좋은 것을 고르는 방법'이다.

즉, 선택의 순간이 왔을 그때, 가장 좋은 것을 선택하는 것이다.

('Greedy'라는 이름을 보더라도 탐욕적인 것을 알 수 있다.)

 

📕 Greedy algorithm vs Dynamic programming

---

그리디 알고리즘과 다이나믹 프로그래밍을 언뜻 보면 비슷하다고 생각할 수 있다.

절차적으로 해결법을 찾는 것과, 작은 문제로 큰 문제의 해답 찾는 등 비슷한 점이라고 생각할 수 있지만, 실제로는 다르다.

 

다이나믹 프로그래밍은 모든 단계에서 선택을 할때, subproblem의 의존하여 선택을 하는반면,

그리디 알고리즘은 subproblem과 관계 없이 항상 가장 좋은 것을 선택하여, subproblem을 비롯한

미래의 일어날 어떠한 선택에도 의존성이 없다.

또한 그리디 알고리즘은 문제를 줄여가는 것이지, 작게 나눠서 문제를 해결하는 D&C와도 다른 방식이다.

(D&C는 한번의 스텝에 여러 subproblem을 만들어내지만, 그리디는 한 단계에 한번의 선택만 한다)

 

또한 DP를 수행할때는 '주로' bottom-up, 즉 상향식으로 작은 문제에서 큰 문제로 문제를 해결하지만, 

('주로'라고 표기한 이유는 DP 중에는 하향식 DP도 존재하기 때문이다.

그럼에도 DP는 선택을 하기 전에 subProblem을 먼저 해결한 후 선택을 진행한다.)

그리디는 이와는 반대로 큰 문제에서 작은 문제로 줄여가는 top-down 방식을 '주로' 사용한다.

 

당연하게도 그리디 알고리즘은 항상 최적의 해를 도출하지 않기 때문에,

그리디 알고리즘에서 매 단계의 선택이 global한 최적의 해를 도출하는지를 증명할 필요가 있다.

하지만 DP는 '최적의 구조'만 가지고 있다면 항상 최적의 해를 도출한다.

 

DP와 그리디 알고리즘의 차이를 가장 확실하게 보여주는 문제는 바로

"0-1 knapsack problem" 과 "Fractional knapsack problem" 이다.

아래의 예제에서 설명하겠다.

 

📕 탐욕적 접근법

---

탐욕적 접근법(Greedy strategy) 는 다음과 같이 말할 수 있다.

 

• Make some greedy choice => Greedy choice는 이 선택을 했을때 최적의 해가 존재한다면 '안전한' 선택이다.              
• Reduce to a smaller subproblem => 문제를 더 작은 사이즈로 줄여 가면서 문제를 푼다.
• Iterate unitl solved 

그리디 접근법은 locally optimal choice로 globally optimal solution 으로 만드는 과정이다.

 

위의 세 접근 법은 아래의 첫번째 예제를 통해서 알 수 있다.

 

 

 

📕 예제 1 : 가장 큰 수 만들기

---

가장 쉽게 접할 수 있는 예제는 바로 가장 큰 수를 만드는 것이다.

3, 9 , 5, 9, 7 ,1로 만들 수 있는 가장 큰 6자리 수 는 무엇일까?

 

우리는 이를 보자마자 무의식적으로 큰 순서대로 정렬하고 있을것이다.

997531 이렇게 말이다.

 

그렇다면 이 수를 만드는 절차는 어떻게 되는가?

1. 가장 큰 수를 찾는다.

2. 변수 string에 붙인다.

3. 원래 배열에서 제거한다.

4. 위의 과정을 배열이 빌때까지 반복한다.

 

위 과정을 C++ 코드로 구현하면 다음과 같이 할 수 있다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  vector<char> digits = {'3', '9', '5', '9', '7', '1'};
  string s;
  sort(digits.begin(), digits.end()); //오름차순으로 정렬
  
  while(digits.size() != 0) { // digits의 길이가 0이 아니라면 실행
   s += digits[digits.size()-1]; //배열의 마지막 원소를 s에 붙여넣음
   digits.pop_back(); //배열의 마지막 원소 제거
  }
  cout << s;
}

가장 큰 수를 선택함으로써 탐욕적인 선택을 했고,

가장 큰 수를 선택한 후,  그 수를 원래의 배열에서 제거함으로써, 남은 문제를 더 작은 사이즈로 줄였으며,

이를 문제가 해결될때까지 반복했다.

 

📕 예제 2 :  Fractional Knapsack problem

---

"Fractional knapscak problem"은 그리디 알고리즘의 대표적인 문제이다.

도둑이 물건을 훔치려 하고 있다. 도둑의 가방은 최대 30kg 까지 넣을 수 있다.

훔치려는 모든 물건은 하나만 존재하고, 모든 물건 마다 무게와 가치가 정해져 있고, 물건의 일부분만 가져갈 수 있다.

물건의 일부분만 가져간다면, 가치 역시 무게에 비례한다.

 

이 문제를 어떻게 풀어야 할까?

먼저 가장 가치있는 순으로 배낭에 넣는다고 생각해보자

그렇다면 140달러의 가치가 있는 20키로 item3와 60달러의 가치가 있는 item2를 넣을 것이다.

그렇다면 훔친 물건의 총 가치는 200달러가 될 것이다.

 

두번째로 단위당 가격이 높은 순으로 넣는다고 생각해보자.

item1은 1kg 당 10달러, item2는 1kg 당 6달러, item3는 1kg당 7달러이다.

만약 물건의 일부분만 가져갈 수 없다면,  item1를 넣고, item3를 넣으면 25kg의 무게이이기 때문에 10키로의 item2을 넣을 수 없다.

그렇기 때문에 가치는 190달러가 된다.

 

하지만 물건의 일부분만 가져갈 수 있기 때문에 greedy 알고리즘이 적용가능한것이다.

먼저 단위당 가격이 높은 순으로 정렬하면

item1은 1kg 당 10달러, item3는 1kg당 7달러, , item2는 1kg 당 6달러이다.

이후 5키로의 item1과 20키로의 Item3를 넣고 남은 item2를 남은 용량 만큼 담는다.

그렇게 되면 50달러 + 140달러 + 30달러 = 220달러가 된다.

 

이렇게 그리디 알고리즘을 사용할 시, 시간복잡도는 O(nlogn)으로 상대적으로 빠른 속도로 답을 도출가능하다.