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

📌 그리디 알고리즘 (탐욕법)

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미
• 최적의 해를 구할 수 있는지 검토하는 과정 필요
• 탐욕법으로 얻은 해가 최적의 해가 되는 경우에 한 해서 출제되는 경우有

---

✅ 문제 - 거스름 돈

- 그리디 알고리즘 설명을 위한 문제 예시로 많이 쓰임

거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정
손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수는?
(단, 거슬러 줘야 할 돈 N은 항상 10의 배수)

💡 해결 아이디어

• 가장 큰 화페 단위부터!

🔎 정당성 분석

• 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
• 만약에 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면?
  • 500원 1개, 100원 3개 총 4개지만 400원 2개로 거슬러 줄 수 있음
  • 큰 단위가 작은 단위의 배수가 아니라면 이와 같은 알고리즘을 이용해서 최적의 해를 보장할 수 없음

📄 예시 답안

n = 1260
count = 0

# 큰 단위의 화페부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin # 해당 화페로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)
# 6

⏰ 시간 복잡도

• 화폐의 종류가 K라고 할 때, O(K)
  • 거슬러줘야 하는 돈과 무관하며, 동전의 총 종류에만 영향을 받음

---

✅ 문제 - 1이 될 때까지

어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행하려 함
1. N - 1
2. N // K (단, N이 K로 나누어 떨어질 때만 선택할 수 있음)
N과 K가 주어질 때 N이 될 때까지 1번 혹은 2을 수행해야 하는 최소 횟수는?

💡 해결 아이디어

• 최대한 많이 나누기
• 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음

🔎 정당성 분석

• N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있음
• K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음
  • 또한 N은 항상 1에 도달 (최적의 해 성립)

📄 예시 답안

# N, K을 공백을 기준으로 구분하여 입력받기
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)

📄 내 코드

n, k = map(int,input().split())
cnt = 0
while(True):
  if n%k!=0:
    n-=1
  else:
    n//=k  
  cnt+=1

  if n==1:
    break

print(cnt)

⏰ 시간 복잡도

• 문제 조건을 확인해보면 N과 K가 10만 이하의 정수이기 때문에 if~else 활용한 내 코드처럼 간단히 작성해도 됨
• 하지만 반복문이 한 번 반복이 될 때마다 바로 n이 k로 나누어 지는 연산이 수행되기 때문에 반복횟수에 따라서 기하급수적으로 N이 빠르게 줄어들게 됨
• 즉, 로그 시간 복잡도가 나올 수 있게 함

---

✅ 문제 - 곱하기 혹은 더하기

숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수는?
(단, 모든 연산은 왼쪽에서 부터 순서대로)

💡 해결 아이디어

• 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1 이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하면 정답

🔎 정당성 분석

• N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있음
• K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음
  • 또한 N은 항상 1에 도달 (최적의 해 성립)

📄 예시 답안

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
    # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <=1:
        result += num
    else:
        result *= num

print(result)

---

✅ 문제 - 모험가 길드

공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정함
N명의 모험가 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값은?

💡 해결 아이디어

• 오름차순 정렬 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인
• '현재 그룹에 포함된 모험가의 수'가 '현재 확인하고 있는 공포도'보다 크거나 같다면 이를 그룹으로 설정

🔎 정당성 분석

• N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있음
• K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음
  • 또한 N은 항상 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) # 총 그룹의 수 출력