[알고리즘/JAVA] 그리디와 우선순위 큐 (과제, 강의실 배정, 보석 도둑)

 

그리디와 우선순위 큐

 

그리디 알고리즘은 매번의 선택의 순간에서의 최선인 답을 도출하면서 결과를 도출하는 방법이다. 매 순간에 최선의 해답을 판단해야 할 때, 우선순위 큐가 유용하게 사용될 수 있다.

우선순위 큐는 그리디에서 매 순간의 최적의 선택이 이전의 결정에 의해 영향을 받을 경우, 그 선택의 후보군들을 저장해 둘 수단으로서 유용하게 사용될 수 있다.

PS문제에서 우선순위 큐와 그리디와 함께 사용되는 경우가 매우 많다. 이러한 방법들을 사용한 문제들을 풀어보도록 하자.

---

 

<함께 보기> 그리디 알고리즘의 개념

https://sjh9708.tistory.com/216

[알고리즘/JAVA] 그리디 (Greedy) : 개념 (동전, 단어 수학, 허프만 코딩)

 

<함께 보기> 우선순위 큐 구현

https://sjh9708.tistory.com/206

[자료구조/JAVA] 우선순위 큐 : 힙(Heap)

 

 

 

---

방법론

 

일반적으로 그리디와 우선순위 큐를 함께 사용하는 문제들은 다음과 같은 문제풀이 방식을 많이 사용하게 된다.

1. 계산 순서 : 나중 단계에서 처리되어도 되는 순서로 진행한다. 처리되지 못하면 후보군으로 넣어서 이후 단계에서 처리하면 된다.
2. 후보군 순서 (우선순위 큐) : 현재 단계의 후보군들 중 가장 높은 가치를 산출할 수 있는 순서

 

해당 방법을 문제를 풀어가면서 이해해보도록 하자.

---

문제 : 과제 (백준 13904)

 

우선 예제에서 마감일과, 과제로 얻을 수 있는 점수를 나열해보면 다음과 같다.

• 1일 : A(20점)
• 2일 : B(50점)
• 3일 : C(30점)
• 4일 : D(10점), E(40점), F(60점)
• 6일 : G(5점)

마지막 과제의 마감일이 6일이므로, 우리는 총 6일동안의 스케줄을 분배해야 한다. 

---

마지막 날인 6일부터 살펴보면 수행할 수 있는 과제는 G뿐이다. 5일에도 6일의 과제를 수행할 수 있다.

4일에는 마감일이 4인 과제인 D, E, F 뿐만 아니라 6일의 과제인 G도 미리 수행할 수 있다. 

이를 토대로 6일동안 수행할 수 있는 과제의 경우의 수는 다음과 같이 표현할 수 있다.

          

• 6일 or 5일 : G(5)
• 4일 : D(10), E(40), F(60), G : 현재 날짜에서 수행할 수 있는 과제 중 가장 높은 점수는 F이다.
• 3일 : C(30), D(5), E(50), F, G
• 2일 : B(50), C(30), D(10), E, F, G
• 1일 : A(20), B, C(30), D(10), E, F ,G

즉 가장 마지막 마감일에 수행할 과제부터 계산하기 시작한다면 해당 날짜에 수행할 수 있는 과제의 후보들은 이전 마감일에 과제를 할당할 때에도 후보로서 사용할 수 있다는 것을 알 수 있다. 

따라서 우리는 마지막 마감일부터 과제를 할당하고, 후보군이 될 과제들은 높은 점수 순서대로 우선순위 큐에서 대기하도록 하고, 후보군들 중 가장 높은 점수를 획득할 수 있는 과제를 해당 날짜에 수행하도록을 설계할 수 있다.

	큐에 삽입	큐에서 꺼냄 (해당 날짜에 할 과제 결정)	우선순위 큐 (후보군)
6일	G(5)	G(5)	G(5)
5일	-	-	-
4일	D(10), E(40), F(60)	F(60)	F(60), E(40), D(10)
3일	C(30)	E(40)	E(40), C(30), D(10)
2일	B(50)	B(50)	B(50), C(30), D(10)
1일	A(20)	C(30)	C(30), A(20), D(10)

 

---

구현

 

입력 받기, 과제 정렬

class Homework implements Comparable<Homework> {
    int date;
    int score;
    public Homework(int date, int score){
        this.date = date;
        this.score = score;
    }

    @Override
    public int compareTo(Homework o) {
        if(this.date == o.date){
            return o.score - this.score;
        }
        return o.date - this.date;
    }

}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        Homework[] homeworks = new Homework[n];
        int maxDate = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            homeworks[i] = new Homework(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            maxDate = Math.max(homeworks[i].date, maxDate);
        }

        Arrays.sort(homeworks);
        
    }
}

 

문제의 형식대로 과제들을 입력받자.

