[알고리즘] Greedy Algorithm(그리디 알고리즘)

*Greedy Algorithm(그리디 알고리즘)

: 일명 탐욕법. 현재 상황에서 지금 당장 좋은 것만 고르는 방법

최소한의 아이디어를 떠올릴 수 있어야 문제를 풀 수 있다. -> 정당성 분석이 가장 중요!

* 상당수의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해라는 것을 추론할 수 있어야 풀리도록 출제!

 

[대표 문제 1] 거스름 돈

 : 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.
-> 가장 적은 양의 동전을 거슬러 주는 최적의 해

=> 이것이 최적의 해라는 근거(정당성)?
: 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문!
-> 그렇지 않다면 가장 큰 화폐 단위부터 거슬러 주는 것이 최적의 해가 아닐 수 있다.

n = 1260
count = 0

coin = [500, 100, 50, 10]

for i in coin:
    count += n//i
    n %= i

print(count)

>>> 6 
: 6개의 동전을 사용하는 것이 최적의 해

* 화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)이다.

 

[대표 문제 2] 1이 될 때까지

 : 주어진 N에 대해서 최대한 많이 나누기를 수행하면 된다.
-> 빼기보다 나누기가 수를 더 많이 줄일 수 있어서, 더 빠르게 1이 될 수 있다!

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

while (n >=k):
    if n % k  != 0:
        n -= 1
        count += 1
    n //= 1
    count += 1

while (n >1):
    n -= 1
    count +=1

print(count)

 

[대표 문제 3] 곱하기 혹은 더하기 

 : 두 수 중에서 하나라도 0 혹은 1일 경우만 곱하기보다 더하기가 더 효율적이다.
따라서 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 0 또는 1인 경우에는 더하기, 나머지는 곱하기를 수행

S = input()

result = int(S[0])

for i in range(1, len(S)):
    number = int(S[i])

    if number <= 1 or result <= 1:
        result += number

    else : 
        result *= number

print(result)

 

[대표 문제 4] 큰 수의 법칙

 : 가장 큰 수를 최대 K번 더하고 다음은 두 번째로 큰 수를 한 번만 더하고 다시 가장 큰 수를 최대로 더하는 방식

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)

 

[대표 문제 5] 숫자 카드 게임

 : 주어지는 입력값의 각 행마다 가장 작은 값들을 비교하여 그중 가장 큰 값을 선택

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)    

 

[대표 문제 6] 모험가 길드

 : 가장 공포도가 낮은 모험가부터 그룹에 합류시키기

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

data.sort()
group = 0
member = 0

for i in data:
    member += 1
    if member >= i:
        group += 1
        member = 0
print(group)

---

강의 내용 출처 - https://youtu.be/g4nfN7Jw-yg