'Greedy', 즉 탐욕적으로 해결한다.

 

 

문제 상황을 '탐욕적으로 해결한다'는 것은 무슨 말일까? 과연 어떠한 경우일까?

욕심이 과한만큼 문제를 '가장 좋은 방법' 즉, 현재로서 가장 최적의 방법으로 해결하려는 경우일 것이다.

 

욕망의 항아리, 나무위키

 

'어라? 그럼 어떠한 문제든 탐욕 알고리즘으로 푸는 것이 가장 좋은 거 아닌가?' 라고 자연스레 생각이 든다.

 

하지만 이는 잘못된 판단이다.

탐욕 알고리즘에서 가장 중요한 키워드는 최적이 아니라 '현재'라고 할 수 있다.

 

이게 무슨 말이냐면..

문제를 해결하기 위해 마주하는 수많은 선택의 순간순간에 지금 현재 가장 최적인 답을 선택한다는 것이다.

 

마치 바로 눈 앞에 있는 돈에 정신이 팔린 욕심쟁이처럼

다음에 일어날 수 있는 상황(경찰에 잡힌다!)(선택의 잠재적 결점)을 전혀 고려하지 않고,

현재 생각하기에 가장 좋은 해답(돈을 가져가자!)을 선택한다.

 

7대 죄악을 다룬 영화 Seven에서 GREED

 

그렇기에 선택할 당시(locally)는 최적이지만, 전체적으로(globally)는 최적이 아닐 수도 있다.

 

탐욕 알고리즘하면 빠질 수 없는 가장 유명한 예시, 동전 문제를 통해 더 자세히 살펴보자.

 

[동전 문제]로 알아보는 그리디 알고리즘의 장점

동전 문제, 거스름돈 문제

 

동전 문제는 가지고 있는 동전의 종류에 따라 목표 금액에 맞는 최소한의 동전 개수를 구하는 문제이다.

 

동전 문제 1. 10원, 50원, 100원, 500원을 가지고 700원을 줘야할 때, 동전의 최소 개수

이 때 줄 수 있는 최악의 경우는 10원짜리 70개일 것이다. 누군가에게 700원을 10원 70개로 준다면 매우 화를 낼테니..

반면에 가장 줄 수 있는 최적의 경우는 500원짜리 1개와 100짜리 2개로 총 3개이다.

 

이 예시는 탐욕 알고리즘의 가장 적합한 예시이다.

가장 큰 최적의 동전(500원)을 먼저 고르고, 다음 100원, 또 한 번 100원 이렇게 세 번을 고르면 되기 때문이다.

 

 

다음 방법을 컴퓨터가 수행하기 위해 알려주려면 다음 단계들로 정의할 수 있을 것 같다.

1. 선정 과정(selection procedure) : 현재 상태에서 가장 좋은(greedy) 해답을 찾아서 해답모음(solution set, 집합)에 포함시킴

     -> '목표 금액이 700원이니까 가장 큰 동전 500원을 골라야겠다!'

2. 적정성 점검(feasibility check) : 새로 얻은 해답 모음이 적절한지 결정함

     -> '방금 고른 동전(500원)까지 여태까지 고른 동전들이 목표 금액 700원을 넘었나?'

3. 해답 점검(solution check) : 새로 얻은 해답 모음이 최적의 해인지 결정함

     -> '방금 고른 동전(500원)까지 여태까지 고른 동전들이 목표 금액 700원과 금액이 같은가?' 

            - 아니요 : '새로운 동전 고르자!' (최적의 해가 아님)

            - 네 : '동전을 모두 골랐다!' (최적의 해임)

 

 

슈도 코드로 표현하면 다음과 같다.

while(동전이 남아있고 문제 미해결){
    가장 가치가 높은 동전을 집음                      // 선택과정
    if (동전을 더하여 거스름돈의 총액이 목표 금액을 초과){ // 적절성 검사
        동전을 도로 집어 넣음
    } else {
        거스름돈에 동전을 포함시킴
    }
    if(거스름돈의 총액이 목표 금액과 같음){             // 해답 점검
        문제 해결!
    }
}

 

