12장 그리디(Greedy)[PYTHON]

목차
1. 그리디 알고리즘
2. 문제 풀이
3. 느낀점

그리디 알고리즘

그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다.
다른 알고리즘에 비해 상대적으로 구현하기 쉽지만 항상 해를 구할 수 있는 것은 아니다.
따라서 문제를 보고 그리디 알고리즘을 적용할 수 있는 문제인가 판단하는 능력이 필요하다.

문제 풀이

문제는 백준 11047번 동전 개수의 최솟값구하기를 예시로 들어보겠다.
BOJ_11047번
문제에서 한 동전 다음의 동전은 이전 동전의 배수라는 조건이 있기 때문에 그리디 알고리즘으로 풀 수 있다.
문제 풀이에 대한 생각은 다음과 같다.

• 동전의 가치가 큰쪽부터 탐색한다.
• cnt += (K) // (현재 동전의 가치)
• K = K % (현재 동전의 가치)
• 만약 나머지가 0이라면 종료

코드로 나타내면 다음과 같다.

import sys

input = sys.stdin.readline
N,K = map(int,input().split())
coin = []
for _ in range(N):
    c = int(input())
    coin.append(c)
    
idx = N - 1
cnt = 0
while True:
    if K - coin[idx] < 0:
        idx -= 1
    elif K - coin[idx] >= 0:
        K -= coin[idx]
        cnt += 1
    if K == 0:
        print(cnt)
        break

느낀점

그리디에 관한 개념은 별다른게 없다.
하지만 문제에 접했을 때 그리디 알고리즘으로 풀 수 있는지 확인하는 능력은 좀처럼 기르기 어려운 것 같다.
또한 그리디 알고리즘을 쓰려면 증명을 해내야하는데 그 과정이 상당히 까다로운 경우가 많다.
많은 문제를 접해보면서 경험을 쌓도록 노력해야겠다.