각 단계에서 그 시점에 가장 좋아 보이는 선택을 하나 고르고, 나중에 다시 검토하지 않고 해를 조립하는 알고리즘 설계 방법. 빠르고 단순하지만, 최적해를 얻을 수 있는 것은 동전의 조합이 일본 동전 같은 경우나 최소 신장 트리의 크루스칼 알고리즘처럼 문제가 특별한 성질을 가질 때로 한정된다.
일본어 명칭: 貪欲法
탐욕 알고리즘(Greedy Algorithm)은(는) 자료 구조와 알고리즘 등 1개 분야의 연습 문제 2개에 나와요.
분야: 자료 구조와 알고리즘
정답: B. 탐욕 알고리즘으로는 3개가 되어, 최소인 2개가 되지 않는다
탐욕 알고리즘에서는 먼저 6엔을 1개 쓰고, 나머지 2엔을 1엔 2개로 지불하므로 3개입니다. 그러나 4엔을 2개 쓰면 2개로 지불할 수 있습니다. 이처럼 탐욕 알고리즘은 그 시점에서 가장 좋은 선택을 쌓아 갈 뿐이므로, 동전의 조합에 따라서는 최적이 되지 않습니다. 동적 계획법으로 '0엔부터 8엔까지 각 금액을 지불하는 최소 개수'를 작은 금액부터 차례로 표로 만들면 반드시 최소 개수가 구해집니다. 덧붙여 1, 5, 10, 50, 100, 500엔 같은 일본 동전의 조합에서는 탐욕 알고리즘으로도 항상 최소가 됩니다.
탐욕 알고리즘에서는 먼저 6엔을 1개 쓰고, 나머지 2엔을 1엔 2개로 지불하므로 3개입니다.
1엔, 4엔, 6엔의 3종류 동전으로 8엔을 지불한다. 큰 동전부터 쓸 수 있는 만큼 쓰는 탐욕 알고리즘으…무게당 가치가 높은 순서로 채우는 탐욕 알고리즘에서는 무게 2와 3(가치 7)을 넣은 뒤 남은 용량 3에 들어갈 물건이 없어 7에서 멈춥니다.
용량 8인 배낭에 (무게, 가치)가 (2, 3), (3, 4), (4, 5), (5, 6)인 4개의 물건 …동적 계획법(Dynamic Programming) 깊이 우선 탐색(Depth-First Search) 너비 우선 탐색(Breadth-First Search) 다익스트라 알고리즘(Dijkstra's Algorithm) 스택(Stack) 시간 복잡도(Time Complexity) 안정 정렬(Stable Sort) 연결 리스트(Linked List) 이진 탐색 트리(Binary Search Tree) 이진 탐색(Binary Search)