[이코테 강좌] Greedy(탐욕법)

출처

• 이 포스팅은 아래의 강좌를 진행하며 정리한 글입니다.

  (이코테 2021 강의 몰아보기) 2. 그리디 & 구현

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
• 정당성 분석
  • 가장 좋아보이는 것만 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토
• 최적의 해를 보장할 수 없을 때가 많음
• 그리디 문제로 주어졌다면(탐욕법으로 풀 수 있는 문제라면), 어떠한 접근으로 그리디로 풀 수 있을지 접근방식을 추론할 수 있어야한다.

문제: 거스름 돈

• 500, 100, 50, 10원 짜리 동전을 무한하게 가지고 있음
• 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수 구하기
  • N은 항상 10의 배수

풀이

• 가장 큰 화폐 단위부터 돈을 거슬러 주기
• 500원에서 부터 100, 50, 10 순서대로 거슬러 줄 수 있을만큼 거슬러 주기
• N = 1,260원
  • 500 * 2 = 1000
  • 100 * 2 = 200
  • 50 * 1 = 50
  • 10 * 1 = 10

정당성 분석

• 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
• N = 800, 화폐 단위가 500, 400, 100이라면 위와 같은 방법으로는 최적의 해가 나올 수 없다.
  • 400 * 2 = 800

코드

n = 1260
cnt = 0

arr = [500, 100, 50, 10]

for coin in arr:
  cnt += n // coin
  n %= coin

print(cnt)

시간 복잡도 분석

• K = 화폐의 종류의 수
• 시간 복잡도 = O(K)

문제: 1이 될 때까지

• N이 1이 될 때까지 다음의 두 과정을 반복적으로 선택하여 수행
  • N에서 1을 뺀다
  • N을 K로 나눈다 (나누어 떨어질 때만 선택 가능)
• N과 K가 주어질 때 N이 1이 될 때까지 수행해야되는 과정의 최소 횟수 구하기
  • 1 <= N <= 100,000
  • 2 <= K <= 100,000

풀이

• K로 나눌 수 있을 때 먼저 나눠주기
• 나누지 못할 때는 나눌 수 있을 때까지 1 빼주기
• 25 3
  • 25 - 1 = 24
  • 24 / 3 = 8
  • 8 - 1 = 7
  • 7 - 1 = 6
  • 6 / 3 = 2
  • 2 - 1 = 1

정당성 분석

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

코드

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

while True:
  target = (n // k) * k # k로 나눌 수 있고 n보다 작고 n에서 가장 가까운 수
  cnt += (n-target) # n이랑 차이 나는 만큼 빼주어야 함
  n = target
  # n을 k로 더이상 나눌 수 없을 때 반복문 탈출
  if n < k:
    break
  # k로 나누기
  cnt += 1
  n //= k

# 남은 수에 대해 1이 될 때까지 빼기
cnt += (n-1)

print(cnt)

문제: 곱하기 혹은 더하기

• 숫자(0부터 9)로만 이루어진 문자열 S
• 숫자 사이에 ‘×’혹은 ‘+’ 연산자를 넣어 만들어질 수 있는 가장 큰 수 구하기
• 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정
  • 1 <= S의 길이 <= 20

풀이

• 두 수 중 하나라도 0이거나 1이라면 + 아니라면 ×
• 02984
  • ((((0 + 2) × 9) × 8) × 4) = 576

정당성 분석

• 두 수 모두 2 이상이라면 곱하기가 훨씬 더 수를 크게 만든다.

코드

s = input()
result = int(s[0]) # 첫 번째 숫자로 시작

for i in range(1, len(s)):
  # 두 수 중에 하나라도 0이거나 1이라면 더하기 수행
  num = int(s[i])
  if num <= 1 or result <= 1:
    result += num
  else:
    result *= num

print(result)

문제: 모험가 길드

• 모험가 N명
• 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여
• 여행을 떠날 수 있는 그룹 수의 최댓값 구하기
• 모든 모험가를 그룹에 넣을 필요는 없다.
  • 1 <= N <= 100,000
  • X <= N

풀이

• 오름차 순으로 정렬
• 공포도가 낮은 순으로 확인하며 현재 그룹에 포함된 모험가 수가 현재 확인하고 있는 공포도보다 크거나 같다면 그룹으로 설정
• 2 3 1 2 2
  • 1 2 2 2 3 (오름차순 정렬)
  • (1) 2 2 2 3
  • (1) (2 2) 2 3

정당성 분석

• 공포도가 오름차순으로 정렬되어있어 항상 최소한의 모험가 수만 포함하는 그룹을 만들게 된다.

코드

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

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

for i in data:
  cnt += 1 # 현재 그룹에 현재 모험가 추가
  if cnt >= i: # 현재 그룹에 포함된 모험가 수가 현재 모험가의 공포도 이상이라면 그룹 결성
    result += 1 # 그룹 수 증가
    cnt = 0 # 현재 그룹 모험가 수 초기화

print(result)