[알고리즘] 그리디 알고리즘 (탐욕 알고리즘)

Greedy algorithm 

 

• 최적의 해에 가까운 값을 구하기 위해 사용된다.
• 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식이다.
• 매 순간 최적을 선택하기 때문에 현재 상황의 선택이 나중에 미칠 영향은 고려하지 않는다. 때문에 최적이라는 보장이 없다.
• 때문에 문제를 풀때 현재 상황에서 최적의 답만 선택해도 풀 수 있는 문제인지 파악해야 한다.
• 그리디 알고리즘을 적용해서 최적해를 구할 수 있는 문제는 2가지 조건을 만족한다.
  • 현재 선택이 이 후의 선택에 영향을 주지 않는다.
  • 매 순간 최적의 해가 문제 전체에 대한 최적의 해 이다.
• 그리디 알고리즘이 최적해를 보장받지는 못하더라도 어느 정도까지 가까운 해를 구할 수 있기 때문에 근사 알고리즘으로 그리디 알고리즘을 사용하는 경우가 있다.
• 그리디 알고리즘은 정렬 알고리즘과 짝을 맞추어 나오기 때문에 정렬하는 다양한 방법과 함께 공부하면 좋다.

 

• 탐욕 알고리즘 문제 예시
  • 문제를 직접 풀지 않고 , 전략을 설명하기 위해 간단하게 문제를 살펴보자. 
    • 부분 배낭 문제 
      • 무게 제한이 K인 배낭에 최대 가치를 가지도록 물건을 넣는 문제이다.
      • 이번 문제에서는 물건을 쪼개서 넣을 수 있다고 가정하자.
       

• 2차원 배열로 데이터를 담고, 무게 대비 가치 비율이 높은 순으로 정렬을 한다.
• 그 중 하나씩 빼서 K에 해당 물건의 무게를 - 해준다.
• 이때, 정렬 기준을 재정의 하는 방법을 알아야 한다.
  • 배열에 대한 정렬 방법
    
    • Arrays.sort( )
  • 객체에 대한 정렬 방법 
    • Comparable, Comparator 인터페이스 기법
    • 둘 다 인터페이스로, 정렬 기준을 구현하기 위해 사용된다.

 

Comparable 

• Comparable 은 compareTo( ) 메서드를 override 해서 구현
• 일반적으로 정렬한 객체에 implements 로 Comparable 인터페이스를 추가하여 구현한다. 

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;
    }



    public static void main(String[] args) {
        Edge edge1 = new Edge(12, "A");
        Edge edge2 = new Edge(10, "A");
        Edge edge3 = new Edge(13, "A");

        Edge[] edges = {edge1, edge2, edge3};

        Arrays.sort(edges);

        for (int i = 0; i < edges.length; i++) {
            System.out.println(edges[i].distance);
        }
    }
}

 

 

Comparator

• Comparator 인터페이스는 compare( ) 메서드를 override 해서 구현
  • 일반적으로는 별도 클래스를 정의해서 구현하며, 동일 객체에 다양한 정렬 기준을 가진 클래스를 작성 가능하다.

public class Edge {
    public Integer distance;
    public String vertex;

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


    public static void main(String[] args) {
        Edge edge1 = new Edge(12, "A");
        Edge edge2 = new Edge(10, "A");
        Edge edge3 = new Edge(13, "A");

        Edge[] edges = {edge1, edge2, edge3};

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

        for (int i = 0; i < edges.length; i++) {
            System.out.println(edges[i].distance);
        }
    }
}

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