그렇다면, 탐욕적 알고리즘의 단점인

현재 상태로는 최선인 선택이지만, 전체적으로는 그렇지 않은 경우는 어떤 경우일까?

 

다음 동전 문제를 통해 알아보자!

 

[동전 문제]로 알아보는 그리디 알고리즘의 단점 (+ 동적 계획법)

동전 문제 2. 10원, 50원, 100원, 120원, 500원을 가지고 160원을 줘야할 때, 동전의 최소 개수

다음 경우를 탐욕 알고리즘으로 푼다면 가장 가치가 큰 120원 1개를 선택하고, 남은 40원은 10원 4개로 총 5개의 동전을 선택할 것이다.

 

하지만 이는 최적의 경우가 아니다.

120원이 아니라 100원을 선택한다면, 50원 1개와 10원 1개로 총 3개의 동전을 선택할 수 있기 때문이다.

 

따라서, 항상 최적의 수를 선택한다고 해서 전체적으로 최적인 경우가 아닐 수도 있으니 탐욕 알고리즘을 사용할 때에는 이를 주의하여 사용해야 할 필요가 있다.

 

그렇다면, 이 문제는 어떻게 푸는 것이 좋을까? 탐욕 알고리즘을 적용한다면 최적의 해를 구할 수 없기에 동적 계획법으로 접근하는 것이 좋다. 모든 동전들의 조합을 고려한 뒤 이전 계산 결과를 저장해가며 최적의 해를 구해야 한다. 

 

DP vs Greedy

linkedin, Jaskaran Singh

 

'dp vs greedy'를 검색하면, 탐욕 알고리즘과 동적 계획법 중 어떤 알고리즘을 사용해야하는가에 대해서 비교해놓은 자료들이 많이 보인다. 두 알고리즘은 '최적의 해'를 구하기 위해 하위 문제를 나눠서 접근하는 유사한 방법을 사용하고 있기 때문이다. 이를 최적 부분 구조(DP의 개념, 추후에 포스팅 예정이다.)이라고 하는데, 복잡한 큰 문제를 해결하기 위해 하위 문제들로 나눠서 작은 문제 단위로 풀고, 이를 모두 조합하였을 때 전체 문제의 최적의 해를 구할 수 있어야 하는 개념이다. DP와 Greedy 모두 이를 만족한다. 동전 문제로 보자면 '현재까지의 값 + 선택할 동전'의 하위 문제로 나눌 수 있기 때문이다. 하지만 둘의 차이점은 시점에 달려있다. 이게 무슨 말이냐 하면.. 탐욕 알고리즘은 추후의 선택, 조합을 고려하지 않는다. 왜냐하면 지금 당장 현재로서의 최적을 찾기 때문이다. 하지만 동적 계획법은 지금 당장 최적의 선택이 아니더라도, 일단 선택한 뒤 저장해가며 전체로서의 최적을 찾는 방법이다.

 

따라서 탐욕 알고리즘은 '지금의 최적'에만 집중하기에 구현이 쉽지만 전체로서의 최적이 아닐 수 있다는 단점이 있으며, 반대로 동적 계획법은 '전체의 최적'을 위한 방법이기에 항상 최적의 해를 구할 수 있지만, 그만큼 구현과 설계가 비교적 복잡할 수 있다는 단점이 있다.

 

 

따라서 어떤 알고리즘을 사용해야할까에 대해 현명한 결정을 하기 위해서는 각 알고리즘의 특성을 잘 이해하고 사용하는 것이 중요할 것 같다. 두 알고리즘은 간단하게 다음과 같은 장단점을 가지고 있다. 문제별로 잘 선택해서 사용해보자.

 

티스토리툴바