그리디 알고리즘이란?, 백준 설탕배달

탐욕 알고리즘(Greedy Algorithm)이란?

• Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
• 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
• 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다.
• 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.
• 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

최선의 선택이란?

서울에서 대구를 거쳐 부산까지 가는최단 경로를 찾는다고 가정해보자. 그림에서 보듯이, 서울에서 대구까지 가는 경로는 3가지가 있으며, 부산까지도 마찬가지로 3가지 경로가 있다. 서울에서 부산까지 가는 최단 경로는 200 + 80 = 280이다. 이 경로는 서울에서 대구까지 가는 최단 경로(200)과 대구에서 부산까지 가는 최단 경로(80)으로 구성된다. 즉 서울에서 대구를 거쳐 부산까지 가는 최단 경로 (최선의 선택)이란 서울에서 대구까지 가는 최단 경로와 대구에서 부산까지 가는 최단 경로 문제의 해결 방법의 합이다. 따라서 문제의 최적 해결방법 부분은 부분 문제에 대한 최적 해결 방법으로 구성된다.

 

 

그리디 알고리즘을 적용하기 위한 조건

그리디 알고리즘을 사용하기 위해 필요한 조건은 2가지가 있다.

1. 탐욕스러운 선택조건

2. 최적 부분 구조 조건

 

1. 탐욕스러운 선택 조건

탐욕적인 선택은 항상 안전하다는 것이 보장되어야 한다. 여기서 "안전하다" 라는 것은 이 선택으로 인해 전체 문제의 최적해를 도출할 수 있어야 한다는 뜻이다.

 

그러나 그리디 알고리즘은 최적해를 보장해주지 않는다.

즉 그리디 알고리즘을 사용해 푸는 문제가 나왔을때 그리디 알고리즘을 사용하면 최적해가 나올 수 있는 문제인가?를 판단해야한다.

 

2. 최적 부분 구조 조건

문제에 대한 최정 해결 방법이 부분 문제에 대해서도 최적의 해결 방법이여야 한다는 조건이다.

즉 전체 문제의 안에는 여러 단계가 존재하고, 이 여러 단계 내의 하나 하나의 단계에 대해 최적해가 도출되어야 한다는 것

 

 

예시 문제 풀기

sugar = int(input())

bag = 0
while sugar >= 0 :
    if sugar % 5 == 0 :  # 5의 배수이면
        bag += (sugar // 5)  # 5로 나눈 몫을 구해야 정수가 됨
        print(bag)
        break
    sugar -= 3  
    bag += 1  # 5의 배수가 될 때까지 설탕-3, 봉지+1
else :
    print(-1)

그리디의 가장 대표적인 문제 거스름돈문제와 유사한 거스름 설탕? 문제다.

 

이 문제에서 생각할 수 있는것은 '가장 큰 단위의 설탕부터 생각하자' 다. 만약 18킬로그램의 설탕을 나눠 담아야 한다고 하면 이것을 3킬로봉지 6개로 담을수도있고, 다양한 방법이 있을 수도 있지만, 조건에서는 '최소 개수'를 구하는 문제이므로 가장 큰 단위부터 나눠 담고 나머지를 그 다음 단위의 봉지로 나눠 담는 해결방법을 떠올릴 수 있다.