[알고리즘] Greedy Algorithm (탐욕 알고리즘)

🔅 Greedy Algorithm (탐욕 알고리즘)이란?

➡️ 선택의 순간마다 눈앞에 보이는 최적의 상황만을 쫓는 알고리즘

➡️ 최적해를 구하는게 탁월하다

❕ 순간마다의 선택은 그 순간에 대해서는 최적이지만, 선택들을 계속 수집한 최종적인 해답은 최적이라는 보장은 없다

➡️ 탐욕 알고리즘을 적용하는 문제들은 지역적으로 최적 && 전역적으로 최적인 문제들이다.

➡️ 대표적인 문제 : 거스름 돈 문제

🔅 탐욕 알고리즘 구현 방법

1. 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답 선택

2. 적절성 검사 (Feasibility Check) : 선택한 해의 문제 조건 만족도 검사

3. 해답 검사 (Solution Check) : 원래의 문제 해결되었는지 검사하고, 해결되지 않았다면 다시 선택 절차부터 과정 반복 진행

🔅 탐욕 알고리즘의 2가지 조건

➡️ 탐욕 알고리즘이 적용되는 문제들은 대부분 탐욕스러운 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두가지 조건이 만족된다.

➡️ 탐욕스러운 선택 조건(Greedy choice property)이란, 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이고

➡️ 최적 부분 구조 조건(Optimal substructure)이란, 문제에 대한 최적해가 부분 문제에서 역시 최적해라는 것이다.

⏺ 이 조건들이 성립하지 않는 경우 탐욕 알고리즘은 최적해를 구하지 못한다.

⏺ 다만, 성립하지 않아도 근사 알고리즘으로 사용이 가능하며, 대부분 속도가 빠르기 때문에 실용적으로 사용이 가능하다.

⏺ 매트로이드 구조가 있는 문제에 대해선 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. \

⏺ 매트로이드는 모든 문제는 아니나, 여러 곳에서 발견되기 때문에 탐욕알고리즘의 활용도를 높여준다.

🔅 근사 알고리즘 (Approximation Algorithm)?

➡️ 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 말한다.

➡️ 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 계산 능력 뿐 아니라 어느 정도 보장된 근사해의 계산이 가능하다.

🔅 탐욕 알고리즘의 대표 예시 문제 - 캐셔(Casher's) 알고리즘

문제 : 30센트의 거스름돈 {1, 5, 10, 25} 의 동전들이 있을때

✅ 캐셔는 항상 가장 높은 값의 동전을 먼저 선택할 것이다.

1. 선택 절차

➡️ 가장 높은 가치의 25센트 동전 선택

2. 적절성 검사

➡️ 1번에서의 선택 동전 합이 거스름돈을 초과하는지 검사

(5센트 남음)

➡️ 초과시 가장 마지막 선택의 동전을 삭제, 1번으로 돌아가 한 단계 작은 동전을 선택

(두번째 선택에서 10센트 선택시 35센트로 거스름돈 초과 -> 한 단계 작은 동전인 5센트 선택)

3. 해답 검사

➡️ 선택된 동전들의 합이 거스름돈 값과 일치하는지 검사

(25+5 = 30센트로 거스름돈 값과 일치함)

➡️ 액수 부족시 1번부터 다시 반복

✅ 이 문제의 구조는 매트로이드로, 탐욕 알고리즘을 이용하면 언제나 최적해를 찾아 낼 수 있다.

✅ 이 문제의 시간복잡도는 동전의 개수만큼 반복되므로 O(N)이다.

 

 

🔅 이 문제 외에도 또 다른 최적해 문제들 (with. 이코테)

1. 어떤 수 N이 1이 될때까지 1을 빼거나 k로 나누기

문제 : 어떤 수 N에 대하여 다음 두 과정 중 하나를 반복하여 수행하려고 한다. 단 두번째 과정은 N이 K로 나누어 떨어질 때만 선택할 수 있다. < 1. N에서 1을 빼기 | 2. N을 K로 나누기 > N과 K가 주어질 때 N이 1이 될 때까지 두가지 과정 중 하나를 수행하는 최소 횟수는?

✅ 주어진 N에 대해 최대한 많이 나누기를 수행한다.

➡️ N이 K로 나눠지는 target 숫자를 구하고 그만큼의 차액은 1을 빼주는 과정이므로 결과값에 더해준다.

➡️ 중간에 N이 K보다 작을 때 벗어난다. 다만 N=1인 차례에 윗 단계에 의해 result에 1이 더해지므로 코드 마지막에 1을 빼준다.

2. 곱하기 혹은 더하기

문제 : 여러개의 숫자로 구성된 하나의 문자열 S(1<=S의 길이<=20)이 주어졌을 때, 만들어질 수 있는 가장 큰 수

✅ 대부분의 경우 '+'보다는 '*'가 값을 더 크게 만든다. 단, 두 수 중 하나라도 '0', 혹은 '1'이 있는 경우 '+'가 더 효율적이다.

➡️ 두 수에 대한 연산 수행시, 두 수 중 하나라도 1인 경우엔 더하고 두 수가 모두 2 이상인 경우 곱한다.

3. 모험가 길드

문제 : 모험가가 N명 있고 각자의 공포도를 측정했을 때 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다. N명의 모험가에 대한 정보가 주어졌을때 만들 수 있는 모험가 그룹의 최대 수는? (단, 모든 모험가가 그룹에 포함되어야 하는 것은 아님)

✅ 오름차순 정렬 후 공포도에 따른 그룹을 만들게 되면 항상 최소한의 모험가의 수만 포함해 그룹을 만들 수 있다.

➡️ 앞에서부터 공포도 확인하면서 현재 그룹에 포함된 모험가의 수가 현재 확인된 공포도보다 크거나 같다면 그룹으로 설정한다.

 

 

❗️[ 참고문헌 ]

이 포스팅은 https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/ 와

[이것이 코딩테스트다 with python]편을 참고하여 작성되었습니다