➕ 나동빈님 이코테에서 들은 내용을 기반으로 정리하고 공부한 게시글입니다.

✔ 그리디란?

그리디(greedy)는 '탐욕스러운'이라는 뜻으로 나에게 가장 이득이 되는, 최소한의 노력으로 최대한의 결과를 내고자 하는 것을 뜻한다.
따라서 그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만을 고르는 방법이다. 이 방법이 언제나 같은 방법으로 사용되어 최선의 결과를 나을 수 있는지 고민해야한다.

✔ 문제1 : 거스름돈

편의점에서 N원을 구매한 손님에게 500원, 100원, 50원, 10원 동전으로 돈을 거슬러줄때 동전의 최소개수를 구하시오. (단, 동전의 개수는 무한하고, 거슬러 줘야 할 돈 N원 은 항상 10의 배수)

👉 문제해결과정

1. 가장 큰 화폐단위부터 거슬러준다.

if) 3740원이면
500원 - 7개 (500원으로 줄 수 있는 돈 3500원)
100원 - 2개 (나머지 240원 중에서 100원으로 줄 수 있는 돈 200원)
50원 - 0개 (나머지 40원 중에서 500원으로 줄 수 있는 돈 0원)
10원 - 4개 (나머지 40원 중에서 10원으로 줄 수 있는 돈 40원)

총 7+2+4 = 13개의 동전이 필요하다.

n = 3740 #거스름돈
count = 0 #거스름돈에 사용될 동전의 개수

array = [500, 100, 50, 10]
for coin in array: #array에 있는 원소 하나씩 돌기( 큰 단위부터)
	# count = count + (n // coin)
    count += n // coin # 거스름돈을 해당 동전단위로 나누었을 때의 몫(동전개수)를 count에 더하기
    # n =  n % coin
    n %= coin #n은 거스름돈을 해당 동전단위로 나누었을 때의 나머지
    
print(count) #총 몇개의 동전이 필요한지

👉 정당성 분석

동전에서 큰 단위는 항상 작은 단위의 배수임으로 작은 단위의 동전들을 합하였을 때, 큰 단위의 동전들 이외의 해가 나올 수 없다.

👉 시간 복잡도 분석

화폐의 종류 = K 일때, 소스코드이 시간 복잡도는 O(K)이다.

• 빅-오-표기법에서 수행히간은 알고리즘이 수행하는 기본 연산 횟수를 뜻한다.

따라서 시간복잡도는 거스름돈의 크기와 무관하며 동전의 총 개수(종류)에만 영향을 받는다.

✔ 문제2 : 1이 될 때까지

어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행한다. 과정이 수행되어 N이 1이 되는 최소 횟수를 구한다. (단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. N과 K는 자연수이다. )
1. N에서 1을 뺀다.
2. N을 K로 나눈다.

👉 문제해결과정

1. N이 최대한 K로 많이 나누어지도록 한다.
2. 나누어지지 않을때 1을 뺀다.

if) n=37 , k=5일 때,
5로 나누어떨어지는 n보다 작거나 같은 수는 35이다.
그러면 37-35=2, 1을 2번 빼고
그다음 35 % 5 = 7, 7번 나눈다.

총 2+7 =9번 연산이 필요하다.

n, k = map(int, input().split())
count = 0 #연산 횟수

while True:
	target = (n//k) * k #n이 k로 나누어질 수 있는 가장 큰 n의 값을 찾는다(target은 k로 나누어떨어지는 n보다 작거나 같은 수)
    #count = count + (n-target)
    count += (n-target) #(n-target)은 1을 빼는 횟수
    n = count
    if n < k : # n이 k보다 작을때 while문 탈출
  		break
    # n을 k로 나누기 
    count += 1
    #n = n // k
    n //= k


if n > 1: # n이 1보다 크다면
	count++
    n--
else:
	print(count)

👉 정당성 분석

1을 빼는 것보다 K로 나누는 것이 N의 수가 작아지는 방법이다.

👉 시간 복잡도 분석

while을 사용하게 되면 시간복잡도가 로그값이 나온다.

• 로그시간복잡도

✔ 문제3 : 곱하기 혹은 더하기

각 자리 숫자가(0~9)로 이루어진 문자열 S 왼쪽부터 오른쪽으로 각 숫자에 'x' 혹은 '+' 연산자를 넣어 가장 큰 수를 만든다. ( 단 모든 연산은 왼쪽에서부터 이루어진다. 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.)

👉 문제해결과정

1. 연속해 있는 두 수 중, 하나라도 0또는 1인 경우 -> +
2. 그 이외의 경우(두 수가 모두 2 이상일 때)는 -> x

if) 07315 일때
((((0+7)*3)+1)+5)

data = input()

front = int(data[0]) #앞에있는 값

for i in range(1, len(data)):
	back = int(data[i]) #뒤에있는 값
    if front <=1 or back <=1:
    	front += back
    else:
    	front *= back
        
print(front)

👉 정당성 분석

일반적으로 +보다 x가 값을 더 크게 만든다. 하지만 두 수 중, 하나라도 0또는 1인 경우는 +가 값을 더 크게 만든다.

✔ 문제3 : 모험가 길드

각 모험가가 가지고있는 공포도 N이 있다. 각 모험가 그룹는 공포도가 X인 모험가는 반드시 X명 이상 구성되어야한다. 최대 몇개의 모험가 그룹을 만들 수 있는가?( 모든 모험가가 그룹에 들어갈 필요는 없다.)

👉 문제해결과정

1. 공포도를 오름차순으로 정렬한다.
2. 가장 낮은 공포도 부터 차례대로 확인한다.
3. 현재 확인하고 있는 공포도의 크기(수) 만큼 현재 확인하고 있는 공포도를 가진 모험가 존재한다면 이를 그룹으로 묶는다.

n = int(input())
data = list(map(int, input().split())) #공포도 리스트
data.sort() #오름차순 정렬

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

for i in data: # 공포도를 낮은 것부터 하나씩 확인
	member += 1 #현재 그룹에 해당 모험가를 포함시키기
    if member >= i: #i는 공포도, 현재 그룹에 포함된 모험가의 수가 현재 공포도 이상이라면, 그룹 결성
    	result += 1 #총 그룹의 수 증가시키기
        member = 0 #현재 그룹에 포함된 모험가의 수 초기화

print(result)

👉 정당성 분석

그룹수를 최대로 만들려면 가장 작은 단위로 묶어야한다. 따라서 오름차순 정렬 후 , 공포도와 현재 그룹의 멤버수를 비교해야한다.

🌱 결론

그리디 알고리즘에서는 문제 풀이를 위한 최소한의 아이디어로 모든 상황에 적용시켜 최적의 해를 구할 수 있는지, 그리고 이 아이디어가 정당한지 검토한다!