[알고리즘] 그리디 알고리즘 - Greedy Algorithm

탐욕적 알고리즘이란? 어떤 선택을 해야할 때 그 당시에 가장 최선의 선택을 하여 문제를 해결하는 알고리즘을 말한다. 

 

- 순간의 선택은 그 당시의 최적의 선택이다. 이런 선택들이 모여 최종적인 해답을 얻는다고 하여 최종 해답이 최적이라는 보장은 없다.

   따라서, 탐욕적 알고리즘은 해답을 얻은 후에 이 해답이 최적인지 검사해야 한다. 

 

- 알고리즘 설계 절차

   1단계) 선정과정(selection procedure)

             : 현재 상태에서 가장 좋은 선택이라고 생각되는 해답을 찾아서 해답모음(solution set)에 포함시킨다.

   2단계) 적정성검사(feasibility test)

             : 새로 얻은 해답모음이 적절한지를 결정한다.

   3단계) 해답 검사(solution check)

             : 새로 얻은 해답모음이 최적의 해인지 결정한다. 

 

- 대표적인 알고리즘

• 거스름돈 문제
• 최소비용 신장트리
  • Prim 알고리즘
  • Kruskal 알고리즘
• 다익스트라 알고리즘
• 배낭 문제
  • 0-1 배낭 채우기 문제
• 최적 머지 패턴
• 허프만 코드(최적 이진코드 찾기) 

 

---

거스름돈 문제

해당 문제를 먼저 도전해보자. 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

<생각해보자>

위의 알고리즘 설계 절차에 따라서 먼저 생각해보자.

음, 동전이 개수가 최소가 되게끔 하려면 큰 액수의 동전부터 생각해야하고... 대부분 이런식으로 생각하고 있을 것이다.

 

정리하자면,

1. 주어야 할 거스름돈을 넘지 않은 가장 큰 액수의 동전을 준다.

2. 1 에서 건네준 동전의 총액이 거스름 돈과 정확하게 일치할 때까지 1을 반복한다.

 

위에서 1 . 은 선정과정에 해당되고, 선정된 동전이 최종 해답에 포함될 수 있는지 검사하는 것이 적정성검사이다. 마지막으로, 현재까지 선정된 동전의 총액이 거스름돈과 일치하는 지 검사하는 것은 해답검사 이다.

 

문제 : 동전의 개수가 최소가 되도록 거스름 돈을 주려면?

입력: changes[] 액면가가 큰 동전이 큰 순서대로 정렬, n : 거스름 돈 액수

출력: cc[] : 거스름돈에서 필요한 각 동전의 개수를 저장한다. 

void minChange(int changes[], int n, int &cc[]){
      cc[] = {0};
      for(int i=1; i<=r; i++){
          while(n>=changes[i]){
              cc[i]++;
              n=n-changes[i];
          }
      }
}

위의 예시 문제의 경우, 필요한 동전의 총 개수만 구하면 되므로 잔돈의 종류별로 몇 개의 동전이 필요한 지 배열에 넣을 필요 없이 잔돈 개수만 더해주면 되기때문에 재귀함수를 사용하지 않고 간단하게 풀리는 문제였다. 

문제의 풀이 추후 업데이트

 

 

 

 

이해가 다 되었다면, 몇가지 비슷한 문제를 더 풀어보도록 하자. 

난이도가 쉽다고 느껴진다면 스킵해도 좋다. 

 

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

https://www.acmicpc.net/problem/11399

11399번: ATM

해설 풀이) 2020/02/08 - [알고리즘/백준 문제풀이] - [백준] 그리디 - 11399. ATM

 

 

0-1 배낭 채우기 문제(Knapsack Problem)

문제 : 어떤 도둑이 배낭을 메고 침입했다. 도둑은 물건의 '무게'와 '값어치'를 알고 있다. 훔칠 물건의 총 무게는 배낭의 용량을 초과할 수 없    다. 배낭에 담을 수 있는 최대 값어치를 구하라.

 

입력 :

•보석 (item)의 개수: n

•보석 집합 S = {item1, item2,…, itemn}

•wi = itemi의 무게, pi = itemi의 가치

•W = 배낭에 넣을 수 있는 총 무게

목표: 배낭의 무게를 넘지 않으면서 최대로 물건을 담는 것. 0-1은 물건이 배낭에 포함되는 것과  포함되지 않는 것을 의미한다.

 

 

배낭의 무게는 30kg 일때,

 

시도1) 가장 비싼 물건 순으로 채워보자.

물건	무게	값
item1	25kg	10
item2	10kg	9
item3	10kg	9

비싼 순으로 채워보면 1 = 25kg => 10 이지만, 최적인 해답은 2+3 = 20kg => 18이다.

