[알고리즘 이론] 그리디 알고리즘 Greedy!!!

[이거이 코딩 테스트다, 나동빈] 책을 공부하고 정리한 글입니다.

🌀그리디 알고리즘 🌀

: 지금 당장 좋은 것만 고르기🥴

 

✅ 예제 1) 거스름돈

N원을 거슬러 줘야함. 카운터에는 500, 100, 50, 10원짜리 동전이 무한히 있음. 거슬러줘야 할 동전의 최소 개수는? (N은 항상 10의 배수임)

나의 풀이~~~~

N = int(input())
num = 0

while 1:
    if N > 500:
        N = N - 500
        num += 1
    elif N > 100:
        N = N - 100
        num += 1
    elif N > 50:
        N = N - 50
        num += 1
    elif N > 10:
        N = N - 10
        num += 1
    else :
        break
print(num)

실행 결과

답안예시를 보니 내 코드가 참 길어보인다....ㅎㅎ

 

거스름돈 문제의 경우 큰 단위가 항상 작은 단위의 배수이기 때문에 그리디 알고리즘을 적용하여 항상 최적의 해를 찾을 수 있지만

그렇지 않을 경우 최적의 해를 찾을 수 없다.

 

✅ 예제2) 큰 수의 법칙

크기 n인 배열이 주어질 때, m은 숫자가 더해질 수 있는 횟수, k는 연속해서 더할 수 있는 수이다.

입력으로 주어지는 k는 항상 m보다 작을 때, k의 최댓값은?

(2 <= n <= 1000, 1 <= m <= 10000, 1 <= k <= 10000)

 

나의 풀이)

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

arr.sort()
res = 0
size = len(arr)

while m != 0:
    for i in (0, k):
        if m == 0:
            break
        m -= 1
        res += arr[size - 1]
    if m == 0:
        break
    res += arr[size - 2]
    m -= 1
print(res)

c언어만 하다가 파이썬 하려니 어떻게 짜야할지 느낌이 안온다....파이썬 문법에 익숙해져야겠다....! 

굳이 arr의 길이를 잴 필요가 1도 없다. 파이썬은 음수로 뒤에서 부터 인덱싱이 가능하다. 담부턴 참고!!! 입출력 받는 방법도 익숙해져야겠다.. 저게 머선소리고...

 

책에서 제시한 효율적인 방법!의 약간 변형)

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

arr.sort()
res = 0

res += (arr[-1] * k + arr[-2]) * int(m / (k+1))
res += (arr[-1]) * (m % (k+1))

print(res)

오오 정말 짧다!!!  res를 더하는 부분을 한줄로도 쓸 수 있을 것 같지만 보기 편하라고 나눠뒀다.

가장 큰 수를 k번, 그 다음으로 큰 수를 1번 더하는 것이 계속 반복되므로 위와 같이 풀이할 수 있다.

 

✅ 예제 3) 숫자 카드 게임

숫자 카드가 n(행) * m(열)으로 놓여있다. 원하는 행에서 가장 낮은 숫자 카드를 뽑아야 함. 뽑은 수가 가장 크도록 하는 경우의 숫자카드를 구하기

 

나의 풀이)

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

for i in range(n):
    arr = list(map(int, input().split()))
    res = max(min(arr), res)

print(res)

 

✅ 예제 4) 1이 될 때까지

어떤 수 n이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행 (단 두번째 연산은 n이 k로 나눠떨어질 때만 수행 가능)

1. n에서 1을 뺌

2. n을 k로 나눔

n과 k가 주어질 때 1 혹은 2를 수행해야 하는 최소 횟수 (입력으로 주어지는 n은 항상 k보다 크거나 같다.)

나의 풀이)

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

while n != 1:
    if n % k == 0:
        res += 1
        n /= k
    else:
        res += 1
        n -= 1
print(res)

 

책에서 제시한 방법)

k로 나누어 떨어지는 수가 될 때까지 한번에 뺀다.

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

while 1:
    target = (n // k) * k
    res += n - target
    n = target

    if n < k :
        break

    res += 1
    n //= k
res += (n - 1)
print(res)