그리디 알고리즘 [개념]

[09강] 그리디 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 그리디 알고리즘에 대해 알아보겠습니다. 목차 그리디 알고리즘 실제 문제에서 그리디 알고리즘 접근 방식과 알고리즘 접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다. 접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고 알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다. 구체적인 예를 들어 설명해보겠습니다. 에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고 그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다. 에라토스테네스의 체 알고리즘은 언제 쓰면 될까요? → 소수(prime number)를 ..

https://gliver.tistory.com/18

1. 그리디 알고리즘

• 그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구하는 알고리즘이다.

• 그리디 알고리즘을 사용하려면 문제가 아래의 조건을 만족해야 한다.

매 순간에서의 최선의 선택 = 문제에서의 최적해

예시1) 그리디 알고리즘 사용 가능

[문제]

동전 1원, 2원, 4원을 가지고 N원을 만들어야 한다.

최소한의 동전의 개수로 N원을 만드는 경우를 출력하는 프로그램을 적성하시오. 답이 여러 가지인 경우 아무 경우나 출력하시오.

(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)

시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.

• 현재 상황에서 가능한 큰 수의 동전을 사용하는 그리디한 풀이로 해결할 수 있다.

• 시간 복잡도:

N = 11

current_num = N
use4 = current_num // 4
current_num %= 4
use2 = current_num // 2
current_num %= 2
use1 = current_num // 1
current_num %= 1

print(f"1을 사용한 횟수: {use1}")
print(f"2을 사용한 횟수: {use2}")
print(f"4을 사용한 횟수: {use4}")
print(f"사용한 동전의 총 개수: {use1 + use2 + use4}")

예시2) 그리디 알고리즘 사용 불가능

[문제]

동전 1원, 3원, 4원을 가지고 N원을 만들어야 한다.

최소한의 동전의 개수로 N원을 만드는 경우를 출력하는 프로그램을 적성하시오. 답이 여러 가지인 경우 아무 경우나 출력하시오.

(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)

시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.

• 이 경우는 매 순간에서의 최선의 선택이 문제의 최적해와 다르므로 그리디하게 풀 수 없다.

반례: N=6

• 그리디 접근: 4원 + 1원 + 1원 = 3개

• 최적의 해: 3원 + 3원 = 2개

• 아래와 같이 브루트 포스적인 풀이로 풀어도 시간 초과가 나게 된다.
• 1a + 3b + 4c = N 을 만족하는 모든 순서쌍에 대해 살펴보는 풀이
• 시간 복잡도:
python

INF = int(1e7)

N = 6

use1 = use3 = use4 = None
min_use = INF

for a in range(N//1 + 1):
	for b in range(N//3 + 1):
		for c in range(N//4 + 1):
			if 1*a + 3*b + 4*c == N:
				if a + b + c < min_use:
					min_use = a + b + c
					use1 = a
					use3 = b
					use4 = c

print(f"1을 사용한 횟수: {use1}")
print(f"3을 사용한 횟수: {use3}")
print(f"4을 사용한 횟수: {use4}")
print(f"사용한 동전의 총 개수: {use1 + use3 + use4}")

2. 실제 문제에서 그리디 알고리즘

• 문제를 보고 그리디한 풀이가 가능한지 확인
• 매 순간에서의 최선의 선택이 문제의 최적해와 일치하는지 확인

• 그리디한 풀이로 풀 수 없는 경우
• 매 순간에서의 최선의 선택이 문제의 최적해와 일치하지 않는 경우에 해당
• 브루트포스, DP, 수학과 같은 다른 방식의 접근이 필요함

심화 내용

MAX = int(1e7)
N = int(1e6)

min_use = MAX
use1 = use3 = use4 = None

for c in range(N // 4 + 1):
    b = (N - 4 * c) // 3
    a = (N - 4 * c) % 3
    if a + b + c < min_use:
        min_use = a + b + c
        use1 = a
        use3 = b
        use4 = c

print(f"1을 사용한 횟수: {use1}")
print(f"3을 사용한 횟수: {use3}")
print(f"4을 사용한 횟수: {use4}")
print(f"사용한 동전의 총 개수: {use1 + use3 + use4}")