그리디 알고리즘

그리디 알고리즘이란?

그리디 알고리즘

• 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미

• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

• 그리디 해법은 그 정당성 분석이 중요

• 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

 

그리디 알고리즘 주의 사항 

• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.

• 그리디 알고리즘을 사용하기 전에, 그리디 알고리즘을 사용해도 되는지 반드시 확인 해야 합니다.

• 그리디 알고리즘을 쓸 수 없는 경우 예시

• 문제:루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들어야 한다.

대표적인 문제 - 거스름돈

- 최적의 해 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 됩니다.

 

가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 무엇일까요?

• 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다.

• 만약에 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면 어떻게 될까요?

• 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 합니다.

 

답안

n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]
for coin in array:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)

우리는 살면서 이런 알고리즘을 많이 사용하고있음

예를들어 작은개 여러개 = 큰거 하나 가 성립하는 상황

즉, 배수관계에 있는 상황

 

따라서

"동전을 잘살펴보아야함"

500원과 300원의 차이 

300원은 그리디를 사용할 수 업고 다이나믹 프로그래밍이라는 알고리즘을 사용해야함

 

문제: 1이 될 때까지

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

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

• N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있습니다.

• 다시 말해 K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있습니다.

• 또한 N은 항상 1에 도달하게 됩니다. (최적의 해 성립)

 

# N, K을 공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())
result = 0
while n>1:
	if n%k == 0:
		n = n//k
	else:
		n -= 1
	result += 1
print(result)

N이 K로 나누어 떨어진다면 n을 k로 나눈 몫을

그게 아니면 1을 빼서 n이 k로 나누어 떨어지도록

 

한마디로 최적의 해를 찾는 규칙을 찾아 최적의 해를 찾을 때까지 그 규칙을 반복하는 것이라고 나는 생각한다.

 

대표적인 문제2 - 곱하기 혹은 더하기

https://www.acmicpc.net/problem/21943

21943번: 연산 최대로

1과0은 더하기를 하는 것이 곱하기보다 낫고

그 나머지 경우는 무조건 곱하기를해야한다.

 

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
	# 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
	num = int(data[i])
	if num <= 1 or result <= 1:
		result += num
	else:
		result *= num

print(result)

 

대표적인 문제 3 모험가 길드

https://www.acmicpc.net/problem/25538

25538번: 모험가 길드

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) # 총 그룹의 수 출력

오름차순이기 때문에

조건만 만족시키면 바로 그룹을 결성시키고

다음 그룹을 만족시키기위한 절차로 도입한다.

 

이로써 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 됩니다.