탐욕 알고리즘 (Greedy Algorithm)
date
Apr 18, 2024
slug
greedy-algorithm
status
Published
tags
Algorithm
summary
type
Post
단순하고 무식하게 문제를 해결하는 알고리즘을 탐욕 알고리즘이라고 한다.
매 순간 가장 좋아보이는 것을 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
책에서는 거스름돈을 예시로 들고 있다. - 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제라고 한다.
단순히 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.
탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때 매우 효과적이고 직관적이다.
그러나 해법을 찾았을 때 우선 정당한 방법인지 검토해야 한다.
위 예시를 그리디 알고리즘으로 풀 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수라서 작은 단위의 동전들을 종합했을 때도 다른 해가 나올 수 없기 때문이다.
이렇게 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.