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

• 그리디 알고리즘
• 탐색 알고리즘
• 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)

문제풀이 코드

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

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

2021.12.08

백준 11047 동전 O

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

for i in range(N):
    arr.append(int(input()))

R = 0
arr.reverse()
for i in arr:
    if K//i != 0:
        R += K//i
        K = K%i

print(R)    

본래 이번 주는 DP 문제 위주로 풀려고 했는데 

친구가 그전에 그리드와 탐색문제를 먼저 풀어보는 것이 좋다고 해서 

그리드 문제로 급히 노선을 갈아탔다.

그런데 지금 문제는 풀었지만

그리드 문제의 유형이 무엇인지 그리드 알고리즘이 무엇인지 모르기 때문에

공부하고 정리하는 시간을 가져야겠다.