과제는 점수와 마감일의 속성이 있으며, 우리는 맨 마지막 마감일부터 차례로 계산할 것이므로 과제들을 마감일이 늦은 순으로 정렬되도록 하자.

그리고 과제의 마지막 마감일 (우리가 계산해야 할 총 기간)을 계산해서 maxDate에 저장해두자.

 

 

---

우선순위 큐 사용으로 날짜별 수행할 과제 계산하기

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        Homework[] homeworks = new Homework[n];
        int maxDate = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            homeworks[i] = new Homework(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            maxDate = Math.max(homeworks[i].date, maxDate);
        }

        Arrays.sort(homeworks);

        // 높은 점수 순으로 정렬되도록 우선순위 큐 생성
        PriorityQueue<Homework> pq = new PriorityQueue<>(new Comparator<Homework>() {
            @Override
            public int compare(Homework o1, Homework o2) {
                return o2.score - o1.score;
            }
        });


        int result = 0;

        // 마지막 마감일의 과제들부터 일정 할당. 단 점수가 높은거 먼저 끝내야함
        int j = 0;
        for(int i = maxDate; i >= 1; i--){

            // 해당 날짜가 마감인 과제들을 모두 Queue에 집어넣음
            while(j < n && homeworks[j].date == i){
                pq.offer(homeworks[j]);
                j++;
            }

            // Queue에서 가장 높은 점수를 얻을 수 있는 현재 날짜에 수행 가능한 과제를 꺼냄
            if(!pq.isEmpty()){
                Homework h = pq.poll();
                result += h.score;
            }

        }

        System.out.println(result);

    }
}

 

1. 앞에서 과제를 마지막 마감일부터 계산해주기 위해서 마감일이 큰(여유로운) 순서대로 정렬하였다.
2. 해당 날짜에 수행할 수 있는 과제들의 후보군을 담아둘 우선순위 큐를 생성한다.
   • 후보군 들 중 가장 획득할 수 있는 점수가 높은 순서대로 꺼낼 수 있도록 정렬을 설정한다.
3. 반복문을 통해서 마지막 마감일부터 1일까지 차례로 수행할 과제를 할당해준다.
   1. 해당 날짜 (i)가 마감일인 과제들을 우선순위 큐에 삽입해주어 후보군에 추가해준다.
   2. 우선순위 큐에서 해당 날짜에 수행할 수 있는 후보군들 중 최대 점수를 얻을 수 있는 과제를 꺼내어 할당해준다. 이를 결과값에 더해준다.
   3. 큐가 비어있으면 수행할 수 있는 과제가 없는 상태이다.
4. 마지막으로 계산한 얻을 수 있는 과제 점수들의 합을 최종 결과값으로 출력한다.

 

---

방법론 다시보기

1. 계산 순서 : 나중 단계에서 처리되어도 되는 순서, 처리되지 못하면 후보군으로 넣을 수 있도록

• 가장 마감일이 늦은 순서 : 당장 처리되지 않더라도 다음 계산의 후보군으로서 사용될 수 있다.

2. 후보군 순서 (우선순위 큐) : 현재 단계에서 후보군들 중 가장 높은 가치를 산출할 수 있는 순서

• 가장 점수가 높은 순서 : 현재 날짜에서 처리할 수 있는 후보군들 중 가장 점수를 선택해야 한다.

 

 

---

전체 코드

class Homework implements Comparable<Homework> {
    int date;
    int score;
    public Homework(int date, int score){
        this.date = date;
        this.score = score;
    }

    @Override
    public int compareTo(Homework o) {
        if(this.date == o.date){
            return o.score - this.score;
        }
        return o.date - this.date;
    }

}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        Homework[] homeworks = new Homework[n];
        int maxDate = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            homeworks[i] = new Homework(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            maxDate = Math.max(homeworks[i].date, maxDate);
        }

        Arrays.sort(homeworks);

        PriorityQueue<Homework> pq = new PriorityQueue<>(new Comparator<Homework>() {
            @Override
            public int compare(Homework o1, Homework o2) {
                return o2.score - o1.score;
            }
        });


        int result = 0;

        // 마감일이 여유로운 날짜의 과제들부터 일정 할당. 단 점수가 높은거 먼저 끝내야함
        int j = 0;
        for(int i = maxDate; i >= 1; i--){

            // 해당 날짜가 마감인 과제들을 모두 Queue에 집어넣음
            while(j < n && homeworks[j].date == i){
                pq.offer(homeworks[j]);
                j++;
            }

            // Queue에서 가장 높은 점수를 얻을 수 있는 현재 날짜에 수행 가능한 과제를 꺼냄
            if(!pq.isEmpty()){
                Homework h = pq.poll();
                result += h.score;
            }

        }

        System.out.println(result);

    }
}

 

 

