이 글은 나동빈님의 이것이 취업을 위한 코딩 테스트다 with 파이썬 책을 정리한 내용입니다.
그리디 알고리즘이란?
그리디(Greedy) 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
코딩테스트의 그리디 알고리즘
코딩 테스트에서 볼 그리디 알고리즘은 다른 알고리즘에 비해 상대적으로 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다.
보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 '창의력' 즉, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용해야 하므로 자주 정렬 알고리즘과 짝을 이뤄 출제된다.
그리디 알고리즘의 정당성
그리디 알고리즘으로 문제를 풀었을 경우 해법이 정당한지 검토해야 한다.
대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한 지 검토할 수 있어야 답을 도출할 수 있다.
ex) 거스름돈
- 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수여서 작은 단위의 동전들을 종합해 다른 해가 나올 수 없어야 한다.
- 800원을 거슬러 줘야 하는 경우 500, 400, 100 단위라면 500, 100, 100, 100 보다 400, 400이 더 적은 수로 거슬러 주는 경우이다.
썸네일 출처
Pixabay로부터 입수된 mohamed Hassan님의 이미지 입니다.
