(알고리즘) Greedy (탐욕 알고리즘)

(알고리즘) Greedy 알고리즘이란

선택의 순간에 그 상황에서의 최적의 선택안만 골라 최종적인 결과에 도달하는 알고리즘

Greedy Algorithm (큰 합 구하기)

파란색은 그리디를 통해 도출한 답(90), 결론적으로 그리디를 통해서는 최적의 답을 고를 수 없습니다. 따라서 그리디가 최적의 답을 얻는 데 좋은 알고리즘은 아니다.

그리디 알고리즘을 사용하는 이유

여러 가지 제약사항을 고려하는 게 아니라 오로지 그 순간에 가장 최적의 선택을 하기 때문에 계산 속도가 빠르다.

그리디 알고리즘은 동적계획법에서 시간소요가 크기 때문에 이를 보완하기 위해서 도출된 알고리즘. 

그리디 알고리즘이 몇몇 케이스에서는 통하는 유형이 있다.

Knapsack Problem

배낭문제란 간략하게 말하면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 문제이다.

여기서 그리디 조건은 무거운 물건의 경우 쪼개서 넣을 수 있다는 것. 그럴 경우, 무게 대비 가치가 높은 것들을 넣어야 한다. 

코드를 순서대로 짜게되면 다음과 같다.

1. 배열안에 가치와 무게를 지닌 물건 정보가 들어있다면, 무게 대비 가치 순으로 배열을 정렬합니다.

2. 순차적으로 가치가 높은 물건부터, 물건 무게가 배낭 무게 제한 이하일 경우 배낭에 넣습니다.

3. 물건 무게가 제한 초과를 할 경우, 잘라서 배낭에 넣습니다.

4. 배낭에 넣은 물건의 가치의 총합을 답으로 출력합니다.

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

근사 알고리즘이란 최적화 문제에 대해 빠르게 근사값을 구하는 알고리즘이다. 최적의 해는 도출한다는 보장이 없지만, 빠른속도로 근사치에 해당하는 값을 구할 수 있다.