그리디(Greedy)

CONCEPT : 나중에 미칠 영향을 고려하지 않고 지금 당장 가장 좋은 것만 고르는 방법

 

tip1. 암기를 해서 풀기보다는 다양한 유형을 접해보는 것이 중요

tip2. 문제 유형이 파악이 힘든경우 greedy algorithm을 상기, 그래도 모르겠다면 다이나믹 프로그래밍이나 그래프 알고리즘 고민.

 

ex. 거스름돈 - 가장 큰 화폐 단위부터 거슬러주기

n = 1260
count = 0

# 큰 단위 화폐부터 list에 입력
coin_types = [500, 100, 50, 10]

for coin in coin_types:
	# type 별 동전 수
    count += n//coin
    # type별 거슬러주고 남은 금액
    n %= coin
print(count)

정당성 check! 

ex. 화폐 단위가 [500원, 400원, 100원]이고 거스름돈이 800원인 경우

greedy algorithm : 500 + 100 + 100 + 100 => 총 4개

but, Actual answer : 400 + 400 => 총 2개

- 이런식의 예외가 있는지 확인 필요.

 

예제 1. 큰 수의 법칙

Q. 주어진 N개의 숫자 배열을 M번 더하여 가장 큰 수 만들기(단, 연속된 숫자가 K번을 초과하면 안된다)

 

- Version 1(단순하게 푸는 방법)

n, m , k = map(int, input().split())

data = list(map(int, input().split()))

data.sort()
first = data[n-1]
second = data[n-2]

result = 0

while True:
    for i in range(k):
        if m == 0:
            break
        result += first
        m -= 1
    if m == 0:
        break
    result += second
    m -= 1
print(result)

- Version 2 (메모리 고려 : 반복되는 수열 파악)

n, m, k = map(int, input().split())

data = list(map(int, input().split()))

data.sort()
first = data[n-1]
second = data[n-2]

# int(m / (k+1)) : 수열이 반복되는 횟수
# int(m / (k+1)) * k : first가 등장하는 횟수
# m % (k+1) : m이 k+1 로 나누어 떨어지지 않을 경우도 고려
count = int(m / (k+1)) * k
count += m % (k+1)

result = 0
result += (count) * first 
result += (m - count) * second

print(result)

SH 풀이

def solution(array, n, m, k):
    array.sort(reverse=True)
    count = m // (k+1)
    d = m%(k+1)
    return array[0]*count*k + array[1]*count + array[0]*d

 

예제 2. 숫자 카드 게임

Q. 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑기(단, rule 존재)

rule 1. 카드들은 N x M 형태로 놓여있다. (N: row의 개수, M: column의 개수)

rule 2. 먼저 뽑고자 하는 카드가 포함된 row 선택

rul3 3. 행에 포함된 카드들 중 가장 낮은 숫자를 선택

 

tip. 각 row에서 가장 작은 수를 찾고 그 수들 중 가장 큰 수를 찾기

 

- Version 1 (min 함수 사용)

n, m = map(int, input().split())

result = 0

for i in range(n):
    data = list(map(int, input().split()))
    min_value = min(data)
    result = max(result, min_value)
print(result)

- Version 2 (이중 for문 사용)

n, m = map(int, input().split())

result = 0

for i in range(n):
    data = list(map(int, input().split()))
    min_value = 10001
    for j in data:
        min_value = min(min_value, j)
    result = max(result, min_value)
print(result)

SH 풀이

def solution(array, n, m):
    result_list = []
    for i in range(n):
        result_list.append(min(array[i]))
    answer = max(result_list)
    return answer

 

예제 3. 1이 될 때까지

Q. N이 1이 될 때까지 다음 두 과정 중 하나를 반복적으로 선택하여 수행한다. (단, 두번째 연산은 N이 K로 나누어 떨어질 경우만 선택 가능)

1. N에서 1을 뺸다.

2. N을 K로 나눈다.

- Version 1 (단순하게 푸는 방법)

n, k = map(int, input().split())
result = 0

while n>=k:
    while n % k !=0:
        n -= 1
        result += 1
    n //=k
    result += 1
# 1<n<k 인경우    
while n>1:
    n-=1
    result +=1
print(result)

 

- Version 2 (-1을 효율적으로 하는 방법)

n, k = map(int, input().split())
result = 0

while True:
    # 나누어 떨어지는 수가 될때 까지 1씩 빼기
    target = (n//k) * k
    result += (n - target)
    n = target
    # 더이상 나눌 수 없을 때
    if n<k:
        break
    result +=1
    n //= k
# 마지막에 남은 수에 대해 계산
result += (n-1)
print(result)

 

SH 풀이

def solution(n, k):
    count=0
    while n > 1:
        if n%k == 0:
            n//=k
        else:
            n-=1
        count += 1
    return count