[알고리즘] 이코테 - 그리디

그리디 알고리즘

어떤 문제가 있을 때, 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이다. 탐욕적, 즉 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해 주는 경우가 많다.

 

e.g., 거스름돈 문제: 500원, 100원, 50원, 10원이 있는 경우에, 거슬러 줘야 할 동전의 최소 개수를 구한다.

 

-> 이때, 가장 큰 화폐단위부터 돈을 거슬러 주면 최소 개수로 동전을 줄 수 있다.

-> 화폐 종류만큼 반복을 수행해야하기 때문에 시간복잡도 O(K)로 문제를 풀 수 있다. 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러줘야 할 금액의 크기와는 무관하다.

# 거스름돈
n=int(input("금액: ")) #1260
answer=0

check=[500,100,50,10]
for i in check:
  cnt=n//i
  answer+=cnt
  n%=cnt*i

print(answer) #6

 

그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분하다. 하지만 거스름돈 예시와 같이 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 효과적이다. 그리디로 해법을 찾았을 때는 그 해법이 정당한 지를 검토해야 한다. 

 

e.g., 거스름돈 문제(추가 설명): 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.

 

 

문제를 만났을 때, 유형 파악이 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적 해결법이 존재하는 지를 고민하자.

 

e.g., 큰 수의 법칙: 주어진 수들을 M번 더하여 가장 큰 수를 만든다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

 

-> 가장 큰 수를 K번 더하고 두번째로 큰 수를 한 번 더하는 연산을 반복하자.

-> 이때, 반복되는 수열을 활용하여 아래의 코드로 작성할 수 있다. 

n=int(input("n: ")) #5
m=int(input("m: ")) #7
k=int(input("k: ")) #2

input_str = input("숫자들을 입력하세요 (공백으로 구분): ")
input_list = input_str.split()  # 입력받은 문자열을 스페이스로 나누어 리스트로 변환
number_list = [int(item) for item in input_list]  # 3 4 3 4 3

short=max(number_list)
number_list.remove(short)
second=max(number_list)

answer=0
answer=(m//(k+1))*(short*k+second)
answer+=(m%(k+1))*short

print(answer) #28

 

e.g., 어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

-> N이 K의 배수가 될 때까지 1씩 빼기 -> N을 K로 나누기

# 1이 될 때까지
n, m=map(int,input().split()) # 17 4

rest=n%m
n-=rest
answer=rest

while True:
  if n==1:
    break
  n//=m
  answer+=1

print(answer) #3