탐욕알고리즘의 예시

탐욕 알고리즘으로 최적해가 보장되지 않는 예시

• 탐욕 알고리즘은 대부분의 경우에서 최적해를 보장하지 못한다.

탐욕 알고리즘으로 최적해가 보장되는 예시

• 분할 가능한 배낭 문제
• Prim 알고리즘
• Kruskal 알고리즘
• Dijkstra 알고리즘
• 회의실 배정 문제
• 허프만 암호화 알고리즘

 

동전 거스름돈 문제

문제 : 100원, 500원, 1000원이 있을 때, 1400원을 교환할 수 있는 최소 동전 개수를 구하라.

최적해인 경우

100원 : 100 x 14 = 14개

500원 : 500 x 2 + 100 x 4 = 6개

1000원 : 1000 x 1 + 100 x 4 = 5개

따라서 최소 동전 개수는 5개이다.

최적해가 아닌 경우

동전이 100원, 700원, 1000원일 경우

위와 같은 방법으로 실행 할 시

1000원: 1000 x1 + 100 x 4 = 5개가 된다.

하지만 실질적으로 700원 2개로 1400원을 만드는 게 전체의 최적해이다.

이 경우 DP(Dynamic Programming) 동적 프로그래밍 기법을 사용해야 한다.

 

동전 거스름돈 문제 pseudocode

 

입력 : 거스름돈 액수 W
출력 : 거스름돈 액수에 대한 최소 동전 수
change = W, n500 = n100 = n50 = n10 = n1 = 0
  // 각각의 동전 수를 위한 변수
while(change >= 500)
	change = change-500, n500++ // 500원짜리 동전 수 1 증가
while(change >= 100)
	change = change-100, n100++ // 100원짜리 동전 수 1 증가      
while(change >= 50)
	change = change-50, n50++   // 50원짜리 동전 수 1 증가
while(change >= 10)
	change = change-10, n10++   // 10원짜리 동전 수 1 증가
while(change >= 1)
	change = change-1, n1++    // 1원짜리 동전 수 1 증가
return (n500+n100+n50+n10+n1) // 총 동전 수 리턴

시간 복잡도

역 반복문(for 문)을 수행하므로 O(N)이 된다.

 

 

작업 스케줄링(Task Scheduling)

기계에서 수행되는 n개의 작업 t1, t2, … tn이 있고, 각 작업은 시작시간과 종료시간이 있다.

작업 스케줄링 문제는 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제이다

최적해일 경우

빠른 시작 시간 작업 우선일 경우만 최적해가 보장된다.

최적해가 아닐 경우

빠른 종료 시간 작업 우선일 경우 기계가 4개가 필요하고 최소 길이로 할 경우에도 마찬가지로 기계가 4개 필요하므로 최적 해를 보장하지 못한다.

 

작업 스케줄링 pseudocode

입력: n개의 작업 t1, t2, ... , tn
출력: 각 기계에 배정된 작업 순서
시작시간의 오름차순으로 정렬한 작업 리스트를 L이라고 한다.
while (L ≠ ∅) {
  L에서 가장 이른 시작시간을 가진 작업 ti를 가져온다.
  if (ti를 수행할 기계가 있으면)
    ti를 수행할 수 있는 기계에 배정한다.
  else
    새로운 기계에 ti를 배정한다.
  ti를 L에서 제거한다.
}
return 각 기계에 배정된 작업 순서

 

시간 복잡도

Line 1에서 n개의 작업을 정렬하는 데 O(nlogn) 시간이 걸린다.

while-루프에서 작업을 L에서 가져다가 수행 가능한 기계를 찾아 배정하므로 O(m)이 걸린다.

(m은 사용된 기계의 수)

while-루프가 수행된 총 횟수는 n번이므로, line 5~12까지는 O(m)*n = O(mn) 시간이 걸린다.

따라서 시간 복잡도는 O(nlogn) + O(nm)이다.

 

 

회의실 배정 문제

회의실 배정 문제는 다음과 같이 나눌 수 있다.

1. 소요 시간이 가장 짧은 회의 순
2. 시작 시간이 가장 이른 회의 순
3. 종료 시간 기준(최적 해가 보장)

Ex.) 각 회의실 시간이 주어졌을 때

A = [1,4], B = [3,5], C = [3,4], D= [2,2] ,E = [1,2]

최적의 해를 구하시오.

• 회의는 한번 시작하면 종료 x
• 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다
• 회의의 시작 시간과 끝나는 시간이 같을 수도 있다.

 

• 시작 시간이 가장 이른 회의 순

$[(1,4), (1,2), (2,2), (3,5), (3,4)]$ 가 된다.

 

• 소요 시간이 가장 짧은 회의 순

$[(2,2), (1,2), (3,4), (3,5), (1,4)]$가 된다.

이 경우에는 여러 회의 시간 중 중간에 짧은 회의가 있을 경우, 이 회의가 가장 먼저 배정되면 이 회의로 인해 앞뒤의 다른 회의가 배정될 수 없게 된다.

 

 

• 종료 시간 기준

회의를 시작하기 위해서는 회의실에서 회의가 진행 중이지 않아야 하고, 회의가 진행 중이지 않기 위해서는 있어야하기 때문이다.

즉, 회의실이 비어있는 시간을 순서대로 찾아내는 것이 핵심이다.

[(1,2), (2,2), (1,4), (3,4), (3,5)]가 된다.

 

회의실 배정 문제 pseudocode

import sys

def greedy(meeting)
	meeting_count = 0 # 소요 시간 
  start_time = 0    # 시작 시간
 
	for time in meeting
		if time[0] >= start_time:
			start_time = time[1]
			meegint_count += 1
	return meeting_count

if __name__ = "__main__":
mCount = int(sys.stdin.readline())
meeting = []
for i in range(mCount):
	start,end = map(int, sys.stdin.readline().split())
	meeting.append((start, end))
# 시작 시간 기준으로 정렬
meeting = sorted(meeting, key = lambda time: time[0])
# 종료 시간 기준으로 정렬
meeting = sorted(meeting, key = lambda time: time[1])
print(greedy(meeting))

 

시간 복잡도

정렬하는데 걸리는 시간 O(nlogn), 회의를 고르는데 걸리는 시간 O(n)으로

O(nlogn)의 시간이 걸린다.