탐욕법(Greedy) 정리

탐욕법

• Greedy 알고리즘 이라고 부른다.
• 최적의 해에 가까운 값을 구하기 위해 사용되는 방법이다.
• 다양한 경우 중 하나를 결정해야 할 때 마다 그 순간마다 최적이라고 생각되는 경우를 선택하는 방식으로 진행하여 최종값을 구하는 방식이다.

탐욕법의 한계

1. 탐욕 알고리즘은 근사치 추정에 활용한다.
2. 반드시 최적의 해를 구할 수는 없다.
3. 최적의 해에 가까운 값을 구하는 방법중 하나일 뿐이다.

동전예제

public class GreedyEx {

    public void Greedy(Integer price, ArrayList<Integer> dataList) {
        Integer totalCoinCount = 0;
        Integer coinNum = 0;
        ArrayList<Integer> details = new ArrayList<>();

        for (int i = 0; i < dataList.size(); i++) {
            coinNum = price / dataList.get(i);
            totalCoinCount += coinNum;
            price -= coinNum * dataList.get(i);
            details.add(coinNum);
            System.out.println(dataList.get(i) + "  =  " + coinNum);
        }

    }

    public static void main(String[] args) {
        GreedyEx greedyEx = new GreedyEx();
        greedyEx.Greedy(4720, new ArrayList<>(Arrays.asList(500, 100, 50, 1)));
    }

}

부분 배낭 예제

  // 부분배낭
    public void Greedy2(Integer[][] objectList, double capacity) {

        double totalValue = 0.0;
        double fraction = 0.0;

        Arrays.sort(objectList, 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 < objectList.length; i++) {
            if (capacity - (double) objectList[i][0] > 0) {
                capacity -= (double) objectList[i][0];
                totalValue += (double) objectList[i][1];
                System.out.println(objectList[i][0] + " " + objectList[i][1]);
            } else {
                fraction = capacity / (double) objectList[i][0];
                totalValue += (double) objectList[i][1] * fraction;
                System.out.println(objectList[i][0] + " " + objectList[i][1]+ " " + fraction);
                break;

            }
        }

        System.out.println(totalValue);

    }

Comparaeble / Comparator 인터페이스

• 두 인터페이스 모두 정렬 기준을 구현하기 위해서 사용되는 인터페이스이다.
• Comparable

  compareTo() 메서드를 오버라이드 해서 구현하는 것으로 정렬할 객체에 implements로 인터페이스를 추가하여 구현한다.

• Comparator

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

    // Comparable 사용 예제
    static class Edge implements Comparable<Edge> {

        private Integer distance;
        private 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;
        }

    }
        // Comparable 사용예제
        Edge edge1 = new Edge(12, "A");
        Edge edge2 = new Edge(14, "A");
        Edge edge3 = new Edge(10, "A");
        Edge[] edges = new Edge[]{edge1, edge2, edge3};
        //Arrays.sort(edges);
        
        // Comparator 사용예제
        Arrays.sort(edges, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.distance - o2.distance;
            }
        });