본 내용은 하단 참고 링크의 블로그로 공부하고 기록을 위해 작성하였습니다.
👨🏻💻 그리디(Greedy) 알고리즘?
그리디 알고리즘을 한국어로 번역하면 탐욕, 욕심쟁이 알고리즘이라고 한다.😯
지금 가장 최적인 답을 근시안적으로 택하는 알고리즘. 즉, 관찰을 통해서 범위를 줄여나가는 알고리즘이다.
👨🏻💻 문제를 해결하는 방법
🧐 이상적인 풀이
선택절차: 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
적절성 검사: 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.
해답 검사: 구현해서 문제를 통과한다.
🧐 현실적인 풀이
- 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
- 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다.
- 믿음을 가지고 구현해서 문제를 통과한다.
실제 코딩 테스트는 시간이 촉박하다. 수학 문제를 증명하는 것 처럼 꼼꼼하게 증명해 나가기엔 어려움이 있다. 그래서 믿는 것이다.
👨🏻💻 그리디 알고리즘을 적용하기 위한 성립 조건
그리디 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 속성(Greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.
탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.
🧐 탐욕적 선택 속성(Greedy choice property)
- 앞의 선택이 이후의 선택에 영향을 주지 않는다.
🧐 최적 부분 구조(Optimal Substructure)
- 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 최적의 근사값을 빠르게 도출할 수 있는 장점을 가지고 있다.
👨🏻💻 근사 알고리즘(Approximation Algorithm)?
어떤 최적화 문제에 대한 해의 근사값을 구하는 것을 의미한다.
이것은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다.
언제나 최적해를 구할 수 있는 문제: 매트로이드. 실용적인 문제 풀이 방안이 될 수 있다.
🔗 Reference
https://blog.encrypted.gg/975
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/
https://www.acmicpc.net/problem/11047 - BOJ11047
