그리디 알고리즘 정의
탐욕 혹은 욕심쟁이 알고리즘이라고도 하며, 탐욕이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 따로 알고리즘의 사용 방법을 알고 있어야 한다거나, 외워야 하는 건 없다.
코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시 말해 특정한 문제를 만났을 때 단순히 현 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.
대표적인 문제로는 거스름돈이 있다.
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
문제 설명 : 문제를 간단히 설명하면 거스름돈을 동전으로 주는데 이때 동전의 개수가 최소가 되어야 한다.
그렇다면 이 문제를 푸는 방법은 뭘까?
코드를 작성하기 전에 어떻게 하면 동전의 개수가 최소가 되는지에 대해 생각해야 한다. 답은 바로 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.
※ 자세한 건 https://dev-cloud.tistory.com/129
대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. 따라서 그리디 알고리즘은 문제를 많이 풀어보는 것이 중요하다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] DP (Dynamic Programming, 동적 계획법) (0) | 2023.09.25 |
|---|---|
| [알고리즘] 에라토스테네스의 체 (1) | 2023.09.23 |
| [알고리즘] BFS/DFS 알고리즘 (그래프 탐색) (0) | 2023.05.15 |
| 누적 합(Prefix Sum, 부분 합) (0) | 2023.03.27 |
| Brute Force (완전 탐색 알고리즘) (0) | 2022.08.05 |