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

1. 탐욕 알고리즘이란?

Greedy algorithm 또는 탐욕 알고리즘이라고 불러옴

최적의 해에 가까운 값을 구하기 위해 사용

여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 

 

2. 탐욕 알고리즘 예 

문제 1 : 동전 문제 

지불해야 하는 값이 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<Integer>();
        
        for(int index = 0; index < coinList.size(); index++) {
        	coinNum = price / coinList.get(index);
            totalCoinCount += coinNum;
            price -= coinNum * coinList.get(index);
            details.add(coinNum);
            System.out.println(coinList.get(index) + "원:" + coinNum + "개");
        }
        System.out.println("총 동전 갯수: "+ totalCoinCount);
    }
}

문제 2. 부분 배낭 문제(Fractional Knapsack Problem)

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

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

 * 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음. 그래서 Fractional Knapsack Problem 으로 부름 

    * Fractional Knapsack Problem 의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재 (0/1 Knapsack Problem 으로 불림)

물건(i)	물건1	물건2	물건3	물건4	물건5
무게(w)	10	15	20	25	30
가치(v)	10	12	10	8	5

// 2차원 배열로 작성해보기 
Integer[][] objectList = { {10, 10}, {15, 12}, {20, 10}, {25, 8}, {30, 5} };

public class GreedyAlgorithm {
	public void knapsackFunc(Integer[][] objectList, double capacity) {
    	double totalValue = 0.0;
        double fraction = 0.0;
        
        Arrays.sort(objectList, new Comparator<Integer[]>() {
        	@Override
            public int compare(Integer[] objectItem1, Integer[] objectItem2) {
            	return (objectItem2[1] / objectItem2[0]) - (objectItem1[1] / objectItem1[0]);
            }
        });
        
        for(int index = 0; index < objectList.length; index++) {
        	if((capacity - (double)objectList[index][0]) > 0) {
            	capacity -= (double)objectList[index][0];
                totalValue += (double)objectList[index][1];
                System.out.println("무게:" + objectList[index][0] + ",가치:" + ObjectList[index][1]);
            } else {
            	fraction = capacity / (double)objectList[Index][0];
                totalValue += (double)objectList[index][1] * fraction;
                System.out.println("무게:"+objectList[index][0]+",가치:"+objectList[index][1]+",비율:"+fraction);
                break;
            }
        }
        System.out.println("총 담을 수 있는 가치:" + totalValue);
    }
}

GreedyAlgorithm gObject = new GreedyAlgorithm();
gObject.knapsackFunc(objectList, 30.0);

 

3. 탐욕 알고리즘의 한계

탐욕 알고리즘은 근사치 추정에 활용

반드시 최적의 해를 구할 수 있는 것은 아니기 때문

최적의 해에 가까운 값을 구하는 방법 중의 하나임 

참고 : 정렬 기준 정의하기 

정렬을 위해서는 정렬 기준이 있어야 함 

객체간 정렬을 위해서는 정렬 기준을 먼저 정의해줘야 함 

Integer[] iArray = new Integer[]{1, 10, 4, 3, 2};
Arrays.sort(iArray);
Arrays.toString(iArray);

public class Edge {
	public Integer distance;
    public String vertex;
	
    public Edge (Integer distance, String vertex) {
    	this.distance = distance;
        this.vertex = vertex;
    }
}

Edge edge1 = new Edge(10, "A");
Edge edge2 = new Edge(12, "A");
Edge edge3 = new Edge(13, "A");
Edge[] edges = new Edge[]{edge1, edge2, edge3};

Comparable과 Comparator 인터페이스

Comparable와 Comparator는 둘 다 인터페이스로, 정렬 기준을 구현하기 위해 사용됨. 

 * Comparable 인터페이스는 compareTo() 메서드를 override 해서 구현

     - 일반적으로는 정렬할 객체에 implements로 Comparable 인터페이스를 추가하여 구현

 * Comparator 인터페이스는 compare() 메서드를 override 해서 구현 

     - 일반적으로는 별도 클래스를 정의해서 구현하며, 따라서, 동일 객체에 다양한 정렬 기준을 가진 클래스 작성 가능 

 

public class Edge implements Comparable<Edge>{
	public Integer distance;
    public String vertex;
	
    public Edge (Integer distance, String vertex) {
    	this.distance = distance;
        this.vertex = vertex;
 	}
    
    @Override
    public int compareTo(Edge e) {
    	return this.distance - e.distance;
    }
}

Edge edge1 = new Edge(10, "A");
Edge edge2 = new Edge(12, "A");
Edge edge3 = new Edge(13, "A");
Edge[] edges = new Edge[]{edge1, edge2, edge3};
Arrays.sort(edges);

// comparator
Edge edge1 = new Edge(10, "A");
Edge edge2 = new Edge(12, "A");
Edge edge3 = new Edge(13, "A");
Edge[] edges = new Edge[]{edge1, edge2, edge3};
Arrays.sort(edges, new Comparator<Edge>() {
	@Override
    public int compare(Edge objectItem1, Edge objectItem2) {
    	return objectItem2.distance - objectItem1.distance;
    }
});

Arrays.sort()와 Comparator

다음 예와 같이 Arrays.sort() 메서드는 인자를 두 개 받아서, 두 번째 인자에 Comparator 클래스를 넣어줄 수도 있음 

  * Edge 객체에 Comparable 인터페이스가 정의되어 있다하더라도, Comparator 클래스의 정렬 기준으로 정렬이 됨 

  

이외에 Java 8 에서 lambda 등을 사용한 기법 등 다양한 정렬 기법이 존재함

Arrays.sort(edges, new Comparator<Edge>() {
	@Override
    public int compare(Edge objectItem1, Edge objectItem2) {
    	return objectItem2.distance - objectItem1.distance;
    }
});