🌈 그리디(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)
Keep Going, Keep Coding!