[알고 스터디] 6. 그리디 알고리즘 (Greedy Algorithm)

그리디,, 욕망이라는 뜻이죠? 욕망하면 맨날 저친구만 생각나네요,, ㅋㅋㅋㅋㅋㅋㅋ 오랜만

 

6.1 탐욕 알고리즘, 그리디 알고리즘!! 얼마나 탐욕적이길래 ㄷㄷ

• 탐욕적인게 뭘까요, 말그대로 욕심많은거죠? 이 알고리즘은 항상 모든 순간에 최적의 경우만 선택합니다.
• 그래서 최적의 해로 근사적으로 접근하려는 방식이다.
• 하지만 항상 좋은 선택만 하는게 최적의 해일까? 그리디 알고리즘의 방식이라면 내가 지금 당장 만원을 받기 vs 10분 후에 100만웜 받기에서 현재의 경우에는 만원 vs 0원 이기 때문에 무조건 전자를 고릅니다. 이후의 상황까지 생각하면 무조건 후자를 골라야 되는데 말이지..
• 그래서 그리디 알고리즘을 적용한다면 그리디 알고리즘의 최적의 해를 보장해주는 상황이라는걸 파악하고 사용해야 합니다.

6.2 그리디 알고리즘 문제를 해결할 때의 세 가지 메커니즘!

• 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
• 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
• 해답 검사(Solution Check) : 문제가 해결되면 끝, 아니라면 선택 절차부터 다시 반복

6.3 그리디 알고리즘을 적용하기 위한 조건!

• 그리디 알고리즘이 잘 동작하는 문제는 대부분 1. 탐욕스러운 선택 조건(Greedy choice property)과 2. 최적 부분 구조 조건(optimal substructure)을 만족함
• 탐욕스러운 선택 조건 : 앞의 선택이 뒤의 선택에 영향 X
• 최적 부분 구조 조건 : 문제에 대한 최종 해결 방법은 문제를 부분으로 나누어도 최적임 (부분 문제에 대한 최적)
• 이러한 조건이 성립하지 않는다면, 그리디는 최적의 해를 가져다 주지 않는다.
• 하지만 그렇더라도 그리디는 근사 알고리즘으로 사용 가능함 -> 계산 속도가 빨라 실용적 사용 가능
• 이때에는 최적해에 가까운지 엄밀한 증명이 필요함
• 어떤 특별한 구조 (=매트로이드)의 경우에서는 그리디가 항상 최적해를 찾아준다.

6.4 근사 알고리즘? 뭐지? 

-> Approximation Algoithm

• 근사 알고리즘은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘
• 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해 계산 가능

6.5 그리디 알고리즘 문제, 예시에는 뭐가 있을까?

예시1) 매트로이드

물건 구입 시에, 거스름돈 거슬러주기

 

매트로이드 구조 : 그리디 알고리즘으로 최적해가 보장되는 공간 구조

-> 독립성이라는 성질을 만족하는 수학적 공간

-> 위에 언급된 2가지 조건을 만족하는 공간

 

<문제 해결 과정>

1. 선택 절차

- 거스름돈의 동전 개수를 줄이기 위해 가장 가치가 높은 동전부터 우선 선택

2. 적절성 검사

- 선택 절차를 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사

- 초과하면 가장 마지막에 선택한 동전을 빼고, 다음 큰 동전을 선택

3. 해답 검사

- 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사

- 액수가 부족하면 다시 선택 절차부터 시행

 

예시2) 활동 선택 문제 (Activity Selection Problem)

회의실 예약 문제, 최대한 많이 예약할 수 있는 방법은?

<문제 해결 과정>

1. 선택절차

- 먼저, 길이가 짧은 회의부터 찾기 -> 이 방법은 가장 짧은게 가장 긴 정답인 케이스랑 겹치면 최적해가 안되므로 부적절

- 다른 방법, 가장 먼저 끝나는 회의부터 찾기

2. 적절성 검사

- 선택 절차를 통해 선택된 회의들이 겹치는지 검사

- 겹치면 빼고 다음 회의 확인

3. 해답 검사

- 모든 목록을 확인했다면 끝, 아니면 계속 선택

 

예시3) 분할가능 배낭문제

가방에 물건을 넣을 때 최대로 넣기, 물건을 정수 외 단위로 분할가능

출처:&nbsp;https://starrykss.tistory.com/1512

<문제 해결 과정>

1. 선택 절차

- 가장 큰 물건부터 선택

2. 적절성 검사

- 가방의 크기를 넘어가지 않는지 확인

- 넘는 다면 다음 큰 물건을 선택

3. 해답 검사

- 총 담은 물건들이 넘었는지 확인, 아니면 계속 선택