탐욕 알고리즘(그리디)

그리디

---

• 최적의 해에 가까운 값을 구하기 위해 사용됨
• 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식

 

1. 동전 문제

---

coin_list = [500, 100, 50, 1]

def min_coin_count(value, coin_list):
    total_coin_count = 0
    details = list()
    coin_list.sort(reverse = True)
    for coin in coin_list:
        coin_num = value // coin
        total_coin_count += coin_num
        value -= coin_num * coin
        details.append([coin, coin_num])
    return total_coin_count, details

print(min_coin_count(4720, coin_list))

 

2. 부분 배낭 문제

---

data_list = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]

def get_max_value(data_list, capacity):
    data_list = sorted(data_list, key=lambda x: x[1]/ x[0], reverse=True)
    total_value = 0
    details = list()

    for data in data_list:
        if capacity - data[0] >= 0:
            capacity = capacity - data[0]
            total_value = total_value + data[1]
            details.append([data[0], data[1], 1])
        else:
            fraction = capacity / data[0]
            total_value = total_value + (data[1] * fraction)
            details.append([data[0], data[1], fraction])
            break
    return total_value, details

print(get_max_value(data_list, 30))

 

3. 실전 코딩 테스트 - 모아서 풀어보면 일정한 패턴이 보인다!

---

** 리스트를 정의하고 데이터를 정렬하는 패턴

[백준 => ATM]

1)

N = 5
N_list = [3, 1, 4, 3, 2]
minimum = 0

# 지금 받은 리스트에서 가장 최적인 것(최소인 시간)을 고르려면? => 순서대로 정렬 필요
N_list.sort()

for index in range(N):
    for index2 in range(index + 1):
        minimum = minimum + N_list[index2]
print(minimum)

2)

N = int(input())
N_list = list(map(int, input().split()))
min = 0

N_list.sort()

for index in range(N):
    for index2 in range(index + 1):
        min += N_list[index2]
print(min)