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

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리한 글입니다

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYEGw61n8DFAVT# 

SW Expert Academy

 

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

목차

01 탐욕 알고리즘

02 동전 거스름돈 문제

03 배낭 문제

04 활동 선택 문제

05 Baby-Gin 다시 보기

 

 

01 탐욕 알고리즘

---

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

최적화 문제를 해결하는 알고리즘으로 그리디 알고리즘은 최적해를 구하는데 사용되는 근시안적 방법으로, 

머릿속에 떠오르는 생각을 검증없이 바로 구현할 경우 Greedy 접근이 됨

* 최적화 문제: 최적(최대값이나 최소값 같은)값을 구하는 문제

• 해당 문제에 여러 해가 있을 수 있음
• The 최적해를 구하는 것이 아니라 an 최적해를 구하는 것

그 순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적인 해답에 도달한다

각 결정은 지역적으로는 최적이나, 선택을 계속 수집하여 해답을 만들었으므로 그것이 최적이라는 보장은 없으므로,

따라서 그리디 알고리즘을 적용시 이 해(solution)가 항상 최적해임을 증명해야 한다

 

동작 과정

1. 해 선택

- 현재 상태에서 부분 문제의 최적해(Best Soultion)를 구한 뒤 부분 해 집합(Solution Set)에 추가

- 하나의 선택이 이루어지면 새로운 부분 문제 발생

2. 실행 가능성 검사 실시

- 새로운 부분 해 집합의 실행 가능 여부 확인

- 문제의 제약 조건 위반 여부 검사

3. 해 검사

- 새로운 부분 해 집합이 문제의 해가 되는지 확인

- 전체 문제의 해가 완성되지 않은 경우 해 선택부터 다시 시작

 

 

 

02 동전 거스름돈 문제

---

동전 거스름돈 문제(Coin Change Problem)란?

손님이 지불한 금액에서 물건값을 제한 차액(거스름돈)을 지불하는 문제로, 보통 지폐와 동전의 개수를 최소한으로 하는 문제로 나온다

 

그리디 알고리즘을 적용한 동전 거스름돈 문제의 동작 과정

1. 해 선택

- 전략 : 가장 좋은 해 선택

- 방법 : 단위가 큰 동전순으로 거스름돈 만들기

2. 실행 가능성 검사 실시

- 거스름돈이 손님에게 내드려야 할 액수를 초과하는지 확인

- 초과한다면 추가한 동전을 빼고 해 선택으로 돌아가 한 단계 작은 동전을 추가함

3. 해 검사

- 해: 손님에게 내드려야 하는 거스름돈의 액수

- 거스름돈을 확인해서 액수에 모자라는 경우 해 선택부터 다시 시작

 

적용 예시

Q: 거스름돈 금액이 800원일 때 동전 개수를 최소화하여 거스름돈을 준다고 했을 때 최적해는?

* 동전의 종류는 500원, 400원, 100원, 50원, 10원

A: 단위가 큰 동전 순으로 거스름돈을 만드는 그리디 전략에 따르면 (500, 100, 100, 100)으로 답이 4가 됨

- 하지만 실제 최적해는 (400,400)으로 2가 된다.

- 즉, 단위가 큰 동전 순으로 거스름돈을 만드는 전략으로는 최적해를 구할 수 없음

- 그리디 알고리즘은 해당 전략이 최적이라는 보장이 없으므로, 이를 보장하기 위해서는 검증하는 작업이 반드시 필요

 

 

 

03 배낭 문제

---

배낭 문제(knapsack Problem)란?

배낭이 수용할 수 있는 무게를 초과하지 않으면서 값의 총합이 최대가 되도록 물건을 선택하는 문제로 정형정 정의는 아래와 같다

 

$\sum_{item_i \in A} w_i <= W$를 만족하면서 $\sum_{item_i \in A} P_i$ 가 최대가 되도록 $A \in S$ 가 되는 A를 결정하는 문제

