그리디 알고리즘
정의 및 특징
- 현재의 상황에서 가장 좋은 것만 고르는 방법
- 탐욕법이나 욕심쟁이 알고리즘이라고도 불리며, 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
- 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
알고리즘의 정당성
- 문제 속 좋은 것을 선택하는 기준이 제시되어 있다면 고려해볼 수 있는 알고리즘으로, 기준을 통해 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야한다.
- 어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해 보는 것도 방법이다.
참고자료
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈
개발하는 강아지