그리디

그리디 알고리즘이란?

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 정당성 분석이 중요 
➡️ 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토가 필요한 기법이다.
(일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.)

 

EX. 거스름 돈 문제

문제: 1260원을 거슬러주어야 할 때 가장 적은 숫자의 화폐를 이용해 거슬러주는 경우에 대해서 찾아본다.

답: 최적의 해를 빠르게 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러주면 된다.
N원을 거슬러줘야할 때, 가장 먼저 500원으로 거슬러 줄 수 있을만큼 거슬러 준다. 이후로 100원, 10원으로 거슬러주기

 

➡️ 정당성 분석
가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.

 cf. 800원을 거슬러줄 때 회폐가 500원, 400원, 100원이라면 500원은 400원의 배수가 아니기 때문에 문제가 생긴다. 400 *2 = 800

결론: 그리디 알고리즘은 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야한다.

 

코드

n=1260
count=0

#배열 생성
#큰 단위의 화폐부터 차례대로 확인
array=[500,100,50,10]

#반복문 사용하기
for coin in array:
	count+=n//coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기 
    n%=coin #남은 금액 계산
    
print(count)

 

➡️ 알고리즘 분석

화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(k)이다. 화폐의 종류만큼 반복하면 된다.

 

예제 풀어보기

문제 1) 1이 될 때 까지

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

2. N을 K로 나눕니다.

 

➡️ 정당성 분석

가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있을까?

k가 2 이상이기만하면 k로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있다. 
+ N은 항상 1에 도달한다 (= 최적의 해이다.)

 

#n,k를 공백을 기준으로 구분하여 입력 받기
n,k=map (int, input().split())
result=0

#for 문이 아닌 while 문으로 반복문
while True: 
	#테크닉, n이 k로 나누어지지 않을 때 나누어지는 가장 큰 값을 찾을 수 있음 -> 1을 빼는 연산을 몇 번 반복할지 계산할 수 있음.
	target=(n//k)*k
	result += (n-target)
    n=target

	#더 나누지 못할 때 종료
    if(n<k):
    	break
        
    result+=1
    n//=k
    
result+=(n-1)
print(result)

위 테크닉이면 시간 복잡도가 줄어들 수 있으니 사용할 수 있다면 사용하자.

 

문제 2) 곱하기 혹은 더하기
각 자리가 숫자(0부터 9)로만 이루어진 문자열 5가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하여 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단 +보다 x를 먼저 계산하는 일반적인 방식과 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

 

아이디어) 대부분은 '+'보다 'x'가 값을 더 크게 만든다. 다만, 0과 1은 더하기가 더 크게 만든다.

 

#배열 입력받기 
data=input()

result=int(data[0])

#i 가 index의 역할로 배열 하나씩 확인
for i in range(1,len(data)):
	#배열 int로 바꾸기
	num=int(data[i])
    if num <=1 or result <=1:
    	result+=num
    else:
    	result*=num
print(result)

 

문제3) 모험가 길드

한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.

모험가 길드장인 A는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.
N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값 구하기.

 

n=int(input())
#배열 입력받기 (파이썬은 크기를 지정하지 않아도 됨.)
data=list(map(int,input().split()))
data.sort()

result=0
count=0

for i in data:
    count+=1
    if count>=i:
        result+=1
        count=0

print(result)

➡️ 정렬을 우선적으로 해야하는 케이스가 많으니 적극적으로 이용하자 ! 

 

출처) 이것이 취업을 위한 코딩테스트다. with 파이썬