• 의미: 물건들의 무게의 합이 배낭무게를 초과하지 않고 물건값이 최대가 되도록 A를 결정
• $S$ : n개의 물건들의 집합, $S={item_1, \cdots , item_n}$
• $w_i$ : i번 째 물건의 무게
• $p_i$ : i번 째 물건의 값(가치)
• $W$ : 배낭에 수용 가능한 총 무게

Knapsack 문제 유형

0-1 Knapsack

• 배낭에 물건을 통째로 담아야 하는 문제
• 물건을 쪼갤 수 없는 경우임

Fractional Knapsack

• 물건을 부분적으로 담는 것이 허용
• 물건을 쪼갤 수 있는 경우

 

0-1 Knapsack에 대한 탐욕적 방법

1. 전략1 : 값이 비싼 물건부터 채운다
2. 전략2 : 무게가 가벼운 물건부터 채운다
3. 전략3 : 무게당 값이 높은 순서로 물건을 채운다

-> 전략 1,2,3 다 최적해를 구할 수 없음, 즉 탐욕적 방법으로 배낭문제의 최적해를 구한다는 보장을 할 수 없음

 

Fractional Kanpsack 방법

• 전략 : 물건의 일부를 잘라서 담을 수 있다
• 실생활에서 사용할 수 있는 방법은 아니나 이상적으로 구할 수 있는 최대 가치임
• 해당 전략으로 최적해를 구할 수 있음*

 

04 활동 선택 문제

---

활동 선택 문제(Activity Selection Problem)란?

한번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제안된 활동들 중 가장 많은 활동을 처리할 수 있는 스케줄을 짜는 문제로 대표적으로 회의실 배정 문제가 있다

*회의실 배정 문제

- 시작시간과 종료시간이 있는 n개의 활동들의 집합에서 서로 겹치지 않는 최대 개수의 활동들의 집합을 구하는 문제

- 양립 가능한 활동들의 크기가 최대가 되는 부분집합을 선택하는 문제

 

 

탐욕 기법의 적용 방법

전략 : 종료 시간이 가장 빠른 활동 순으로 선택

최선의 선택 : 종료 시간이 가장 빠른 활동 순으로 선택

항상 최적의 해 구할 수 있음

탑다운 방식(top-down approach)의 문제 해결

 

탐욕 기법을 적용한 반복 알고리즘(c++)

//일을 종료시간이 빠른 순으로 정렬(단, 종료시간이 같을 경우 시작시간이 빠른 순으로 정렬)
sort(work.begin(), work.end(), compare); 
int tmp = work[0].second; //제일 종료시간이 빠른애로 스타트
int ans = 1; //총 가능한 회의 갯수

for(int i = 1; i < total_work; i++){
    //현재 진행하고 있는 회의가 종료되는 시간과 같거나 이후에 시작하는 일 고르기
    if( w[i].first >= tmp){
        ans++;
        tmp = w[i].second; //고른 일의 종료시간을 저장
    }

 

탐욕 알고리즘이 최적해를 구한다는 것에 대한 증명 

탐욕적 선택 속성(Greedy choice property)

- 탐욕적 선택은 최적해로 갈 수 있음 즉, 항상 안전하다는 것을 보여야 함

최적 부분 구조(Optimal substructure property)

- 최적화 문제를 정형화

- 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남음

- [원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해]임을 증명

 

탐욕 기법과 동적 계획법의 비교

탐욕 기법(Greedy Algorithm)	동적 계획법(Dynamic Programming)
단계마다 가장 좋아 보이는 것을 선택함 -> 지역 최적 선택(local optimal choice)	매 단계의 선택은 해결한 하위 문제의 해를 기반으로 함
하위 문제 풀기 전, (탐욕적) 선택이 먼저 이루어짐	하위 문제 우선 해결
Top-down 방식	Bottom-up 방식
일반적으로, 빠르고 간결함	좀 더 느리고, 복잡함