Greedy-Algorithm (탐욕 알고리즘)

728x90

탐욕 알고리즘은 현재 사용 가능한 최상의 옵션을 선택하여 문제를 해결하는 접근 방식

하향식 접근 방식으로 작동한다. 이 알고리즘은 모든 문제에 대해 최상의 결과를 생성하지 않을 수 있다.

문제에 다음 속성이 있는 경우 사용할 수 있는지 여부를 결정할 수 있다.

1. 그리디 초이스 속성

한 번 선택한 이전 단계를 다시 고려하지 않고 각 단계에서 최선의 선택을 선택하여 문제에 대한 최적의 솔루션을 찾을 수 있다면 탐욕적인 접근 방식을 사용하여 문제를 해결할 수 있습니다. 이 속성을 탐욕 선택 속성이라 한다.

2. 최적의 하부구조

문제에 대한 최적의 전체 솔루션이 하위 문제에 대한 최적의 솔루션에 해당하는 경우 탐욕적인 접근 방식을 사용하여 문제를 해결할 수 있다. 이 속성을 최적 하부 구조라고 한다

위 두개에 특성을 가지는 문제들을 해결하는 데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을 때에는 사용할 수 있다
하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.
어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

근사알고리즘은 다음 관련 문제가 나왔을때 정리해보도록 하겠다.

(Python)백준 알고리즘 2839번: 설탕 배달

문제 출처:https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에

windy7271.tistory.com

출처: