01. List 1 - 4차시 탐욕 알고리즘(Greedy Algorithm)

1. 탐욕 알고리즘(Greedy Algorithm)

---

그 순간에 최적이라고 생각되는 것을 선택해나가는 방식

---

 

 최적 해를 구하는데 사용되는 근시안적인 방법이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식으로 진행하여 최종적인 해답에 도달한다. 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없다. 일반적으로, 머리속에 떠오르는 생각을 검증없이 바로 구현하면 Greedy 접근이 된다.

 

2. 탐욕 알고리즘 수행 과정

1. 해 선택

현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분 해 집합(Solution Set)에 추가한다.

 

2. 실행 가능성 검사

새로운 부분 해 집합이 실행 가능한지를 확인한다. 그 다음 문제의 제약 조건을 위반하지 않는지를 검사한다.

 

3. 해 검사

새로운 부분 해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 해 선택부터 다시 한다.

 

예시) 거스름돈 줄이기

어떻게 하면 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?

 

1. 해 선택

> 가장 좋은 해를 선택

가장 단위가 큰 지폐 혹은 동전을 고른다.

 

2. 실행 가능섬 검사

금액이 거스름돈을 초과하는지를 확인. 초과한다면 마지막에 추가한 동전을 빼고, 해 선택으로 돌아가서 한 단계 작은 단위의 동전을 추가한다.

 

3. 해 검사

금액이 거스름돈과 일치하는지 확인. 금액이 모자라면 다시 해 선택으로 돌아간다.

 

3. Baby-gin 문제 다시풀기

완전 검색이 아닌 탐욕 알고리즘으로 풀기

1. 6개의 숫자는 6자리의 정수 값으로 입력된다.

 

2. COUNTS 리스트의 각 원소를 체크하여 run과 triplete 및 Baby-gin 여부를 판단한다.

> 탐욕 알고리즘 적용.

COUNTS 리스트에서 run과 triplete 중에 가능한 것을 조사한다. 그리고 조사에 사용한 데이터는 삭제한다. 남은 데이터를 다시 run과 triplete중에 가능한지 검사한다.

 

예) 444345를 뽑은 경우

COUNTS list

1	2	3	4	5	6	7	8	9	0
		1	4	1

run 조사 후 run 데이터 완전 삭제

1	2	3	4	5	6	7	8	9	0
			3

triplete 조사 후 baby-gin 성립된다.

 

3. 슈도코드로 표현

num = 456789 # baby-gin을 확인할 6자리 수
counts = [0] * 12 # COUNTS 리스트

for i in range(6):
	counts[num % 10] += 1
    num //= 10

i = 0
tri = run = 0
while i < 10 :
	if counts[i] >= 3 : # triplete 조사
    	counts[i] -= 3 # 조사 후 데이터 삭제
        tri += 1
        countinue
   	if counts[i] >= 1 and counts[i + 1] >= 1 and counts[i + 2] >= 1 : # run 조사
    	counts[i] -= 1
        counts[i + 1] -= 1
        counts[i + 2] -= 1 # 조사 후 데이터 삭제
        run += 1
        countinue
    i += 1
 
if run + tri == 2 : print("baby-gin")
else : print("lose")

 

4. 탐욕 알고리즘 접근의 경우, 해답을 찾아내지 못할 때

입력 받은 숫자를 정렬한 후, 앞뒤 3자리씩 끊어서 run, triplete을 확인하는 방법에 경우 해답을 찾지 못한다.

 

예) 1, 2, 3, 1, 2, 3

정렬하면 {1, 1, 2, 2, 3, 3}로서, 오히려 baby-gin 확인을 실패할 수 있다.

3. 유의점

탐욕 알고리즘적인 접근은 해답을 찾아내지 못하는 경우도 있다.