---

문제 : 강의실 배정 (백준 11000)

 

해당 문제는 결국 강의들을 얼마나 최대한 많이 합칠 수 있느냐가 문제이다.

강의들을 순서대로 합치려고 시도할 때, 지금 당장에는 합쳐질 수 없어도, 후보군으로서 저장해둔 후 나중 순서의 강의와 합치는 것이 가능할 수도 있다.
따라서 해당 문제 유형도 우선순위 큐가 유용하게 사용될 수 있다는 것을 알 수 있다.

 

---

구현

class Lecture implements Comparable<Lecture>{
    int start;
    int end;

    public Lecture(int start, int end){
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Lecture o) {
        if(o.start == this.start){
            return this.end - o.end;
        }
        return this.start - o.start;
    }

    public String toString(){
        return this.start + " " + this.end;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        Lecture[] array = new Lecture[n];


        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            array[i] = new Lecture(start, end);
        }

        Arrays.sort(array); // 강의를 빨리 시작하는 순으로 정렬


        // 현재 강의와 연속해서 진행할 수 있는 후보군들을 담을 우선순위 큐 (끝나는 시간이 빠른 순으로 정렬)
        // 만약 후보와 연속해서 진행할 수 있다면 합쳐서 큐에 저장, 그렇지 않다면 따로 큐에 추가로 저장.
        // 결국 해당 우선순위 큐의 Item의 개수가 강의실의 개수이다.
        PriorityQueue<Lecture> queue = new PriorityQueue<>(new Comparator<Lecture>() {
            @Override
            public int compare(Lecture o1, Lecture o2) {
                if(o1.end == o2.end){
                    return o1.start - o2.start;
                }
                return o1.end - o2.end;
            }
        });

        queue.offer(array[0]); // 맨 처음 시작하는 강의를 강의실에 배정

        for(int i = 1; i < n; i++){ //시작하는 순서대로 계산
            Lecture c = queue.peek(); //가장 끝나는 시간이 빠른 강의 후보 (가장 합칠 수 있는 가능성이 높음)

            // 합치는 것이 가능하다면 합쳐서 큐에 저장
            if(c.end <= array[i].start){
                queue.poll();
                queue.offer(new Lecture(c.start, array[i].end));
            }

            // 합치는 것이 불가능하다면 따로 큐에 저장
            else{
                queue.offer(array[i]);
            }
        }

        System.out.println(queue.size());
    }
}

1. 강의를 시작시간이 빠른 순서대로 이전 순서의 강의들과 합병하는 것을 시도
2. 이전 순서의 강의들은 다음에 계산될 강의와 합쳐질 수 있는 후보군으로서 우선순위 큐에 끝나는 시간이 빠른 순서대로 정렬 
   • 가장 끝나는 시간이 빠른 강의가 다음 차례에 올 강의들과 합쳐질 확률이 가장 높은 강의이기 때문이다. 
   • 합치는 순서는 시작시간 기준이므로 후보군들의 시작시간보다는 무조건 느리다. 따라서 이는 계산할 필요성이 없다.
   • 큐의 최적 후보(A)가 끝나는 시간이 현재 계산중인 강의(B)의 시작 시간보다 빠르다면 합쳐질 수 있다. 
     • 이 경우 (A의 시작 시간, B의 종료 시간)인 새로운 후보군으로 합쳐서 큐에 넣어준다. 이어서 다음 강의와 합쳐질 수 후보군으로서 추가해주기 위함이다. A와 B를 C라는 새로운 강의로 만들어 준다고 생각하면 된다.
   • 이렇게 계산하게 된다면 최대한 밀도있게 강의들을 합칠 수 있다.
3. 결국 큐에 남아있는 병합이 완료된 강의들의 수가, 최소 필요한 강의실의 수가 된다.

 

---

방법론 다시보기

1. 계산 순서 : 나중 단계에서 처리되어도 되는 순서, 처리되지 못하면 후보군으로 넣을 수 있도록

• 시작 시간이 빠른 강의들 순서 : 당장 합쳐지지 않더라도, 이후의 강의들과 합쳐질 수 있도록 후보군으로 사용된다. 이후 병합하는 단계에서 시작시간을 고려하지 않기 위해서 미리 시작 시간 순서대로 정렬하여 계산을 시작한다.

2. 후보군 순서 (우선순위 큐) : 현재 단계에서 후보군들 중 가장 높은 가치를 산출할 수 있는 순서

• 종료 시간이 빠른 강의들 순서 : 후보군들 중 종료 시간이 가장 빠른 강의가 현재 계산 시점에서 합쳐질 가능성이 가장 높은 강의(가치가 높음)이다.

 

 

---

문제 : 보석 도둑 (백준 1202)

