그리디, 당장 좋은 것

그리디(Greedy) 알고리즘은 단순하지만 강력한 PS 알고리즘이다. 탐욕법이라고도 부르는 이 알고리즘은 이름에서 알 수 있듯이 어떠한 문제를 단순 무식하게, 탐욕적으로 해결한다. 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰(작은) 순서대로와 같은 힌트를 알게 모르게 제시해준다. 보통 이 기준은 정렬 알고리즘과 자주 사용된다.

거스름돈

500원, 100원, 50원, 10원짜리 동전이 있을 때 손님에게 거슬러 줘야할 동전의 최소 개수를 구하는 문제이다. (단, 거슬러 줘야할 돈 N은 항상 10의 배수이다.)

풀이

1
2
3
4
5
6
7
money = int(input())
cash=[500, 100, 50, 10]
count=0
for coin in cash:
    count += money // coin
    money %= coin
print(count)

앞서 설명했듯이 문제에 동전의 “최소 개수”를 구하라고 명시되어 있다. 또한 그리디로 해결할 수 있는 이유는 큰 단위가 항상 작은 단위의 배수임으로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 시간복잡도는 화폐의 종류가 K개라고 할 때 O(K)가 된다.

큰 수의 법칙

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

예) [2,4,5,4,6], M=8, K=3일 때 6+6+6+5+6+6+6+5=46

첫번째 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n,m,k=map(int,input().split())
numbers=list(map(int,input().split()))
numbers.sort()

result=0

n_1=numbers[-1]
n_2=numbers[-2]

while 1:
    for j in range(k):
        if m==0: break
        result+=n_1
        m-=1
    if m==0: break
    result+=n_2
    m-=1

print(result)

결국 필요한 수는 가장 큰 수와 두번째로 큰 수이다. 가장 큰 수를 반복하다가, 같은 수가 K번이 넘을 때 두번째로 큰 수를 끼워주면 되기 때문이다.

하지만 위와 같은 방식은 수가 커질수록 비효율적이게 된다.

반복되는 수열에 대해서 파악해야 한다.

두번째 풀이

1
2
3
4
5
6
7
8
9
10
11
n,m,k=map(int,input().split())
numbers=list(map(int,input().split()))
numbers.sort()

n_1=numbers[-1]
n_2=numbers[-2]

#나누어 떨어지는 경우, 나누어 떨어지지 않는 경우 (나누어 떨어지지 않는 경우는 무조건 가장 큰 수를 더하는 경우임)
count=int(m/(k+1))*k + m%(k+1)
result=count*n_1 + (m-count)*n_2
print(result)

전체적으로 가장 큰 수가 필요한 경우, 두번째로 큰 수가 필요한 경우(결국 전체 개수 M에서 가장 큰 수를 쓴 횟수를 뺀 값이 된다)를 구하면 끝나는 문제이다.

숫자 카드 게임

여러 개(N*M)의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는다. 단, 선택된 행의 가장 낮은 숫자 카드를 뽑는다.

풀이

1
2
3
4
5
N,M=map(int,input().split())
num=[]
for _ in range(N):
    num.append(min(map(int,input().split())))
print(max(num))

간단하다. 입력받음과 동시에 가장 작은 수를 num배열에 넣고 마지막에 최대값을 출력해주면 된다.

1이 될 때까지

어떤 수 N이 1이 될 때까지 나누거나 뺀다. 방법은 두가지이다.

  • N에서 1을 뺀다
  • N을 K로 나눈다 (단, N이 K로 나누어 떨어질때만)

첫번째 풀이

1
2
3
4
5
6
7
8
9
10
11
n,k=map(int,input().split())
count=0
while 1:
    if n==1: break
    if n%k==0:
        count+=1
        n=n//k
    else:
        count+=1
        n-=1
print(count)

최대한 많이 나누면 된다. 1을 빼는 것보다 나눌 때 숫자가 훨씬 빨리 작아지기 때문이다. N이 K의 배수가 되도록 한번에 뺀다면 좀 더 효율적으로 짤 수 있다.

두번째 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n,k=map(int,input().split())
count=0
while 1:
    target=(n//k)*k # N이 K의 배수가 되도록 만들기
    count+=(n-target) # n-target: 1을 몇번 뺐는지
    n=target # 결국 n은 k의 배수
    
    if n<k: break # 더 이상 나눌 수 없을 때
    # n을 k로 나누기
    count+=1
    n//=k

count+=(n-1)
print(count)

N을 K의 배수가 되도록 만들고 나머지 경우를 빼주면 된다.