그리디 (Greedy) 알고리즘

그리디 (Greedy) 알고리즘이란?

1. 현재 상황에서 지금 당장 좋은 것만 고르는 방법

2. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.

3. 간혹 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 암시하는 경우도 있음.

4. 대부분의 문제는 그리디 알고리즘을 사용했을 때 ‘최적의 해’를 찾을 수 없을 가능성이 다분.
   • 예를 들면, 가지고 있는 동전 중에서 가장 큰 단위가 작은 단위의 배수가 아닌 경우.
   • 위와 같은 경우는 다이나믹 프로그래밍 (Dynamic Programming)을 통해 해결할 수 있을 가능성이 있음.
5. 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘부터 적용해서 정당한지 체크!

예제 문제

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

1. n에서 1을 뺀다.
2. n을 k로 나눈다.

n이 1이 될 때까지 1번 혹은 2번 과정을 수행해야 하는 최소 횟수는?

import sys

n, k = map(int, sys.stdin.readline().split())

idx = 0

while n != 1:
    if n % k == 0:
        n /= k
        idx += 1
    else:
        n -= 1
        idx += 1

2번 연산을 수행할 수 있으면 우선적으로 수행해야 연산 횟수를 줄일 수 있음. 따라서 greedy 알고리즘으로 분류.