Greedy 접근법 - 백준 1931번

Greedy 접근법이란 모든 경우(단계)에 대해 최적의 해를 선택하면 그것이 결국 전체의 최적해가 된다는 접근법이다.

Greedy 접근법의 대표문제라고 할 수 있는 회의실 배정문제를 풀어보았다. 

 

다음과 같은 문제에서 Greedy 접근법이 성립하는 이유에 대한 증명 - 귀류법을 이용한 증명

cf) 귀류법: 가정을 부정하여 모순을 보임으로써 가정에 대한 결론이 맞음을 보이는 방식

 

Greedy한 선택이 최적해를 포함하지 않는다고 가정 - 결론 부정

최적해가 존재함은 자명하다. 따라서 그렇다면 Greedy하지 않은 선택이 최적해를 포함할 것이다. 

 

우리가 가정한 최적해의 제일 첫 회의의 끝나는 시간보다 항상 제일 먼저 끝나는 회의의 끝나는 시간이 앞선다. 

따라서 그 회의 대신, 제일 먼저 끝나는 회의를 선택하는 것이 최적해이다. 이는 'Greedy하지 않은 선택이 최적해를 포함할 것이다'에 모순되며, 따라서 기존의 가정인 'Greedy한 선택이 최적해를 포함한다'가 성립한다. 

 

따라서 회의실 문제에 대한 알고리즘을 다음과 같이 설정하였다. 

1. 회의개수, 시작시간, 종료시간을 입력받고 종료시간을 기준으로 배열을 정렬해준다. 

2. 가장 빨리 끝나는 회의를 순차적으로 선택하는것이 최적해이므로, 가장 빨리 끝나는 회의를 선택해준다. 

3. 첫번째 선택한 회의의 종료시간을 기준으로, 그 다음 회의를 선택해준다. 

4. 이 과정을 반복한다. (선택된 회의의 개수를 기록하고, 출력해준다.) 

 

실제 작성한 코드는 아래와 같다. 

회의개수, 회의 시작시간, 회의 종료시간을 사용자로부터 입력받고 2차원배열에 회의시작시간과 종료시간을 저장한다.

이번 문제를 해결하면서 새롭게 알게된 부분은 Arrays.sort라는 java의 내장함수이다. 이 함수는 기본적으로는 일차원 배열에 대해서 오름차순으로 정렬해주는데, 위와같은 방법으로 comparator를 이용하여서 원하는 정렬방식과 정렬대상을 설정해줄 수 있음을 알게 되었다. 위의 함수는 0번째 인덱스가 아닌 1번째 인덱스에 대해 오름차순으로 배열을 정렬해주도록 sort함수를 작성해준 것이다. 만약 내림차순으로 정렬하고 싶다면 t2[]-t1[]의 방식으로 코드를 작성해주면 된다.

 

출력은 아래와 같이된다.