[알고리즘] 그리디 정리

그리디 ( 탐욕법 ) - 정당성 분석 (최적의 해 찾기)

그리디는 지금 현재 상황에서 고를 수 있는 최적의 해를 구하는 것이다.

그리디 특징

• 사전에 외우지 않고 풀수 있을 가능성이 있는 유형, 따라서 많은 유형을 접해보는것이 중요하다
• 문제를 풀기 위한 최소한의 아이디어를 요한다. ( 특정 문제에서 현재 상황에 가장 좋아 보이는 것만을 선택해 풀수있는지 파악할 수 있어야 한다.
• 일부는 다익스트라 알고리즘 처럼 암기가 필요한 부분이 있다
• 정렬 라이브러리의 사용 방법을 알아야한다 ( 순서에 대한 기준을 알아야 한다. )

 

문제 1 ) 거스름돈 문제

N은 항상 10의 배수

idea - 가장 큰 단위가 작은 단위의 배수이므로, 가장 큰 화폐 단위부터 거슬러야함

n = 1260 # 1260원을 내야함
count = 0

array = [500,100,50,10] # 큰화폐부터 차례로 확인

for coin in array:
	count += n // coin  # 거슬러 줄수있는 동전 개수세기 1260 // 500 == 2
	n %= coin # 260원이 남음

print(count) # 화폐종류가 K일때, 시간복잡도는 O(K)

→ O(K) : 화폐의 종류만큼 반복 수행, 시간 복잡도는 금액과는 무관, 화폐 종류에만 영향을 받음

 

 

문제 2) 1이 될때까지 : N을 1로 만들때까지 수행횟수의 최솟값 찾기

수행과정

• N에서 1을빼기 ( 1≤n≤100.000), ( 2≤k ≤100.000)
• N을 K로 나누기
  • 두가지의 수행을 통해 n→1로 하고 그 횟수를 최소한으로 하기

idea

• n을 최대한 많이 나누기
• 2이상 수로 나누는 작업이 1을 빼는것보다 좋다

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

while True:
	target = (n//k) * k  #n이 k로 나눠 떨어지지 않을때, 나눠떨어질수있는 가장 가까운값 찾기
	res += (n - target) #n이 k로 나눠 떨어지는 수가 될때까지 빼기
	n = target
	if n < k:
		break
	res += 1 # k로 나누기
	n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기 ㅠ
res += (n-1)
print(res)

 

 

문제 3) 곱하기 혹은 더하기

수행과정

• 각 문자열은 0 ~ 9 로 이뤄져있고, 각 숫자들을 ‘+’ 혹은 ‘*’을 연결해서 최댓값 구하기

idea

• 대부분 ‘+’보다는 ‘*’가 더 크게 만든다
• 다만 하나라도 0 혹은 1이 있다면, ‘+’을 수행

data = input() #문저열로 받아짐
res = int(data[0]) # 받은 데이터의 1번째 데이터를 int형으로 바꿈
for i in range(1, len(data)): # 1부터 data의 길이만큼 수행
	num = int(data[i])
	if num <= 1 or res <=1:
		res += num
	else:
		res *= num
print(res)

 

 

문제 4) 모험자 길드

수행과정

• 모험가 N명 (N명을 대상으로 공포도 측정, 공포도가 크면 상황 대처능력이 떨어짐)
• 공포도 x인 모험가는 x명이상으로 그룹참여 가능
• 여행을 떠날 수 있는 그룹의 최댓값
• ex) N = 5, 공포도가 각각 2,3,1,2,2 → 그룹은 1,2 즉, 2개 가능 & 남은 사람은 마을에 남아 있어도 된다.
• 여기서는 3이 해당됨

idea

• 오름 차순 정렬 → 공포도가 낮은 모험가부터 하나씩 확인

n = int(input())
data = list(map(int,input().split()))
data.sort()

res = 0 # 총 그룹수
count = 0 # 현재 그룹에 포함된 모험가 수
for i in data: # i는 공포도
	count += 1
	if count >= i:
		res += 1
		count = 0
print(res)