알고리즘) 탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘(Greedy Algorithm)

 

탐욕 알고리즘은 '미래를 생각하지 않고 현 상황에서 가장 최선의 선택을 하는 알고리즘'으로

그 선택이 탐욕스럽다고 해서 붙여진 알고리즘입니다.

현 상태에서는 최선의 선택을 하지만 각 단계를 거치고 나면 최선의 선택을 하지 못하는 경우가 많습니다.

 

미래에 대한 분기가 생기게 되면 최선의 선택을 하지 않습니다.

예시로 지금 선택하면 1개를 주는데 다음에 선택하면 3개를 주는 상황을 가정을 하면

다음 단계에서 받으면 3개를 받을수 있지만. 탐욕 알고리즘으로는 1개를 선택합니다.

 

많이들 예시로 작업한 동전을 거슬러주는 상황으로 테스트 코드를 작성합니다.

대체적으로 동전은 불편하기 때문에 최소의 동전으로 거슬러주는 상황이 거슬러 받는 사람에게는 좋다는 가정입니다.

    private void GreedAlogrithm( int _value ){

        Logger.LogFormat("[GreedAlogrithm] Start Value :{0}",_value);

        int []coinList = {500,100,50,10,1};
        int calcValue = _value;
        int coinIndex = 0;

        while(calcValue > 0){
            int coin = coinList[coinIndex];
            if(coin < calcValue){
                int mok = calcValue / coin;
                Logger.LogFormat("[Calc] Coin :{0} x {1}", coin, mok);
                calcValue-= (mok * coin);
            }
            
            coinIndex++;
        }
    }

123

코인을 500원, 100원, 50원, 10원, 1원이 있다는 가정 하에 해당 로직을 처리했다.

탐욕 알고리즘의 단점은 현상황에서 애매하게 떨어지는 값인 경우 (1원 이 없다는 가정하에)는 

정상적으로 거슬러주지 못한다.

그래서 경우에 따라서는 현 상황에서 최선의 선택을 해야하는 상황에서 종종 사용하게 된다.

 

★★★☆☆