Algorithm/Baekjoon(백준)

[Algorithm] Greedy Algorithm 탐욕 알고리즘 1 - [ 백준 5585 ]

통스 2019. 11. 18. 13:10
반응형

오늘은 Greedy Algorithm(탐욕 알고리즘)에 대해서 알아보겠습니다.

 

탐욕 알고리즘은 Dynamic Programming과 마찬가지로 가장 최적화를 하기 위해서 만들어진 알고리즘입니다. 이 알고리즘을 탐욕 알고리즘이라고 부르는 이유는 탐욕 알고리즘의 기본 원칙이 

더보기

각 단계에서 가장 최적의 답만을 선택한다.

이기 때문입니다. 미래를 생각하는 것이 아니라 지금 현재 단계만을 가지고 답을 도출하기 때문에 마치 욕심쟁이 같다고 생각되어 탐욕 알고리즘이라는 이름을 얻게 되었습니다.

 

그렇다면 일반적으로 탐욕 알고리즘을 사용하는 경우는 언제일까요? 탐욕 알고리즘은 최적화를 하기 위해 고안된 알고리즘이지만 다이나믹 프로그래밍과 다르게 모든 경우에서 최적의 답을 구해주진 않습니다. 위에서 언급했듯이 현재 단계만을 고려하기에 미래나 다른 방식의 해를 전혀 고려하지 않기 때문입니다. 하지만 특정 조건이 갖춰진다면 다이나믹 프로그래밍보다 더 효율적으로 해를 구할 수 있습니다. 탐욕 알고리즘으로 풀 수 있는 문제는 대표적으로 다음 3가지입니다.

 

  1. 거스름돈 문제
  2. 배낭(KnapSack) 문제
  3. 회의실 배정(Activity Selection) 문제

거스름돈 문제

백준 5585 거스름돈에서 같은 문제를 풀 수 있습니다.

더보기

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

이 문제에서 탐욕 알고리즘 방식을 적용해서 푼다면 다음과 같이 풀 수 있다. (Ex: 거스름돈 620엔을 줘야할때)

 

  1. 총 거스름돈을 넘지 않고 줄 수 있는 최대 금액을 거스름돈을 준다. (Ex: 500엔)
  2. 총 거스름돈에서 1번에서 구한 금액을 제외한다(Ex:120엔)
  3. 답을 사용한 동전만큼 더한다.
  4. 1~3번의 과정을 총 거스름돈이 0원이 될때까지 반복한다.(Ex : 120 - 100 = 20엔, 20 - 10 = 10엔, 10 - 10 = 0엔)
  5. 더해진 총 동전 개수를 구한다.(500엔 1개, 100엔 1개, 10엔 2개 -> 4개)

이 내용을 코드로 옮기면 다음과 같다. (C++)

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

using namespace std;

int changeCoin[6] = {500, 100, 50, 10, 5, 1};

int main(void){

    //지불할 돈(1000이하)
    int price;
    cin>>price;

    int coinCnt = 0;
    int coinIdx = 0;

    int change = 1000-price;

    while(change != 0){
        //현재 단계에서 사용한 동전 수
        int cnt = change / changeCoin[coinIdx];
        //이번 단계에서 사용한 동전 수를 더하고
        coinCnt += cnt;
        //거스름돈에서 사용한 돈을 빼준다.
        change -= cnt * changeCoin[coinIdx];
        //다음 단계의 거스름돈으로 옮긴다.
        coinIdx++;
    }

    cout<<coinCnt<<endl;

    return 0;
}

위와 같이 계산하면 해당 문제는 통과가 가능하다.

 

 

하지만 이 문제를 조금만 바꾸어서 생각해보자. 만약 거스름돈의 종류가 {500, 100, 50, 10, 5, 1}에서 {500, 310, 100, 50, 10, 5, 1}으로 바뀐다면 어떨까? 이렇게 바뀐 문제를 위 코드로 푼다면 똑같이 4개가 나오겠지만 실제로 생각해본다면 답인 [500, 100, 10, 10]보다 [310, 310]으로 2개인 경우가 최소 거스름돈 개수가 된다.

 

이렇게 답이 다르게 나오는 경우는 탐욕 알고리즘이 방식인 현재 단계에서 최적(문제에서 500엔)만을 고려한 알고리즘이라서 그렇다. 따라서 최적화 문제라고 무조건 탐욕 알고리즘을 방식을 따르는 건 옳지 않고 매우 조심해야 한다.

반응형