이것이 코테다 영상 강의 - 그리디

그리디 알고리즘

• 탐욕법이라고도 하는 알고리즘이다.
• 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.
• 그리디를 사용해도 최적의 해를 구할 수 있는지 확인해 봐야하고, 정당성 분석 또한 이루어져야 한다.

대표 문제

거스름 돈

n = 1260
count = 0

# 화폐단위
money = [500, 100, 50, 10]

for coin in money:
	count += n // coin
    n %= coin
    
print(count)

• 동전의 갯수를 가장 적게 줄 수 있을 때의 동전 갯수 출력 문제이다.
• 당연히 큰 단위의 화폐부터 거슬러 줘야 함으로 전형적인 그리디 문제이다.

• 화폐의 종류가 k라고 할 때, 시간 복잡도는 $O(k)$이다.

1이 될 때까지

#1이 될 때까지
## 입력 받기
n, k = map(int, input().split())
result = 0

while True:
    ## N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n//k) * k
    result += (n - target)
    n = target
    ## N이 K 보다 작을 때 (나눌 수 없을 때) 탈출
    if n < k:
        break
    ## K로 나누기
    result += 1
    n //= k

## 마지막 남은 수에 대하여 1씩 빼기
result += (n-1)
print(result)

• 1 빼기 or k로 나누기 두 가지 연산만 갖고 최소의 계산으로 n을 1로 만드는 문제
• 1 빼기보다 k로 나누기가 항상 빠르니 정당성이 성립된다. -> 그리디

곱하기 혹은 더하기

n = input()

result = int(n[0])

for i in range(1, len(n)):
    num = int(n[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

• 주어진 정수 문자열을 왼쪽에서부터 오른쪽으로 더하거나 곱해서 최대값 만드는 문제
• 0이나 1은 더해주고 나머지는 항상 곱하는 것이 항상 빠르다.

모험가 길드

#모험가 길드
n = int(input())
data = list(map(int, input().split()))
##오름차순 정렬
data.sort()

result = 0  #총 그룹 수
count = 0   #현재 그룹에 포함된 모험가의 수

for i in data:
    count += 1
    if count >= i:
        result += 1
        count = 0

print(result)