알고리즘 - 그리디 알고리즘

탐욕 알고리즘(Greedy Algorithm)

 

매 순간 현재 상황에서 가장 좋아보이는 최선의 선택으로 문제를 해결하는 방식

 

최적해: 주어진 문제를 가장 효과적으로 해결하는 최상의 답 또는 해결 방법

 

• 항상 최적의 값을 보장하는 것이 아닌, 최적의 값의 근사 값을 목표로 함
• 문제를 분할한 뒤, 각 문제에 대한 최적해를 구해 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용
• 따라서 정해진 공식 없이 창의력을 요구함

 

탐욕 알고리즘의 특징 

• 탐욕 선택 속성
  • 각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우
  • 각 단계에서 이상적인 선택 => 최적의 결과
  • 앞의 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조
  • 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우
  • 전체 문제를 분할하고 각 문제에 대해 최적해를 구한 뒤 조합하여 전체 문제의 최적해를 구함
• 비가역성
  • 한 번 선택하면 이후에 되돌리지 않는다.
• 문제의 구조가 탐욕 알고리즘에 맞지 않으면 오답을 도출할 확률이 높다.

 

동작방식

 

트리에서 가장 큰 값을 찾으려고 할 때

1. 시작 노드에서 자식 노드를 비교하여 더 큰 10으로 따라간다.
2. 또 10노드의 자식 노드를 비교하여 더 큰 14로 따라간다
3. 그리디 알고리즘으로 구한 가장 큰 값은 14가 된다.

다른 알고리즘을 사용하면 노드에서 가장 큰 값인 100을 찾을 수 있을 것이다. 하지만 탐욕 알고리즘은 당장의 자식 노드만을 비교하며 큰 값을 쫓아간다.

 

 

오직 눈앞의 최선만을 쫓아가기 때문에 탐욕 알고리즘이라고 불린다.

 

 

탐욕 알고리즘의 장단점

장점	단점
설계와 이해가 매우 쉽다.	최적해의 보장이 없다. (이게 제일 큰 단점)
현재의 선택만을 고려하므로 연산 속도가 매우 빠르다.
전체 경우의 수를 계산하기 않고, 이전 단계들을 기록하지 않아 메모리 소모가 적다.	이전 선택을 돌이킬 수 없어 초기의 얕은 선택이 전체에 악영향을 미칠 수 있다.

 

 

---

탐욕 알고리즘 예제

1) 거스름돈 예제

일본은 오늘날에도 현금(동전)을 많이 사용한다. 나는 마트 사장이고, 손님에게 거스름 돈을 돌려주어야 한다. 거스름 돈을 N엔 돌려주어야 할 때, 사용하는 동전의 최소 개수를 구한다. (10의 배수로)

 

풀이

1. 무조건 큰 동전부터 소진해야 한다.
2. N이 500 미만이 되면 100미만이 될 때까지 100씩 빼준다.
3. 이를 반복하여 N이 0이 될 때까지 count하여 동전 개수를 반환한다.

코드

def greedy_coin(N):
    count = 0                   # 동전 개수
    money = 1000-N              # 거스름 돈
    coin = [500, 100, 50, 10]   # 동전 단위 (500엔, 100앤, 50엔, 10엔)

    for i in coin:              # coin 안의 요소           
        count+= money//i        # 거스름 돈을 i번째 인덱스의 값을 나눈 몫을 count에 저장
        money %= i              # 거스름 돈을 i번째 인덱스의 값으로 나눈 나머지(나머지 거스름돈)
    
    return count                # 동전 개수 반환

while(True): 
    num = int(input("상품의 종 합계를 입력하세요(10의 배수): "))

    if num%10 != 0 :            # 만약 10의 배수로 입력하지 않았다면
        print("10의 배수로 입력하세요 ")
    else:
        print(greedy_coin(num))
        break

 

출력결과

 

상품의 총 합계를 입력 받으면 1000-560 = 440 이므로

100엔짜리 동전 4개와 10엔짜리 동전 4개, 총 8개를 주는 것이 최소한의 동전 개수이다.

 

10의 배수로 입력하지 않으면 이런 결과가 나오도록 했다.

 

 

 

 

2) 회의실 배정 예제

한 개의 회의실에 N개의 회의에 대해 사용표를 만들려고한다. 각 회의에 대해 시작 시간과 종료시간이 다음과 같다면 각 회의가 겹치지 않게 회의실을 사용할 수 있는 최대 개수를 찾아보려고 한다.

회의 시간	풀이
(1, 4) => 1시에 시작해서 4시에 끝남	1. 회의 종료 시간을 기준으로 정렬
(3, 5)	2. 회의 시작 시간이 마지막 회의 종료 시간보다 크면 회의실 사용이 가능함
(0, 6)	3. count에 +1 해주고
(5, 7)	4. 회의 끝나는 시간을 회의 종료시간으로 초기화
(3, 8)
(5, 9)
(12, 14)
(2, 13)

 

코드

def meetings(time):
    time.sort(key=lambda x:(x[1], x[0]))	# 종료시간으로 오름차순 정렬

    count = 0
    last_end = 0

    for start, end in time:					
        if start >= last_end:			# 회의 시작시간이 마지막 회의 종료시간보다 크거나 같으면
            count += 1				# 회의할 수 있음 (1증가)
            last_end = end
    
    return count

# 데이터 입력
time = [(1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (12, 14), (2, 13)]
print(meetings(time))

 

출력결과

 

(1,4) (5,7) (12, 14) 세 개의 회의를 진행할 수 있다.

 

 

 

 

2) 배낭 문제 예제

n개의 물건이 있을 때 각 물건에는 가치와 무게가 존재한다.

무게를 정해주고, 배낭에 담을 수 있는 무게를 넘어서는 물건은 담지 못한다.

이 때, 배낭에 물건의 가치가 가장 높게 담는 문제이다.

물건을 분할(잘라 담는)가능하다고 가정하고 분할 가능한 배낭 문제를 풀어본다.

(단, 배낭은 1개이며 배낭에 담을 수 있는 최대 용량은 15kg이다)

 

풀이

1. 아이템별 무게, 아이템별 가치를 입력하고
2. 1Kg 당 가치가 가장 높은 순서대로 정렬
3. 위에서 정렬한 순서대로 배낭에 하나씩 담다가
4. 최대 용량 15kg를 넘을 것 같으면 아이템을 분할한다.

코드

def func(items, capacity):
    items.sort(key=lambda x:x[1] / x[0], reverse=True)
    total = 0.0
    bag_list = []

    for weight, value in items:
        if capacity - weight >= 0:
            capacity -= weight
            total += value
            bag_list.append((weight, value, 1))
        else:
            fraction = capacity /weight
            total += value + fraction
            bag_list.append((weight, value, fraction))
            break

    return total, bag_list

items = [(2, 10), (4, 30), (3, 25), (8, 80), (5, 65), (1, 8)]
capacity = 15

Max_value, taken = func(items, capacity)
print(f"최대가치:  {Max_value}")
print("담은 물건 (무게, 가치, 비율): ", taken)

 

출력결과