알고리즘 기초 - 그리디(Greedy)

🌈 그리디(Greedy)

🔥 그리디(Greedy) 기법 이란?

🔥 그리디(Greedy) 연습 문제

1. 그리디(Greedy) 기법 이란?

• 그리디 알고리즘은 최적의 해에 가까운 값을 구하기 위해 사용되고, 여러 경우 중 하나를 선택할 때마다 매순간 최적이라고 생각되는 경우를 선택하는 방식을 진행하여 최종적인 값을 구하는 방식
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함
• 그리디 해법은 그 정당성 분석이 중요함
• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음
  • 예를들어, 숫자의 합이 가장 큰 경로를 구할 때, 그리디 알고리즘은 단순히 지금 당장 큰 값을 선택하여 경로를 선택하기 때문에 최종적으로 경로의 모든 수의 합이 가장 큰 합이 되지 않을 가능성 존재
• 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻는 해가 최적의 해가 되는 상황을 전제하고, 이를 추론할 수 있어야 풀리도록 문제가 출제됨

1) 거스름 돈 문제

• 거스름돈으로 사용할 수 있는 동전이 500원, 100원, 50원, 10원이 무제한 존재한다고 가정할 때, 거스름돈 N원을 줄 수 있는 최소의 동전을 사용하여 구하시오.
• 최적의 해는 동전의 갯수가 최소가 되야하기 때문에 가장 큰 화폐 단위부터 돈을 거슬러 줘야함
• 즉, N원을 거슬러줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준 뒤, 그 후 100원, 50원, 10원을 순으로 최대 거슬러 줘 N값에 도달하는 것이 해법임

coin_list = [100, 10, 50, 500]
def greed_coin_count(money, coin_list):
    coin_count = 0
    details = list()
    coin_list.sort(reverse=True) # 값이 큰 것부터 정렬
    for coin in coin_list:
        coin_num = money // coin # 현재 거스름돈을 coin으로 나눈 몫
        coin_count += coin_num # coin 갯수를 계속 더함
        money = money % coin # 총 거스름 교체(money = money - (coin_num * num))
        details.append([coin, coin_num])
    return coin_count, details
print(greed_coin_count(4720, coin_list)) # (13, [[500, 9], [100, 2], [50, 0], [10, 2]])

• 화폐의 종류가 k개 라고 할 때, 시간 복잡도는 O(K)임
• 이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받 음

2) 부분 배낭 문제(Fractional Kanpsack Problem)

• 각 물건이 무게(w)와 가치(v)로 표현될 때, 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제

def get_max_value(data_list, capacity):
    # 물건별 무게 대비 가치가 높은 순으로 정렬
    data_list = sorted(data_list, key=lambda x: x[1]/x[0], reverse=True)
    # print(data_list) # [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]
    total_value = 0
    details = list()
    for data in data_list:
        if capacity - data[0] >= 0: # 수용크기가 첫번째 물건의 무게보다 클 때
            capacity -= data[0]
            total_value += data[1]
            details.append([data[0], data[1], 1])
        else: # 수용크기가 첫번째 물건의 무게보다 작을 때
            fraction = capacity / data[0]
            total_value += data[1] * fraction
            details.append([data[0], data[1], fraction])
            break
    return total_value, details
# Test
data_list = [(10,10),(15,12),(20,10),(25,8),(30,5)]
print(get_max_value(data_list, 30))
# (24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25]])

2. 그리디(Greedy) 연습 문제

1) 1이 될 때까지

• N = 17, K = 4일 때, N이 1이 될 때까지 과정을 수행하는 최소 횟수는 총 3번
  • 첫번째(1번 과정) : 17 - 1 = 16
  • 두번째(2번 과정) : 16 / 4 = 4
  • 세번째(2번 과정) : 4 / 4 = 1

# 풀이 1 (효율적인 방법)
n, k = map(int, input().split())
result = 0
while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k # K로 나눌수 있는 N과 가장 가까운 수를 target 할당
    result = result + (n - target) # result = k로 나눌 수 있는 수까지 도달하기 위해 -1한 과정 수 
    n = target # n을 k로 나눌 수 있는 값으로 할당
    # N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    result = result + 1 # k로 나눌 수 있는 값이 되었기 때문에 2번 과정을 수행한 의미로 1을 더함
    n = n // k  # k로 나눈 몫을 n으로 할당(2번 과정 수행)
# 마지막으로 남은 수에 대하여 1씩 빼기
result = result + (n - 1)
print(result)

# 풀이 2
n, k = map(int, input().split())
result = 0
while True:
    if n % k == 0:
        n = n // k
        if n < k:
            break
    else:
        if n > k:
            target = (n // k) * k
            result = result + (n - target)
            n = target
        else:
            result = result + n
    result = result + 1
print(result)

2) 곱하기 혹은 더하기

• 대부분의 경우 '+'보다 'x'가 더 값을 크게 만들지만, 두 수 중 1개라도 0 또는 1이였을 때에는 '+'을 수행하는 것이 더 큰 수를 만들 수 있음
• 따라서 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1이하인 경우에는 더하고, 두 수가 모두 2이상인 경우에는 곱하면됨

data = input()
result = int(data[0])
for i in range(1, len(data)):
    # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
        result = result + num
    else:
        result = result * num
print(result)

3) 모험가 길드

n = int(input())
data = list(map(int, input().split()))
data.sort() # 정렬
# print(data) # 1,2,2,2,3
result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수
# 공포도가 낮은 것부터 하나씩 확인
for i in data:
    count = count + 1 # 현재 그룹에 해당 모험가를 포함시키기
    if count >= i:
        result = result + 1
        count = 0
    # print(f'i : {i}, count : {count}, result : {result}')
print(result)