Greedy 알고리즘

그리디 알고리즘의 핵심 가정

현재 순간의 최적 선택이 전체에서도 최적일 것이다 라는 가정.

현재 상황에서 가장 좋아 보이는 선택(즉, 가장 이득이 되는 선택)을 반복적으로 하는 알고리즘 설계 기법이다.

이 방식은 전체적인 최적해를 보장하지는 않지만, 문제의 특성에 따라 최적해를 구할 수 있는 경우도 많다.

 

사용 조건

1. 탐욕적 선택 속성 : 이전의 선택이 이후 선택에 영향을 주지 않음
2. 최적 부분 구조 : 전체 문제의 최적해가 부분 문제의 최적해로 구성됨

 

탐욕적 선택 속성이란?

현재의 순간 최적 선택이, 전체 최적해의 일부가 될 수 있는가?

 

의미 : 어떤 국소적인 선택(가장 좋은 선택)을 했을 때, 나중의 선택들에 악영향을 주지 않으며, 결국 전체에서도 최적해로 이어질 수 있어야 함. 한마디로, 이전의 선택이 이후의 선택 가능성이나 품질에 영향을 주지 않아야 함.

 

 확인 방법 : 가능한 여러 선택지 중 가장 좋은 것만 선택했을 때, 전체 최적해로 이어지는지 증명 또는 반례 확인

 

예시 : 동전 거스름돈 문제

항상 큰 동전부터 선택해도 남은 금액이 그 다음 동전으로 정확히 표현 가능하다면, 이 속성이 성립한다.

 

 

 

최적 부분 구조란?

문제를 더 작은 부분 문제로 나누고, 이 부분 문제들의 최적해를 모아서 전체 최적해를 만들 수 있는가?

 

의미 : 문제를 쪼갰을 때 각 부분 문제를 최적으로 해결하고, 이들을 결합한 전체도 최적이 되는 구조여야 함.

 

확인 방법 : 문제를 분할해보고, 그 부분 문제의 최적해를 조합했을 때 전체 문제의 최적해가 나오는지 논리적으로 설명하거나 증명

 

예시 : 회의실 배정

끝나는 시간이 빠른 회의를 선택하는 것이, 전체 활동 수를 최대화하는 데 항상 도움이 됨. 남은 시간 동안의 선택도 같은 전략을 적용해 부분 최적해들이 전체 최적해를 구성함.

 

 

그리디 알고리즘 문제풀이들

https://chabin37.tistory.com/96

[JAVA] 백준 1931 회의실 배정

 

 

https://chabin37.tistory.com/98

[JAVA] 백준 1700 멀티탭 스케줄링

 

https://chabin37.tistory.com/99

[JAVA] 백준 2569 짐정리

 

https://chabin37.tistory.com/100

[JAVA] 백준 1715 카드 정렬하기

https://chabin37.tistory.com/101

[JAVA] 백준 2322 아령

https://chabin37.tistory.com/105

[JAVA] 백준 2457 공주님의 정원

https://chabin37.tistory.com/127

[JAVA] 백준 2413 비슷한 순열