Dev Chongmin

알고리즘을 공부하는 데 있어서 우선적으로 공부해야 하는 알고리즘이 있다면 세 가지가 있다고 한다.

• 그리디 알고리즘
• 탐색 알고리즘
• DP ( 동적계획법)

이 세 가지인데 그중에서 그리디 알고리즘에 대해 공부한 것을 정리하는 글

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

탐욕법이라고도 부르며 현재 상황에서 가장 좋은 것을 고르는 알고리즘이다.

현재 상황에서 가장 좋은 것을 고른다는 것은 어떠한 문제가 여러 단계로 나뉘어

차례로 알고리즘이 이어지는 경우, 그 단계마다 가장 좋은 선택을 한다는 것을 의미한다.

그러나 현재 상황에서 가장 좋은 것을 고르는 행위가 그 문제의 모든 경우의 수에서 발생하는최적의 해라는 것을 담보하지는 않는다. 그렇기에 문제를 봤을 때 이 문제가 그리디 알고리즘으로 

풀 수 있는지 추론할 수 있는 능력이 필요하다.

 문제를 그리디 알고리즘으로 풀기 위한 조건

• 각각의 값이 서로 다른 값에 영향을 주지 않을 것
• 그리디 알고리즘으로 풀어낸 값이 모든 경우의 수에서 최적의 해일 것
• 주어진 상위의 값이 하위 값의 배수일 것

세 번째 조건이 그래도 문제를 파악하는데 가장 도움이 되지 않을까 싶다.

그런데 세 번째 조건을 만족해도 그리디로 풀 수 없는 문제가 있으니 문제같다......

예제

백준 11047번 문제

필요한 동전의 최솟값을 구하는 문제로 가장 큰 가치를 가진 동전부터 차례로 나누면 

동전의 최솟값을 구 할 수 있을 것으로 보인다.

거기에 그리디 알고리즘을 적용하게 만든 가장 중요한 문장은 노랗게 칠한 문장 같다.

주어진 상위의 값이 하위 값의 배수라는 것을 알려주었으니 말이다.

N, K = map(int, input().split())
arr = []

for i in range(N):
    arr.append(int(input()))
arr.reverse()                   # 동전을 큰 수부터 계산하기 위해서

R = 0                           # 필요한 동전의 갯수
for i in arr:
    if K//i != 0:               # 조건이 없어도 되긴하다.
        R += K//i                
        K = K%i

print(R)

문제풀이 코드

이제야 한 문제 풀어본 것이기 때문에 앞으로도 문제를 풀어보면서

내가 그리디 문제인지 잘 추론할 수 있는 능력을 기르도록 해야겠다.