[Algorithm] 그리디 알고리즘 中, 활동 선택 문제 (ft. BOJ1931_회의실배정.java)

민지·2024년 1월 3일

Algorithm

목록 보기

5/8

들어가며

그리디 알고리즘을 활용할 수 있는 문제에서 브루트포스로 풀다가 시간초과가 났다.
나름 정렬을 했다고 생각했는데, 정렬 기준을 잘못 잡았다는 게 문제였다.
그리고 활동 선택 문제라는 분류가 그리디 알고리즘의 대표적인 문제임을 알고 포스팅을 작성해보기로 한다.

그리디 알고리즘

탐욕 알고리즘(Greedy algorithm)은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

최적이라는 보장은 없다.

활동 선택 문제(Activity Selection Problem)

활동 선택 문제에서 그리디하게 푼다는 것.
= 가능한 활동시간 내에서 최대한 많은 활동을 할 수 있도록 활동들의 집합을 고르는 것.

시작시간과 종료시간으로 표시된 일련의 활동이 주어지면, 주어진 시간 내에 수행할 충돌하지 않는 활동을 선택하는 것과 관련된 조합 최적화 문제.

가정 상황

한 번에 하나의 활동만 수행할 수 있다.
수행할 수 있는 최대 활동 수를 선택한다.
활동에 가중치가 존재하지 않는다. (이는 동적 프로그래밍(DP)를 사용)

전형적인 유형

각각 고유한 시간 요구 사항(시작 및 종료 시간)이 있는 여러 경쟁 이벤트를 위한 공간을 예약하는 문제.
한 번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제아너된 활동들 중 가장 많은 활동을 처리할 수 있는 스케줄을 짜는 문제.

이런 유형은 그리디 알고리즘을 사용해 솔루션을 찾으면 항상 최적의 솔루션이 나온다.

선택 방법

제일 먼저 종료되는 활동을 선택한다.
해당 활동과 양립가능한 활동들의 subproblem에서 또 다시 제일 먼저 종료되는 활동을 선택한다.

이유

제일 먼저 끝나는 활동을 선택했을 때, 남은 subproblem에서 최대한 많은 활동을 고를 수 있다.

수도 코드1: 재귀적 관점

수도 코드2: 반복문 관점

대표 문제)BOJ 1931 회의실 배정

java로 풀었다.

기존 코드(시간초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static class Time {
        int start;
        int end;

        Time(int start, int end) {
            this.start = start;
            this.end = end;
        }
        int getStart() {
            return start;
        }
        int getEnd() {
            return end;
        }

    }
    static int N;
    static Time[] times;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        times = new Time[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            times[i] = new Time(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(times, Comparator.comparing(Time::getEnd)
                                     .thenComparing(Time::getStart));

        solve(0, 0, 0);
    }

    private static void solve(int cnt, int idx, int endTime) {

        if(endTime >= times[times.length-1].end) {
            if(idx < times.length && times[idx].start == times[idx].end) cnt++;
            System.out.println(cnt);
            System.exit(0);
        }

        for (int i = idx; i < N; i++) {
            if(endTime <= times[i].start) {
                solve(cnt+1, idx+1, times[i].end);
            }
        }
    }
}

통과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static class Time {
        int start;
        int end;

        Time(int start, int end) {
            this.start = start;
            this.end = end;
        }
        int getStart() {
            return start;
        }
        int getEnd() {
            return end;
        }

    }
    static int N, ans;
    static Time[] times;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        times = new Time[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            times[i] = new Time(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        /*
        끝나는 시각을 빠른 순으로 정렬해준다.
        단, 끝나는 시각이 동일할 경우 시작 시각이 빠른 순으로 정렬한다.
        그 후에는 endTime을 정해 시작 시간이 그 이후일 경우를 세어주며 갱신한다.
        */
        Arrays.sort(times, Comparator.comparing(Time::getEnd)
                                     .thenComparing(Time::getStart));

        int endTime = 0, cnt = 0;
        for (int i = 0; i < N; i++) {
            if(endTime <= times[i].start) {
                endTime = times[i].end;
                cnt++;
            }
        }
        System.out.println(cnt);

    }
}