그리디 알고리즘의 정의
그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.
즉, 현재 내가 내린 선택이 나중에 어떤 결과를 가져올지는 고려하지 않고, 무조건 지금 가장 저렴한 선택, 가장 빠른 선택 혹은 가장 가치 있는 선택을 내리는 것입니다. 그래서 그리디라는 이름이 붙여졌습니다.
그리디 알고리즘의 특징
그리디 알고리즘은 항상 최적의 해를 보장하지는 않습니다. 항상 최적의 해를 보장하지 않기 때문에 근사 알고리즘이라고도 불립니다.
그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.
쉽게 설명하자면, 그리디 알고리즘을 사용할 수 있는 첫 번째 조건은 현재의 선택이 미래의 선택에 영향을 주지 않는 경우입니다. 예를 들어, 서울에서 대전, 대전에서 부산으로 가는 최소 비용을 계산하는 문제에서, 서울에서 대전까지 가는 경로가 대전에서 부산까지의 경로에 영향을 미치지 않는다면 그리디 알고리즘을 사용할 수 있습니다.
두 번째 조건은 문제의 일부분에 대한 최적의 해가 전체 최적화를 이루는 경우입니다. 서울에서 부산까지의 최소 거리를 구하는 문제를 예로 들면, 서울에서 대전까지의 최소 거리와 대전에서 부산까지의 최소 거리를 더하면 전체 최적화가 됩니다.
그리디 알고리즘의 전략
그리디 알고리즘을 효과적으로 사용하기 위해서는 정렬이 핵심입니다. 예를 들어, 회의실 배정 문제를 생각해 봅시다. 여러 개의 회의 요청이 주어졌을 때, 겹치지 않게 최대한 많은 회의를 진행하려면 종료 시간을 기준으로 정렬하는 것이 좋습니다. 이렇게 하면 가장 빨리 끝나는 회의부터 진행하여 최대한 많은 회의를 진행할 수 있습니다.
그리디 알고리즘의 활용
그리디 알고리즘은 코딩 테스트에서 자주 사용됩니다. 그 이유는 속도 때문입니다. 다이나믹 프로그래밍보다 빠르기 때문에, 최적화가 보장되는 경우에 그리디 알고리즘을 사용하면 더 빠르게 문제를 해결할 수 있습니다.
참조자료
https://coding-grandpa.tistory.com/138
https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