따라서 최적의 알고리즘이 아니다!

 

시도2) 가장 가벼운 물건부터 채워보자.

물건	무게	값
item1	25kg	10
item2	10kg	4
item3	10kg	4

가벼운 순으로 채우면 2+3 = 20kg => 8 이지만, 최적의 해답은 1 => 25kg = 10 이다.

따라서 이번에도 최적의 알고리즘이 아니다!

 

시도3) 무게당 가치(값/무게)가 가장 높은 물건부터 채운다. 

물건	무게	값	무게당 가치
item1	5kg	50	10
item2	10kg	60	6
item3	10kg	149	7

무게당 가치가 높은 물건부터 채우면 1+3 = 25kg =>190 이지만, 최적의 해답은 2 + 3 = 30kg => 200이다. 

이것또한 최적의 알고리즘이 아니다!

 

동적 프로그래밍을 이용하여 푼다.

 

n개의 보석들 중에 최적으로 고른 부분집합을 A라고 하자.

1. A가 n번째 보석을 포함하고 있다면, A는 n번째 보석을 뺀 나머지 n-1개 중에서 최적으로 고른 가격의 합에다가 n번째 보석의 가격을 더한 것과 같다. 

2. A가 n번째 보석을 포함하고 있지 않다면, A는 n번째를 뺀 나머지 n-1개 중에서 최적으로 고른 부분집합과 간다. 

 

이를 식으로 표현하면 다음과 같다. 

• (V[i][j]를 처음 i번째까지의 item 만으로 무게 j(j <=W)를 넘지 않으면서 얻을 수 있는 최적의 이익으로 정의)
• V[i][j] = max(V[i−1][j], vi+ V[i−1][j−wi]), if j ≥ wi
•                      V[i−1][j], if j < wi
• when V[0][j] = 0 and V[i][0] = 0

int GreedyKnapsack_DP(int n, int m) // n:물건개수, m:배낭무게
{ 
    int i, w;
 
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= m; w++) // V[i]:가방, W[i]:무게배열, P[i]:이익배열
        {
            if (i == 0 || w == 0)
            {
                 V[i][w] = 0; 
            }
            else if (w > V[i]) // 물건의 무게가 가방무게보다 크면
            {
             	 V[i][w] = V[i - 1][w];
                 
            }
            else
            {
               	 V[i][w] = max(V[i - 1][w], V[i - 1][w - W[i]] + P[i]);
            }
        }
    }
    return K[n][m];
}

 

 

 

 

 

배낭 빈틈없이 채우기 

문제 : 배낭의 용량을 넘지 않으면서 가장 최대의 이득을 얻을 수 있도록 배낭채우기

입력 : 배낭의 용량 M, 아이템의 개수 n, 각 아이템의 이득과 무게가 저장된 배열 p[1:n], w[1:n](무게당 이익이 큰 순으로 정렬 p[i]/w[i] >=p[i+1]/w[i+1])

출력 : 배낭에 들어가는 아이템 리스트 (x[1:n])

 

배낭 빈틈없이 채우기 문제는 0-1 배낭 채우기 문제와 달리 item을 잘라서 일부만 담을 수 있다. 배낭 빈틈없이 채우기 문제는 시도3의 방법으로 항상 최적의 해를 구할 수 있다.

물건	무게	값	무게당 가치
item1	5kg	50	10
item2	10kg	60	6
item3	10kg	149	7

1+3+2x(1/2) => 50+140+30 => 220 

void GreedyKnapsack(float M, int n, int p[], int w[], int& x[]){
	for(int i=1; i<=n; i++){
    	x[i] = 0.0; //초기화
    }
    float U = M;
    for(int i=1; i<=n; i++){
        if(w[i] > U){
              break;
        }
        x[i] = 1.0;
        U -= w[i];
    }
    if(i <= n){
        x[i] = U/w[i];
    }   
}

시간복잡도는 O(NlogN)이다.

 

 

이제, 문제를 풀어보자.

첫번째 문제는, 0-1 배낭 채우기에 관한 문제이고

두번째 문제는, 배낭 빈틈없이 채우기에 관한 문제이다.

 

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

https://www.acmicpc.net/problem/13575

13575번: 보석 가게

문제의 풀이 추후 업데이트

 

 

 

 

 

 

더 많은 문제를 풀어보고 싶다면, 해당 링크로 가서 문제를 풀어보자.

보통 나의 경우 정답비율로 50%내외의 문제를 푸는데, 표의 정답 비율을 클릭하면 정렬되어서 보이므로 원하는 문제를 선택해서 풀어보면된다.

https://www.acmicpc.net/problem/tag/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그리디 알고리즘 - 1 페이지