[그리디 알고리즘]

<그리디 알고리즘>

어떻게 정렬해야 미래의 선택을 따져보지 않고 현재만 고려해도 최적의 해를 구할 수 있을까 라는 답을 생각해봐야 합니다.

-그리디 알고리즘의 대표적 문제 유형으로는 활동 선택 문제나 거스름돈 문제 등이 있다.

회의실 정하기 백준 문제 중

가장 빨리 끝나는 회의부터 먼저 진행해야 가장 많은 회의를 진행할 수 있다라는 결론을 내릴 수 있다.

그러므로 입력받은 정보들을 종료 시간을 기준으로 오름차순으로 정렬하고 제일 처음부터 진행 가능한 회의들을 하나씩 진행합니다. 그렇게 하나를 진행하고 나면 해당 종료 시간 전에 시작하는 회의는 진행이 불가능하니 무시하고 진행 가능한 회의들을 또 진행하며 반복하는 겁니다.
그래서 종료 시간을 기준으로 잘 정렬하기만 하면 현재의 선택이 무조건 최적의 해라고 보장할 수 있고 그렇다면 미래의 조건과 선택을 고려하지 않아도 최적의 해를 보장할 수 있는 겁니다.

 

그리디 알고리즘을 사용하는 이유
: 단순히 정렬을 잘해서 빠르게 문제를 푼다라는게 핵심이다보니,
문제마다 다 다른느낌입니다. 즉 이 그리디 알고리즘은 많이 익혀서 많이 풀어야만 문제를 잘 풀 수 있습니다. 

이 그리디 알고리즘은 다이나믹 프로그래밍의 사촌 같은 존재로. DP 보다 더 빠르다는 특징이 있습니다.

그리디 알고리즘 문제 추천