[Algorithm_Greedy]_1. 그리디(탐욕법)

Greedy

그리디(탐욕법)알고리즘은 단순하지만 가장 강력한 문제 해결방법이다. 

탐욕법이라고 하는 이유는 단순 무식하게 탐욕적으로 풀어서 그런것 같습니다 

여기서 탐욕적이라는 말은 현재 상황에서 가장 좋은 것만 고르는 방법을 의미합니다.

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 보통 문제에서

/가장 큰 순서대로, 가장 작은 순서대로/ -> 정렬알고리즘과 결합하여 자주 출제됩니다.

---

대표적인 그리디알고리즘 문제는 거스름돈 문제입니다.

 

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 하는 동전의 최소 개수를 구하라 

N은 10의 배수이다.

 

n = 1270
count = 0

# 큰단위의 화폐부터 차례대로 확인하기 -> 정렬
list1 = [500, 100, 50, 10]
for coin in list1:
	count + = n//coin
    n%= coin
    
print(count)

코드는 이러한형식으로 진행될 것입니다. 

 

코딩 테스트의 대부분의 문제는 그리디 알고리즘을 이용해서 '최적의 해' 찾을 수 없을 가능성이 다분합니다. 그래서 그리디알고리즘으로 문제 해법을 찾았을때는 그 로직이 정당한지 검토해야합니다. 위와 같은 거스름돈 문제는 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 가능한것입니다.!

백준 알고리즘에서 그리디 풀어보았습니다. 

 

---

백준 알고리즘 11034번 : 캥거루 세마리2

 

캥거루 세 마리가 사막에서 놀고 있다. 사막에는 수직선이 하나 있고, 캥거루는 서로 다른 한 좌표 위에 있다.

한 번 움직일 때, 바깥쪽의 두 캥거루 중 한 마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다.

캥거루는 최대 몇 번 움직일 수 있을까?

 

while True:
    try:
        A,B,C = map(int, input().split())


        d = max(B - A, C - B)

        print(d - 1)
    except:
        break