그리디 알고리즘(Greedy Algorithm)은 현재 상태에서 가장 최선의 선택을 반복하며 전체 문제를 해결하는 알고리즘 기법입니다. 이번에는 그리디 알고리즘의 개념과 3단계를 정리하고, 백준 11047번 “동전 0” 문제를 활용하여 이를 설명해보겠습니다.

1. 그리디 알고리즘 개념

그리디 알고리즘은 전체 최적해를 찾는 것이 아닌, 각 단계에서 최선의 선택을 하는 방식으로 진행됩니다. 하지만 이러한 방식이 항상 최적해를 보장하지는 않기 때문에, 문제마다 적용 가능성을 고려해야 합니다.

1.1 그리디 알고리즘의 3단계

1. 최적해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 문제의 제약조건을 만족하는지 검사한다.
3. 최적해 검사: 지금까지 선택한 해가 전체 문제를 해결할 수 있는지 확인한다. 해결되지 않았다면 1단계로 돌아가 반복한다.

2. 예제: 백준 11047번 “동전 0”

2.1 문제 설명

• N개의 동전 종류가 주어지고, 목표 금액 K를 만들기 위해 최소한의 동전을 사용해야 합니다.
• 가장 큰 단위의 동전부터 사용하여 최적해를 찾아야 합니다.

2.2 코드 구현 (Python)

import sys

n, k = map(int, sys.stdin.readline().split())  # 동전 개수와 목표 금액 입력
coin = []
for i in range(n):
    coin.append(int(sys.stdin.readline().strip()))  # 동전 종류 입력

count = 0  # 사용한 동전 개수

while True:
    if k == 0:  # 목표 금액이 0원이 되면 종료
        break
    for i in range(len(coin)-1, -1, -1):  # 큰 동전부터 탐색
        if coin[i] <= k:  # 현재 동전이 목표 금액보다 작거나 같을 경우
            mok = k // coin[i]  # 해당 동전으로 채울 수 있는 개수 계산
            k -= coin[i] * mok  # 목표 금액에서 사용한 금액 빼기
            count += mok  # 사용한 동전 개수 추가
            break  # 다시 큰 동전부터 탐색

sys.stdout.write(f"{count}")  # 결과 출력

3. 코드 분석: 그리디 알고리즘의 적용

3.1 최적해 선택 (Greedy Choice)

• 가장 큰 가치의 동전부터 사용하여 목표 금액을 채우려고 합니다.
• for i in range(len(coin)-1, -1, -1): 부분에서 동전 리스트를 역순으로 탐색하며 최적해를 선택합니다.
• if coin[i] <= k: 조건을 통해 현재 동전이 목표 금액보다 작거나 같은 경우에만 사용하도록 합니다.

3.2 적절성 검사 (Feasibility Check)

• mok = k // coin[i] 연산을 통해 해당 동전을 사용할 수 있는 최대 개수를 계산합니다.
• k -= coin[i] * mok 부분에서 현재 선택한 동전을 사용한 후 남은 금액을 계산합니다.
• 이 과정에서 목표 금액이 0이 되지 않으면 다음 단계로 넘어가 다른 동전을 탐색합니다.

3.3 최적해 검사 (Solution Check)

• if k == 0: 조건을 통해 목표 금액이 0원이 되었는지를 검사합니다.
• 목표 금액이 0이 되면 break를 통해 반복문을 종료하고, 최종적으로 최소 동전 개수를 출력합니다.

4. 시간 복잡도 분석

이 알고리즘의 시간 복잡도를 계산해보면:

1. 동전 리스트를 입력받아 저장하는 과정: O(N)
2. 동전을 큰 순서대로 탐색하는 반복문: O(N)
3. 각 동전에 대해 몫을 계산하는 연산: O(1)

총 O(N)의 시간 복잡도를 가지며, 이는 매우 효율적입니다.

5. 정리

그리디 알고리즘은 항상 최적해를 보장하지 않지만, 이 문제에서는 항상 최적의 선택이 전체 최적해를 보장하기 때문에 적용이 가능합니다. 동전 단위가 배수 관계에 있는 경우, 항상 큰 단위부터 채우는 것이 최적해가 됩니다. 하지만 동전 단위가 배수 관계가 아닐 경우에는 다르게 접근해야 합니다.