Greedy

그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고 불린다.

미래를 생각하지 않고 근시안적으로 각 단계에서 가장 최선의 선택을 하는 기법. 

 

알고리즘

1. 해 선택(Selection Procedure) : 지금 당시에 가장 최적인 해를 구한뒤, 이를 부분해 집합에 추가한다.

2. 적절성 검사(Feasibility Check): 새로운 부분해 집합이 적절한지 검사한다.

3. 해 검사(Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 아직 문제의 해가 완성되지 않았다면 1번 부터 다시 시작한다. 

 

그리디 알고리즘이 통하는 몇몇 문제들이 있다.

 

활동선택 문제

활동 선택 문제는 쉽게 말해 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 것이다.

 

직관적으로 생각했을 때, 최적의 해를 구하기 위해서는 첫번째 활동이 최대한 일찍 끝나면 된다. 그래야 다른 활동들을 더 많이 선택할 수 있기 때문!!

 

1. 해 선택 : 가장 빨리 끝나는 활동을 부분해 집합에 추가한다.

2. 적절성 검사 : 부분해 집합에서 겹치는 활동시간이 있는지 검사. 활동 시간이 겹친다면 최근에 추가한 활동을 삭제하고, 다시 1번으로 돌아가 그 다음으로 빨리 끝나는 활동을 부분해 집합에 추가한다.

3 해 검사 : 모든 경우를 활동시간을 탐색하고 검사를 끝낸다.

 

 

소스코드

public class Greedy {
    public class Task implements Comparable<Task> {
        int num;
        int start;
        int end;
 
        public Task(int num, int start, int end) {
            this.num = num;
            this.start = start;
            this.end = end;
        }
 
        @Override
        public int compareTo(Task o) {
            return this.end - o.end;
        }
 
    }
 
    public int[] go(int[][] arrays) {
        int[] answer = {};
 
        LinkedList<Task> list = new LinkedList<>();
        LinkedList<Task> result = new LinkedList<>();
        for (int i = 0; i < arrays.length; i++) {
            list.add(new Task(i + 1, arrays[i][1], arrays[i][2]));
        }
 
        // 끝나는 시간이 짧은 순으로 정렬
        Collections.sort(list);
 
        // 1. 해 선택 - 가장 빨리 끝나는 활동을 부분해 집합에 추가
        result.add(list.getFirst());
        int last = list.getFirst().end;
        for (int i = 1; i < list.size(); i++) {
        // 2. 적절성 검사 - 시간이 겹치지 않는 것 집합에 추가
            if (list.get(i).start > last) {
                last = list.get(i).end;
                result.add(list.get(i));
            }
        }
 
        for (Task t : result) {
            System.out.print(t.num + " ");
        }
        return answer;
    }
}