[문제 해결 알고리즘] 그리디 알고리즘 2

1. 부분 배낭(Knapsack) 알고리즘

 (1) 배낭 문제 : n개의 물건이 있고, 각 물건의 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 때 최대의 가치를 갖도록 배낭에 넣을 문제들을 정하는 문제

 (2) 부분 배낭 문제 : 원래 배낭 문제는 물건을 통째로 배낭에 넣어야되지만, 부분 배낭 문제는 물건을 부분적으로 담는 것을 허용함

 > 단위 무게당 가장 값나가는 물건을 배낭에 넣고 계속해서 그 다음으로 값나가는 물건을 넣음

 > 만일 그 다음으로 값나가는 물건을 통째로 배낭에 넣을 수 없게 되면 부분적으로 배낭에 담음

 (3) 부분 배낭 문제 알고리즘 (Fractional napsack)

  - 입력 : n개의 물건, 각 물건의 무게(w)와 가치(v), 배낭의 용량 c

  - 출력 : 배낭에 담은 물건 리스트 L과 배낭에 담은 물건 가치 합

  ⓐ 각 물건의 대해 단위 무게당 가치 계산

  ⓑ 물건들을 단위 무게당 가치를 기준으로 내림차순으로 정렬, 정렬된 물건 리스트 = S

  ⓒ L = null, w = 0, v = 0

  ⓓ S에서 단위 무게단 가치가 가장 큰 물건 x를 가져옴

  ⓔ while((w+x의 무게) <= c) { 

  ⓕ x를 L에 추가

  ⓖ w = w + x무게

  ⓗ v = v + x가치

  ⓘ x를 S에서 제거

  ⓙ S에서 단위 무게당 가장 가치가 큰 물건 x를 가져옴 }

  ⓚ if (( c-w ) > 0) {

  ⓛ 물건 x를 c-w만큼 L에 추가

  ⓜ v = v + (c-w) }

  ⓝ return L, v

 (4) 시간 복잡도

  - n개의 물건 각각 단위 무게당 가치 계산 O(n)

  - 물건 단위 무게당 가치를 내림차순 정렬 O(nlogn)

  - while 루프의 수행은 n번을 넘지 않으며 루프 내의 수행은 O(1)이 걸림 == O(n)

  - if 내의 수행은 O(1)이 걸림

  - O(n) + O(nlogn) + O(n) + O(1) = O(nlogn)

2. 집합 커버(Cover) 알고리즘

 - n 개의 원소를 가진 집합인 U가 있고 U의 부분 집합들을 원소로 하는 집합 F가 주어질 때, F의 원소들인 집합들 중에서 어떤 집합들을 선택하여 합집합을 하면 U와 같게 되는가?

 - 집합 커버 문제 : F에서 선택하는 집합의 수를 최소화하는 문제

 (1) 예제 : 신도시 계획 학교 배치 

  - 10개의 마을이 신도시에 있다. 학교의 위치를 선정해야 한다. 

  - 학교는 마을에 위치해야하며, 등교거리는 15분 이내여야함

  - 어느마을에 신설하면 최소 개수의 학교를 신설할 수 있는가?

 (2) 가장 단순한 방법

  - F에 있는 집합들의 모든 조합을 1개씩 합집합하여 U가 되는지 확인하고, U가 되는 조합의 집합 수가 최소인 것을 찾음

  - F에 n개의 집합이 있다고 가정 시 2^n -1개 진행

 (3) 집합 커버 문제의 근사해

  - 최적해를 찾는 방법 : n이 커지면 최적해를 찾는 것은 실질적으로 불가능

  > 극복하기 위해 최적해를 찾는 대신에 최적해에 근접한 근사해를 찾음

  (4) 집합 커버 문제 알고리즘

  - 입력 : U, F = {Si}, i = 1,2,...,n

  - 출력 : 집합 커버 C

  ⓐ  C = null

  ⓑ while (U =null) {

  ⓒ U의 원소들을 가장 많이 포함하고 있는 Si를 F에서 선택

  ⓓ U = U- Si

  ⓔ Si를 F에서 제거하고 Si를 C에 추가 }

  ⓕ return C

 (5) 집합 커버 알고리즘의 시간복잡도

  - while 루프 조건 O(1)

  - U의 원소를 가장 많이 포함하고 있는 S를 찾으려면 현재 남아있는 Si를 U와 비교

  - Si의 수는 n이고, Si와 U의 비교는 O(n) 시간 걸리므로, O(n^2) 걸림

  - 집합 U에서 집합 Si의 원소 제거 O(n) 시간

 - Si를 C에 추가 O(1)

 - 루프 1번 실행 시 시간 복잡도 : O(1) + O(n^2) + O(n) + O(1) == O(n^2)

 - n번 실행 시 O(n^3)

(6) 근사 비율 

 - 근사해가 최적해에 얼마나 근사한지를 나타내는 근사 비율을 알고리즘과 함께 제시해야 함

 - setCover 알고리즘의 근사 비율 : Klog(2)n으로 최악의 경우의 해 일지라도 그 집합의 수가 Klog(2)n을 넘지 않는다는 뜻

 - K는 최적해의 집합의 개수

 - 신도시 계획 예제는 최적해가 2개로 Klog(2)n = 2log(2)10 < 2*4 = 8

 > SetCover 알고리즘이 찾는 근사해의 집합 수는 8개를 초과하지 않음 

 - 도시 계획, 경비 시스템, 기업의 경력 직원 공고 등에서 사용

3. 작업 스케줄링(Task Scheduling) 문제

(1) 문제 개요 : 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제

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

 - 학술대회에서 발표자들을 강의실에 배정하는 문제와 같음

 - 시작 시간, 종료 시간, 작업 길이에 대해 다음과 같은 그리디 알고리즘 생각 가능

 > 빠른 시작 시간 작업 우선 배정, 빠른 종료시간 작업 우선 배정, 짧은 작업 우선 배정, 긴 작업 우선 배정

(2) 시작 시간 기준으로 정렬 JobScheduling

 - 입력 : n개의 작업 t1, t2, ..., tn

 - 출력 : 각 기계에 배정된 작업 순서

 ⓐ 시작시간의 오름 차순으로 정렬한 작업 리스트 L (시작시간이 같은 경우, 종료 시간의 오름차순으로 정렬)

 ⓑ while (L != null) {

 ⓒ L에서 가장 이른 시작시간 작업 ti를 가져옴

 ⓓ if(ti를 수행할 기계가 있으면) 

 ⓔ {ti를 수행할 수 있는 기계에 배정함 }

 ⓕ else {새로운 기계에 ti를 배정함} 

 ⓖ ti를 L에서 제거 }

 ⓗ return 각 기계에 배정된 작업 순서

(3) 시간 복잡도

  - n개의 작업을 정렬하는데 O(nlogn)

  - while 루프에서 기계의 개수만큼 가능한 이력을 찾는 시간 O(m)

  - while 루프는 총 n번 걸림

  - O(nlogn) + O(mn) 

  - 기계의 개수에 따라 최종 결과가 다름 max O(n^2)