탐욕법(Greedy Method)

📢  탐욕법

• 탐욕법(Greedy Method) : 일반적인 알고리즘 설계 기법 가운데 하나
  
  👉 구성(Configuration) : 다양한 선택, 모음, 또는 찾아야 할 값들
  👉 목표(Objective) : 구성에 할당된 점수가 존재하며, 이를 최대화 또는 최소화해야 하는 상황
  
  
• 탐욕적 선택 속성(Greedy-Choice Property)을 가진 문제에 적용할 경우 가장 잘 맞는다.
  
  👉 출발 구성으로부터 시작하여 지속적인 지역적 향상을 통해, 전체 최적해를 항상 찾을 수 있다.
  
  
• 예시
  
  👉 잔돈 거스르기
  👉 부분 배낭 문제
  👉 최소신장트리
  
  

📢  잔돈 거스르기 문제

• 구성
  
  👉 거슬야 할 금액 정보
  👉 종류 여러 개의 동전들
  
  
• 목표
  
  👉 동전 수를 최소화
  
  
• 탐욕해
  
  👉 가능하 항상 제일 큰 동전으로 거슬러준다.
  
  만약, 이 문제가 탐욕적 선택속성을 가졌다면 탐욕해는 최적해가 된다.
  
  
• 예시
  
  👉 예시 1. 동전 종류가 32원, 8원, 1원 인 경우
  
  탐욕적 선택 속성 : 있음(O) = 왜냐면, 32원 이상의 금액은 32원을 빼고는 최소 수의 동전으로 만들 수가 없기 때문
  ( 8원을 넘지만 32원에 못 미치는 금액에 대해서도 마찬가지 )
  
  👉 예시 2. 동전 종류가 30원, 20원, 5원, 1원인 경우
  
  탐욕적 선택 속성 : 없음(X) = 왜냐면, 40원은 두 개의 20원만으로 만들 수 있으나, 탐욕해는 세 개의 동전을 택하기 때문이다. ( 3개의 동전 = 30원 + 5원 + 5원 )
  
  

 

📢  부분적 배낭 문제

• 구성 : N 항목의 집합 S = 각 항목 i는 다음을 가진다.
  
  👉 b(i) : 양수의 이득
  👉 v(i) : 양수의 부피
  
  
• 목표
  
  👉 최대 부피 한도 V 내에서, 최대의 총 이득을 주는 항목들을 선택한다.
  
  
• 부분적 배낭 문제(The Fractional Knapsack Problem) : 각 항목의 일부만을 취할 수 있는 문제
  
  👉 x(i)가 항목 i를 덜어 담는 양을 표시한다고 하면
  👉 목표 : (i∈S) ∑ b(i) ( x(i) / v(i) )를 최대화
  👉 제약 : (i∈S) ∑ x(i) ≤ V
  
  
• 예시
  
  👉 구성 : n 항목의 집합 S = 각 항목 i는 다음을 가진다.
  
  b(i) : 양수의 이득
  v(i) : 양수의 부피
  
  👉 목표 : 최대 부피 한도 V 내에서, 최대의 총 이득을 주는 항목들을 선택

항목	A	B	C	D	E	탐욕해(전체배낭 10ml)
이득	32	15	27	5	4	B ( 3ml )
부피	8ml	3ml	9ml	5ml	2ml	A ( 7ml )
가치 (ml 당)	4	5	3	1	2	총이득 = 43 ml

• 설명 : 각 항목의 최소단위인 1ml당 가치를 봤을 때, 우선적으로 가치가 높은 B부터 3ml을 다 담고, 나머지 A 전체 8ml 에서 7ml을 담은 것이 가장 최적의 이득을 취할 수 있다.
  이것이 가능한 이유는, 부분적으로, 항목을 나눌 수 있기 때문이다.

📢  0-1 배낭 문제

• 0-1 배낭 문제 (또는 all-or-nothing knapsack problem) : 각 항목의 일부만을 취할 수는 없는 문제
• 0-1 배낭 문제는 탐욕적 선택 속성을 만족하지 않는다.
• 예 : 최적해는 이득 36을 가져다 주는 { A,E }지만, 탐욕해는 이득 = 24를 가져다 주는 { B,E,D }를 고른다.

항목	A	B	C	D	E	탐욕해(전체배낭 10kg)
이득	32	15	27	5	4	B ( 3kg )
무게	8kg	3kg	9kg	5kg	2kg	E ( 2kg )
가치 (kg 당)	4	5	3	1	2	D ( 5kg )
						총 이득 = 24 kg