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

✋ (알고리즘) Greedy (탐욕 그리디 알고리즘)이란

 

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

Greedy 알고리즘

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

 

 

 

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

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

그리디 알고리즘은 동적계획법에서 시간소요가 크기 때문에 이를 보완하기 위해서 도출된 알고리즘입니다. 그리디 알고리즘은 최적의 답을 도출하는 알고리즘이 아닙니다. 하지만 몇몇 케이스에서는 통하는 유형이 있습니다. 

 

 

 

 

 

📌 Knapsack Problem (배낭 문제)

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

 

여기서 조건이 주어집니다. 무거운 물건의 경우 쪼개서 넣을 수 있습니다. 그럴 경우, 무게 대비 가치가 높은 것들을 넣어야 할 것입니다. 배낭에 담은 물건의 가치의 최대값을 구하는게 목적이라고 합시다.

 

수도코드 (Pseudo Code)를 짜보면,

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

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

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

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

 

즉, 그때 그때마다 최선의 선택을 하는 것이 결과론적으로도 최선의 답입니다.