[알고리즘] 그리디(탐욕법) with Python

💡 그리디 알고리즘

"지금 당장 좋은 것만 고르는 방법"

한국어로 번역하면 탐욕법이라고 할 수 있는데, 이름 그대로 어떠한 문제가 생겼을 때 단순 무식하게 탐욕적으로 문제를 해결하는 알고리즘이다. 단순하지만 강력한 문제 해결방법이다.

💡 그리디 알고리즘 사용시 주의점

그리디 알고리즘의 해가 '최적 해'를 항상 보장하는 것은 아니다. 때문에 그리디 알고리즘을 적용할 때 주의해야할 것은 "해당 방법이 정당성을 가지고 있는가?"이다.

💡 그리디 알고리즘 대표적 예시

Q1. 거스름돈 구하기

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

 

[문제의 아이디어]

: "가장 큰 화폐 단위부터 돈을 거슬러주자."

가장 큰 화폐 단위를 최대한 활용해서 거슬러줬을때 동전의 최소 개수를 사용할 수 있으므로 해당 문제에서 그리디 해법은 정당성을 가지고 있다라고 할 수 있다.

 

[코드]

n = 2470

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n//coin # 해당 단위의 화폐로 거슬러줄 수 있는 동전 갯수
	n = n%coin # 아직 거슬러줘야할 돈
print(count)

 

 

---

💡 그리디 알고리즘 예시

Q1. 1이 될 때까지

 어떠한 수 N이 1이 될때까지 다음의 두과정 중 하나를 반복적으로 선택하여 수행하려고한다. 단 두번째 연산은 N이 나누어 떨어질 때만 선택할 수 있다.

방법 1) N에서 1을 뺀다.

방법 2) N을 K로 나눈다.

N과 K가 주어질때 N이 1이 될때까지 1번 또는 2번 과정을 수행해야하는 최소횟수를 구하는 프로그램을 작성하시오.

 

* 입력조건

- 첫번째 줄에 N(2<N<100,000)과 K(2<K<100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 K보다 크거나 같다.

* 출력조건

- N이 1이될때 까지 1번 혹은 2번 과정을 수행해야하는 횟수의 최솟값을 출력

 

입력 예시 : 25 5

출력 예시 : 2

 

[문제의 아이디어]

: "최대한 많이 나누자."

어떠한 수가 있을 때 (방법 1)을 선택하는 것보다 (방법 2)를 선택하는 것이 더 빠르게 1이라는 숫자에 도달 할 수 있다. 

 

[코드]

n, k = map(int, input().split())
count = 0

while n!=1:
  if n%k ==0:
    n=n//k
    count+=1
  else:
    n=n-1
    count+=1
print(count)

---

Q2. 곱하기 혹은 더하기

각 자리가 숫자로만 이루어진 문자열 S가 주어질 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X'또는 '+'연산자를 넣어 만들 수 있는 가장큰 수를 구하는 프로그램을 작성하세요. 단, 일반적인 사칙연산 방식 이아닌, 모든 연산은 외쪽에서부터 순서대로 이루어진다고 가정합니다.

 

*입력 조건

- 첫째줄에 여러개의 숫자로 구성된 하나의 문자열 S가 주어집니다.(1<=S의길이<=20)

*출력 조건

- 첫째줄에 만들 수 있는 가장 큰수를 출력합니다.

 

입력 예시 : 02984

출력 예시 : 576

 

[문제 아이디어]

:"0이나 1이 아니라면 곱하는게 좋다"

 

[코드]

data = list(map(int, input()))
result = 0

for i in data:
  # 0이나 1이라면 더하자
  if i<=1 or result <=1:
    result += i
  else: # 아니라면 곱하자
    result *= i

print(result)

 

---

Q3. 모험가 길드⭐

  한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했는데 공포도가 높은 모험가는 쉽게 공포를 느껴 위험상황에서 제대로 대처할 능력이 떨어집니다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠나도록 규정했습니다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 수의 최대값을 구하는 프로그램을 작성하세요. 

  예를 들어 N=5이고 각 모험가의 공포도가 "2 3 1 2 2"이라고 가정합시다.

이때 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고 그룹2에 공포도가 2인 남은 두명을 넣게되면 총 2개의 그룹을 만들 수 있습니다. 또한 몇명의 모험가는 마을에 그대로 남아있어도 됩니다.

 

*입력 조건

- 첫째 줄에 모험가의 수 N이 주어집니다.(1<=N<=100,000)

- 둘째 줄에 각 모험가의 공포도의 값을 N이하의 자연수로 주어지며 각 자연수는 공백으로 구분합니다.

*출력 조건

-여행을 떠날 수 있는 그룹의 최댓값을 출력합니다

 

*입력 예시

5

2 3 1 2 2

*출력 예시

2

 

[문제 아이디어]

"공포도가 낮은 사람들은 빨리 묶어서 보내고 높은 사람은 차라리 안보내는게 나을 수 있다."

->공포도를 기준으로 오름차순 정렬을 한다.

공포도가 가장 낮은 모험가부터 하나씩 확인하며 그룹에 포함될 모험가의 수를 계산한다.

만약 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면 그룹을 결성할 수 있다.

 

[코드]

n = int(input())
adventure = list(map(int, input().split()))

adventure.sort() # 공포도를 기준으로 정렬

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수

for a in adventure:
  count += 1 # 모험가를 현재 그룹에 포함시킨다
  if count >= a: # 공포도보다 그룹의 모험가의 수가 크다면 빨리 출발시키자
    result += 1
    count = 0 # 그룹 초기화

print(result)

 

 

출처 참고 :

https://youtu.be/2zjoKjt97vQ

동일한 문제이며, 코드를 저에게 맞춰 약간씩 변형하였습니다.