탐욕 알고리즘

탐욕 알고리즘 (Greedy)

Greedy algorithm 또는 탐욕 알고리즘 이라고 불림
최적의 해에 가까운 값을 구하기 위해 사용
매 순간 최적이라고 생각되는 경우를 선택해 최종적인 값을 구하는 방식

 

탐욕 알고리즘 예

 

동전 문제

지불해야 하는 값이 4720원 일 때, 1원, 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오

 

가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현

public class GreedyAlgorithm {
    public void coinFunc(Integer price, ArrayList<Integer> coinList) {
        Integer totalCoinCount = 0;
        Integer coinNum = 0;
        ArrayList<Integer> details = new ArrayList<>();
        
        for(int i = 0; i < coinList.size(); i++) {
            coinNum = price / coinList.get(i);
            totalCoinCount += coinNum;
            price -= (coinNum * coinList.get(i));
            details.add(coinNum);
            
            System.out.println(coinList.get(i) + "원 : " + coinNum + "개");
        }
        
        System.out.println("총 동전 갯수 : " + totalCoinCount);
    }
}



GreedyAlgorithm ga = new GreedyAlgorithm();
ArrayList<Integer> coinList = new ArrayList<Integer>(Arrays.asList(500, 100, 50, 1));
ga.coinFunc(4720, coinList);    // 500원 : 9개 / 100원 : 2개 / 50원 : 0개 / 1원 : 20개

 

 

부분 배낭 문제

무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제

 

각 물건은 무게(w)와 가치(v)로 표현 될 수 있음

물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 반대로 쪼개서 넣을 수 없는 배낭문제도 존재함

// 2차원 배열
Integer[][] array = {    {10, 10}, 
                         {15, 12}, 
                         {20, 10}, 
                         {25, 8}, 
                         {30, 5}
                     };
                     
public class GreedyAlgorithm {
    public void knapsackFunc(Integer[][] objArray , double capacity) {
        double totalValue = 0.0;
        double fraction = 0.0;
        
        Arrays.sort(objArray, new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return (o2[1] / o2[0]) - (o1[1] / o1[0]);
            }
        });
        
        for(int i = 0; i < objArray.length; i++) {
            // 다 들어갈 수 있으면
            if(capacity - (double)objArray[i][0] > 0) {
                capacity -= (double)objArray[i][0];
                totalValue += (double)objArray[i][1];
                
                System.out.println("무게 : " + objArray[i][0] + "가치 : " + objArray[i][1]);
                
            } else {
                fraction = capacity / double)objArray[i][0];
                totalValue += (double)objArray[i][1] * fraction;
                
                System.out.println("무게 : " + objArray[i][0] + "가치 : " + objArray[i][1] + "비율 : " + fraction);
                
                break;
            }
        }
        
        System.out.println("총 담을 수 있는 가치 : " + totalValue);
    }
}


GreedyAlgorithm ga = new GreedyAlgorithm();
Integer[][] objectList = { {10, 10}, {15, 12}, {20, 10}, {25, 8}, {30, 5} };
ga.knapsackFunc(objectList, 30.0);    // 무게 : 10 가치 : 10 / 무게 : 15 가치 : 12
                                      // 무게 : 20 가치 : 10 비율 : 0.25 / 총 담을 수 있는 가치 : 24.5

 

 

탐욕 알고리즘의 한계

근사치 추정에 활용, 반드시 최적의 해를 구할 수 있는 것은 아님

 

 

 

 

 

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스