수용량이 다른 가방들이 주어지고, 각각의 무게와 가치를 가지는 보석들이 있을 경우, 최대 가치의 보석들을 가방에 담아가야 하는 문제이다.

1. 가장 가벼운 가방부터 시작해서 수용할 수 있는 보석 중 최대한 가치있는 것을 챙겨두어야 한다. 
   • 따라서 계산 순서는 가벼운 가방부터 계산해야 한다.
2. 보석은 가장 가벼운 가방부터 계산하게 되므로, 해당 가방이 수용할 수 있는 보석들을 알아낼 수 있도록 해야 한다. 따라서 무게(M) 순서대로 정렬해두어 현재 계산중인 가방이 수용할 수 있는 보석들을 얻어낼 수 있도록 하자. 챙기지 못하더라도 후보군에 넣어두고 다음 가방이 이를 수용할 수 있다
   • 계산 순서에 따라서 보석의 순서도 가벼운 순서대로 정렬해둔다.
   • 가벼운 보석은 나중에 수용량이 큰 가방에 들어갈 수 있다. 만약 반대로 무거운 가방부터 계산한다면 무거운 보석은 나중에 가벼운 가방에 들어갈 수 없다.
3. 현재 계산중인 가방에 챙길 수 있는 보석 후보군을 저장해 둘 우선순위 큐는 가치가 최대인 보석 순서대로 정렬해둔다.

 

 

이를 토대로 예제 입력 2를 경우로 한번 생각해보면 다음과 같은 흐름이 나오게 된다.

• 보석(무게, 가치) : A(1, 65), C(2, 99), B(5, 23)
• 가방(수용량) : Y(2), Z(10)

가방	후보군에 추가된 보석	가방에 넣을 보석	후보군 (우선순위 큐)
Y(2)	A(1, 65), C(2, 99)	C(2, 99)	C(2, 99), A(1, 65)
Z(10)	B(5, 23)	A(1, 65)	A(1, 65), B(5, 23)

 

결과 : 164

 

 

---

구현

class Jewelry implements Comparable<Jewelry>{
    int value;
    int weight;

    @Override
    public int compareTo(Jewelry o) {
        if(o.weight == this.weight){
            return o.value - this.value;
        }
        return this.weight - o.weight;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());


        // 보석의 무게가 낮은 순서대로 정렬 -> 같으면 가치가 높은 순서대로 정렬
        ArrayList<Jewelry> jewelries = new ArrayList<>();

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            Jewelry j = new Jewelry();
            j.weight = Integer.parseInt(st.nextToken());
            j.value = Integer.parseInt(st.nextToken());
            jewelries.add(j);
        }

        Collections.sort(jewelries);

        ArrayList<Long> bags = new ArrayList<>();
        for(int i = 0; i < k; i++){
            st = new StringTokenizer(br.readLine());
            bags.add(Long.parseLong(st.nextToken()));
        }

        // 수용 무게가 낮은 가방 순으로 정렬 -> 가장 낮은 가방부터 가장 높은 가치의 보석을 챙길 수 있도록
        Collections.sort(bags);

        long total = 0;

        // 현재 가방에 챙길 수 있는 보석들의 후보군 -> 가치가 높은 보석 순으로 정렬
        PriorityQueue<Jewelry> queue = new PriorityQueue<>(new Comparator<Jewelry>() {
            @Override
            public int compare(Jewelry o1, Jewelry o2) {
                if(o2.value == o1.value){
                    return o1.weight - o2.weight;
                }
                return o2.value - o1.value;
            }
        });


        int index = 0;
        for(int i = 0; i < k; i++){
            // 현재 가방의 무게에서 수용할 수 있는 보석을 후보군에 추가함
            for(int l = index; l < n; l++){
                Jewelry j = jewelries.get(index);
                if(j.weight > bags.get(i)){
                    break;
                }
                queue.add(j);
                index++;
            }
            // 우선순위 큐의 맨 첫번째 -> 가방이 수용 가능한 후보군들 중 가격이 제일 높은 것
            if(!queue.isEmpty()){
                Jewelry j = queue.poll();
                total += j.value;
            }
        }

        System.out.println(total);
    }
}

 

방법론 다시보기

1. 계산 순서 : 나중 단계에서 처리되어도 되는 순서, 처리되지 못하면 후보군으로 넣을 수 있도록

• 가벼운 보석, 수용량이 작은 가방 순서 : 당장 처리되지 않더라도 다음 계산의 후보군으로서 사용될 수 있다.

2. 후보군 순서 (우선순위 큐) : 현재 단계에서 후보군들 중 가장 높은 가치를 산출할 수 있는 순서

• 가장 가치가 높은 순서 : 후보군들 가운데 현재 계산에서 가장 높은 가치를 챙길 수 있는 보석을 꺼내야 하기 때문이다.

 

 

 

---