[알고리즘] Greedy Algorithm

Greedy Algorithm

탐욕적(Greedy)으로 문제를 해결하는 알고리즘

탐욕적(Greedy)이란?
현재 상황에서 지금 당장 좋은 것만 고르는 방법

특징

알고리즘 문제의 폭이 매우 넓다. 단순 암기보단 많은 유형에 대한 연습이 필요

문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는가?
단순히 현 상황에서 가장 좋아 보이는 것만을 선택(탐욕적)해도 문제를 풀 수 있는가?

문제 : 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복적으로 선택하여 수행한다.
단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

입력 조건 : 첫째 줄에 N (2 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력조건 : 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행하야하는 횟수의 최솟값을 출력한다.

#1 나누기가 가능한 경우 2번 연산, 그렇지 않은 경우 1번 연산

#1이 될 때 까지
n, k = map(int, input().split())

count = 0

while True:
  if n == 1:
    break
  
  if n%k == 0:
    n = n//k
  else:
    n -= 1
  count += 1

print(count)

가장 생각하기 쉬운 아이디어 하지만 각 연산과정 마다 if 연산이 필요하다.

#2 N을 K의 배수로 만들기

1. N이 K의 배수가 될 때까지 1씩 빼기
2. N을 K로 나누기

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

count = 0

while n >= k:
  while n % k != 0: # N이 K로 나누어 떨어지지 않는다면
    n -= 1
    count += 1

  n //= k
  count += 1

while n > 1: # n이 k보다 작은 경우 더 이상 나눌수 없어 1씩 뺀다
  n -= 1
  count += 1

print(count)

N을 K의 배수로 먼저 만드는 과정 이후 각 조건에 따른 연산을 반복 수행한다.

#3 #2의 과정을 한 번에 수행하기

1. N이 K의 배수가 되도록 한번에 연산하기
2. N이 K보다 작은 경우 한번에 1로 만들기

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

count = 0

while True:
  target = (n//k)*k   # n보다 작은 k로 나누어 떨어지는 수
  count += (n-target) # target이 될 때까지 -1의 횟수
  n = target

  if n < k: # n이 k보다 작으면 더 이상 나눌 수 없다
    break

  count += 1
  n //= k

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

print(count)

반복적인 -1 연산을 한 번에 수행한다.

정리

그리디 알고리즘은 현재의 선택이 나중에 미칠 영향을 크게 고려하지 않는다.
현재에서의 최선의 선택을 하는 것

해결과정에서 나타나는 반복과 규칙을 이용한다면 코드의 실제 계산 횟수를 효율적으로 줄일 수 있다.

참고

나동빈(2020).이것이 취업을 위한 코딩 테스트다 with 파이썬.한빛미디어