[Algorithm/Java] greedy 그리디 알고리즘 (탐욕법)

그리디 (greedy) 알고리즘

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체에서 최선의 선택지라고 가정하는 알고리즘이다.

빠르게 근사치를 계산할 수 있지만, 결과적으로 전체 케이스 중 최적의 값이 아닐 수도 있다.

따라서 이 문제를 그리디 알고리즘으로 해결해도 될지 고민해 보는 것이 필요하다.

 

그리디 알고리즘 수행 과정

1. 해 선택

현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.

2. 적절성 검사

현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.

3. 해 검사

현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 

만약 전체 문제를 해결할 수 없다고 판단되면 다시 1번으로 돌아가 과정을 반복한다.

 

이처럼 그리디 알고리즘을 수행하는 과정은 어떻게 보면 간단하다. 그러나 모든 문제에 동일하게 적용할 수 없고, 수행 과정보다는 문제를 이해하는 것이 더 중요하다.

---

예제

여러개의 활동이 있고, 각 활동의 시작/종료 시간이 주어졌을 때 각 활동을 가장 효율적으로 사용하는 방법을 구하는 문제이다.

 

강의실 배정, 회의실 배정, 스케쥴링 등 주어진 자원을 가장 효율적으로 사용할 수 있는 방법을 구하는 문제로 많이 응용된다.

 

주어진 문제

아래와 같이 어떤 활동의 시작시간과 종료시간이 주어졌다.

한 사람이 이 활동을 최대한 여러 개를 할 수 있는 경우를 찾아라.

(종료시간이 x인 활동 이후에 시작시간이 x인 활동을 바로 할 수 있다.)

종료시간 기준 정렬

아래와 같이 종료 시간을 기준으로 정렬한다.

종료시간이 가장 빠른 활동부터 하고, 그때그때 그 활동 이후에 할 수 있는 활동들을 골라서 하면 된다.

결과는 C - B - E 순으로 활동을 할 때 가장 많은 활동을 할 수 있게 된다.

---

그리디 문제

2023.06.26 - [코딩테스트] - [백준/Java] 11000번 : 강의실 배정 / 그리디 알고리즘

[백준/Java] 11000번 : 강의실 배정 / 그리디 알고리즘