4. 그리디 알고리즘

• 부분 배낭 문제
• 0-1 배낭 문제
• 집합 커버 문제 (7장) np문제
  전체 집합 U
  부분집합 F1, F2, ... Fn
  어떤 부분집합을 합쳐야 최소한의 집합을 사용해 전체집합을 표현할 수 있을까?...

  ex) 신도시 계획 학교배치
  어떤 위치에 학교를 지어야 모든 마을의 사람들이 10분안에 마을 사람들이 등하교가능할까? 학교의 갯수를 최소화

np문제 -> np문제 (O)
np문제 -> p문제 (?) 현대 난제 (불가능할것으로 보고 있지만 증명되지 않음)

• 작업 스케줄링

4.1. 집합커버문제

조건
학교는 마을에 위치해야함
등교거리는 15분 이내여야함(하나의 간선만으로 접근가능해야함)

해설

각각의 점에서 한번에 간선만으로 연결되어있는 점의 집합 부분집합 Sn를 만든다

U = {1,2,3,4,5,6,7,8,9,10}
S1 = {1,2,3,8}
S2 = {1,2,3,4,8}
S3 = {1,2,3,4}
S4 = {2,3,4,5,7,8}
S5 = {4,5,6,7}
S6 = {5,6,7,9,10}
S7 = {4,5,6,7}
S8 = {1,2,4,8}
S9 = {6,9}
S10 = {6,10}

최소 부분집합을 합쳐 U를 만든다.
정답 S2 + S6

최적화를 찾는 방법은 모든 점을 검사(2^n-1)은 집합의 크기가 커지면 불가능에 가깝다. 따라서 근사해를 찾는 알고리즘을 공부할 예정

알고리즘
현재 전체집합을 만들기 위해 필요한 점을 가장 많은 점을 포함하고 있는 부분집합을 먼저 선택함
선택된 집합이 가지고 있는 점을 지움

시간복잡도: O(n^3)
근사비율: K*logn

4.2 작업 스케줄링

기계에서 수행되는 n개의 작업을 작업이 겹치지 않도록 최소한의 기계에 배정

조건
작업의 수
작업의 시작시간과 종료시간

1. 현 시점에서 가장 빨리 시작하는 작업부터 배정(최적해 가능)
2. 현 시점에서 가장 빨리 종료하는 작업부터 배정
3. 짧은 작업 우선 배정
4. 긴 작업 우선 배정

알고리즘
작업 시작시간 순으로 오름차순으로 정렬
해당 작업을 수행할 수 있는 기계가 있으면 배정
없다면 새로운 기계에 작업을 배정

시간복잡도: O(nlogn) + O(mn) //작업수 n ,기계의 수 m

4.3 허프만 압축

파일의 각 문자가 8bit 아스키코드로 파일에 저장될 경우
이를 압축하기 위해서 자주사용하는 문자는 짧은 코드로 표현해 파일의 크기를 줄임

알고리즘
자주 나타는 문자는 짧은 2진코드를 할당
드물기 나타나는 문자는 긴 2진코드에 할당

허프만 압축으로 변환시킨 문자코드는 접두부 특성이 존재한다.

가변코드의 경우 코드의 길이를 알 수 없어 코드와 코드 사이를 나누어 주는 특수한 코드 없이는 오해의 소지가 있음
허프만 압축의 경우는 접두부특성을 나타내 오해의 소지가 없도록함

ex)
접두부 특성이 없음
101 = a
1011 = b
01 = c
101101 = aa?, bc?

입력) n개의 문자에 대한 빈도수
ex) a 100, b 200, c 192, d 123...
출력) 허프만 트리

시간복잡도: O(nlogn) //n개의 문자종류