그리디 알고리즘

그리디 알고리즈 (탐욕법), 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미

 

이러한 트리가 있다고 할 때 Root에서 시작하는 경로중 아스키코드의 총합이 더 작은 경우의 경로를 고르라고 할 때 그리드의 경우   현재 상황에서 지금 가장 작은 아스키코드를 가지고 있는  B를 선택하게 되고 그 이후에는 D, H 순으로 경로를 고르게 됩니다. 이처럼 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 그리디 알고리즘 또는 탐욕 법이라고 말합니다.

 

그리디 알고리즘으로 분류되는 코테의 경우 그리디 알고리즘을 써도 최적의 해가 나오는 경우들만 출제합니다.

---

예시 문제

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

백준의 설탕 배달 문제 같은 경우 

3킬로그램 봉지와 5킬로그램 봉지가 있다고 할 때 N킬로그램을 배달할 때 가장 최적의 봉지 개수를 구하면 됩니다.

정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다.

 

이것을 그리드 알고리즘으로 풀게 되면 

N = int(input())
result = 0
while N >= 0:
    if N % 5 == 0:
        result += (N // 5)
        print(result)
        break
    N -= 3
    result += 1
else:
    print(-1)

이러식으로 가장 큰 수인 5를 사용하여 전부 뺄 수 있을 경우 빼주고 result에 목을 더하여 총 result를 출력합니다. 전부 뺄 수 없을 경우 그다음으로 작은 3을 하나 빼주고  result에 1을 더합니다. 이렇게 반복하여 break를 못하고 while의 조건인 N이 0 보다 작게 되면 else로 설정해놓은 -1을 출력합니다.

 

이 소스 생각보다 과정이 복잡하지만 가장 큰 수인 5부터 3으로 반복하여 검사한다는 것을 보면 이것도 그리디 알고리즘을 썼다고 할 수 있습니다.

---

그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아닙니다. 하지만 위와 같은 문제에서 적당한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적입니다.

 

그리디 알고리즘으로 문제의 해법을  찾았을 때는 이 해법이 정당한지 검증해야 합니다.