스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제 임의의 작업(Task)이 서비스를 받기 위해 대기하는 시간 + 실제 서비스를 받는 시간 스케줄링 문제 모든 작업의 전체 시스템 내부시간이 최소화 되도록 일정을 구성하는 문제

스케줄링 (Scheduling) 스케줄링 문제 t1=5, t2=10, t3=4 Example: 3개의 작업이 있고, 각 작업에 소요되는 시간이 5, 10, 4이다. t1=5, t2=10, t3=4 [1, 2, 3]: 5+(5+10)+(5+10+4) = 39, [1, 3, 2]: 5+(5+4)+(5+4+10)=33, [2, 1, 3]: 10+(10+5)+(10+5+4) = 44, [2, 3, 1]: 10+(10+4)+(10+4+5)=43, [3, 1, 2]: 4+(4+5)+(4+5+10) = 32, [3, 2, 1]: 4+(4+10)+(4+10+5)=37.

스케줄링 (Scheduling) 스케줄링 문제를 위한 탐욕알고리즘 정리 4.3 작업시간별로 작업을 비내림차순으로 정렬한다. 시간복잡도: W(n)(nlgn)  why? 정리 4.3 시스템 내부의 총 시간이 최소가 되도록 하는 유일한 스케줄은 작업시간별로 작업을 비내림차순으로 짠 스케줄이다. 작업시간별로 작업을 비내림차순으로 정렬한다. while (답을 구하지 못했음) { 다음 작업을 스케줄에 넣는다; //선택절차&적정성 점검 if (작업이 더 이상 없다) // 해답 점검 답을 구했음; }

마감시간 있는 스케줄링 마감시간(deadline)이 있는 스케줄링 문제: 각 작업을 끝내는 데 1의 단위시간이 걸림 각 작업마다 마감시간과 작업 후 발생하는 이익이 할당되어 있음 전체 작업의 시작 시간: 1 마감시간(deadline): 작업이 반드시 시작되어야 하는 마지 노선 시간 “작업 T1의 마감시간이 2이다”의 의미  작업 T1은 시점 1 혹은 2에 시작 가능 “작업 T2의 마감시간이 1이다”의 의미  작업 T2는 시점 1에만 시작 가능 총 이익을 최대가 되게 작업의 스케줄을 짜는 문제

마감시간 있는 스케줄링 마감시간이 있는 스케줄링 문제: Example: 작업의 마감시간과 이익이 다음 표와 같다고 하자. 이 경우의 가능한 스케줄과 총 이익은 오른쪽과 같다. 최적 스케줄: [4, 1] 이익이 가장 큰 작업 4는 최적 스케줄에 포함되었지만 두 번째로 이익이 큰 작업 2는 포함되지 않았다. 그 이유는 작업 4와 작업 2의 마감시간이 같아 둘 중 하나만 포함할 수 있기 때문이다.

마감시간 있는 스케줄링 마감시간이 있는 스케줄링 문제를 위한 탐욕알고리즘 작업을 이익이 큰 것 부터 차례로 정렬 (비올림차순)한다. S = ; while (답을 구하지 못했음) { 다음 작업을 선택; //선택절차 if (이 작업을 추가하면 S가 적절하다.) //적정성 점검 이 작업을 S에 추가; if (작업이 더 이상 없다) // 해답 점검 답을 구했음; }

마감시간 있는 스케줄링 마감시간이 있는 스케줄링 문제를 위한 탐욕알고리즘 예제 4.4

허프만 코드 Representation of characters in computer 7 bits/char (ASCII) 2 bytes/char (KSC Hangul) 2 bytes/char (UNICODE) Isn’t there more efficient way to store text? Huffman Code: 문자들로 이루어진 데이터 파일을 코드화 하는 방법 중 하나 Data compression based on frequency  Huffman Code Binary coding (0과 1만 사용, 즉 이진 코딩) Variable length coding (가변 길이 이진 코딩) Assign short code for characters used frequently

허프만 코드 고정 길이 이진 코딩 vs. 가변 길이 이진 코딩 최적 이진 코딩 문제(Optimal Binary Code) 텍스트 파일의 문자 집합: {a, b, c} 고정길이 이진 코딩 a: 00, b: 01, c: 11 ababcbbbc  000100011101010111 (18 비트) 가변길이 이진 코딩 b가 가장 빈번하게 나온다는 것을 안다고 가정  b를 0으로 코딩 a: 10, b:0, c:11 (주의: a를 01로 코딩할 수 없음. Why?) ababcbbbc  1001001100011 (13 비트) 최적 이진 코딩 문제(Optimal Binary Code) 주어진 파일에 있는 문자들을 이진 코드로 표현하는 데 필요한 비트의 개수가 최소가 되는 이진 문자 코드를 찾는 문제

허프만 코드 Huffman code는 prefix code (전치 코드) 문자 코드가 서로 다른 길이를 가질 수 있다. 즉, 한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수 없다. {b, a, c}={0, 10, 11} : prefix code {a, b}={01, 011} : not prefix code 전치 코드의 장점 전치 코드는 Leaf가 코드 문자로 구성된 이진 트리 (Binary Tree)로 표현 가능 인코딩되어 있는 것을 디코딩할 때 (즉, 복원할 때) 트리의 뿌리에서 1-pass 만에 디코딩이 가능

허프만 코드 Huffman code의 예 문자 집합 {a, b, c, d, e, f}에 대한 3가지 코드법 각 코드법을 사용한 결과 인코딩 파일의 총 비트 수 C1: 16 * 3 + 5 * 3 + 12 * 3 + 17 * 3 + 10 * 3 + 25 * 3 = 255 C2: 16 * 2 + 5 * 5 + 12 * 4 + 17 * 3 + 10 * 5 + 25 * 1 = 231 C3: 16 * 2 + 5 * 4 + 12 * 3 + 17 * 2 + 10 * 4 + 25 * 2 = 212 C3 방법이 가장 효율이 좋다.

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) 최적 코드에 해당하는 이진 트리를 구축하여 최적이진문자 코드(Huffman code)를 만드는 문제

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) priority queue 이용 [알고리즘] Top Priority – 빈도수가 가장 작은 문자 내부적으로는 heap으로 구현하는 것이 가장 좋다. [알고리즘] priority_queue 에 낮은 빈도수부터 오름차순으로 저장 priority_queue 에서 차례로 두 개를 선택 left와 right child에 배치하고 두 빈도수를 가진 새로운 root 노드를 만들어 binary subtree 를 생성 두 빈도수의 합을 priority_queue 에 삽입 더 이상 진행할 수 없을 때까지 반복 시간 복잡도: Θ(n lgn)

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) [의사코드] 노드 타입 선언 우선순위 큐 PQ에 있는 nodetype 객체들을 가리키는 n개의 포인터를 다음과 같이 배열한다. PQ의 각 포인터 p에 대해

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) [의사코드] 복잡도 분석: insert(PQ, r)에서 (lgn)시간 필요. 그러므로 전체적으로 (n lgn) 의 효율을 지님

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) I:1 S:1 Y:1 A:2 b:2 M:3 Y:1 1 A:2 b:2 M:3 A:2 b:2 Y:1 S:1 I:1 2 3 1 M:3

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) M:3 3 A:2 b:2 4 Y:1 2 I:1 S:1 1 1 Y:1 2 1 I:1 S:1 A:2 b:2 4 1 M:3 6 Y:1 S:1 I:1 2 3 1

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) 10 4 6 M:3 A:2 b:2 3 Y:1 2 I:1 1 4 6 1 1 M:3 A:2 b:2 3 1 Y:1 2 1 I:1 S:1

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code)

허프만 코드 최적 이진 코딩 문제(Optimal Binary Code) Another Example 1 1 1 1 1 문 자 1 문 자 빈 도 A 2 B 18 C 9 D 30 E F 36 1 1 1 1 문 자 빈 도 원래(ASCII) 크기 압축된 크기 차이 A 2 7*2=14 4*2=8 6 B 18 7*18=126 2*18=36 90 C 9 7*9=63 4*9=36 27 D 30 7*30=210 2*30=60 150 E 3*9=27 36 F 7*36=252 2*36=72 180 계 104 728 240 488 Data Structure

Dynamic Programming vs. Greedy Method

0-1배낭 채우기 문제 (0-1 Knapsack Problem)(1/2) 문제의 개념적 정의 어떤 도둑이 보석상에서 배낭을 매고 침입했다. 도둑이 똑똑하여 각 보석의 “무게”와 “값어치”를 알고 있다. 훔칠 보석의 총 무게가 용량 W를 초과하면 배낭이 망가진다. 도둑은 총 무게가 W를 초과하지 않으면서 보석들의 총 값어치가 최대가 되도록 보석을 배낭에 담고자 한다.

0-1배낭 채우기 문제 (0-1 Knapsack Problem)(2/2) 문제의 정형적 정의 입력: 보석 (item)의 개수: n 보석 집합 S = {item1, item2,…, itemn} wi = itemi의 무게, pi = itemi의 가치 W = 배낭에 넣을 수 있는 총 무게 문제 정의 를 만족하면서 가 최대가 되도록 A  S가 되는 A를 결정하는 문제이다.

0-1배낭 채우기 – 무작정 알고리즘 n개의 아이템에 대해서 모든 부분집합을 다 고려한다. 모든 부분집합들 중에서 총 무게가 W를 초과하는 것들을 버리고, 남은 것들 중에서 총 이익이 최대가 되는 것을 하나 선택한다. 그러나, 불행하게도 크기가 n인 집합의 부분집합의 수는 2n개이다.

0-1배낭 채우기 – 탐욕적 방법 1 [선택전략] 가장 비싼 물건부터 우선적으로 채운다. 애석하게도 이 알고리즘은 최적이 아니다! 왜 아닌가? 보기: W = 30kg  탐욕적인 방법: item1 25kg  10만원 최적인 해답: item2 + item3  20kg  18만원

0-1배낭 채우기 – 탐욕적 방법 2 [선택전략] 가장 가벼운 물건부터 우선적으로 채운다. 마찬가지로 이 알고리즘도 최적이 아니다! 왜 아닌가? 보기: W = 30kg  탐욕적인 방법: item2 + item3  20kg  14만원 최적인 해답: item1 25kg  20만원

0-1배낭 채우기 – 탐욕적 방법 3 [선택전략]무게 당 가치가 가장 높은 물건부터 우선적으로 채운다. 그래도 최적이 아니다! 왜 아닌가? 보기: W = 30kg  탐욕적인 방법: item1 + item3  25kg  190만원 최적인 해답: item2 + item3  30kg  200만원 더 복잡한 탐욕적 방법을 쓰더라도, 0-1 배낭 채우기 문제는 풀리지 않는다.

0-1배낭 채우기 – 동적 프로그래밍 (1/5) 동적 계획법 – 개략적인 전략 wi = itemi의 무게 pi = itemi의 가치 W = 배낭에 넣을 수 있는 총 무게 A를 최적을 이루는 부분집합이라고 가정 A에 item1, item2, item3, … 처럼 item1 부터 차례대로 보석을 (조건을 따져가며) 채운다고 가정

0-1배낭 채우기 – 동적 프로그래밍 (2/5) 동적 계획법 – 개략적인 전략 A가 itemn을 포함하지 않는 경우 A는 처음 n-1개 아이템들 중에서 최적을 이루는 부분집합과 동일 A가 itemn을 포함하는 경우 A는 총 무게가 W-wn 을 초과할 수 없다는 제약조건하에서 처음 n-1개 아이템들 중에서 최적을 이루는 부분집합에 itemn이 포함된 결과 최적의 이익 = 처음 n-1개 아이템들로 이루어진 이익 + pn

0-1배낭 채우기 – 동적 프로그래밍 (3/5) i > 0 이고 w > 0일 때, 전체 무게가 w가 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고의 이익(optimal profit)을 P[i][w]라고 하면, 다음의 재귀 관계식을 얻을 수 있다. P[i-1][w]는 i번째 항목을 포함시키지 않는 경우의 최고 이익이다. pi + P[i - 1][w - wi]는 i번째 항목을 포함시키는 경우의 최고 이익이다.

0-1배낭 채우기 – 동적 프로그래밍 (4/5) 그러면 어떻게 P[n][W]값을 구할 수 있을까? 다음과 같은 2차원 배열을 만든 후, 각 항을 계산하여 채워 넣으면 된다. int P[0..n][0..W] 여기서 P[0][w] = 0, P[i][0] = 0으로 놓는다. 계산해야 할 항목의 수는 nW 이다.  꽤 많은걸? 하지만… 뒷 장의 예제를 보자.

0-1배낭 채우기 – 동적 프로그래밍 (5/5) 앞선 예에서 P[3][30]을 계산해 보자. 다음과 같이 실제 계산해야 할 항의 수는 많지 않다. 3rd 1st

0-1배낭 채우기 – 동적 프로그래밍 (5/5) 개선된 알고리즘의 최악의 경우 수행시간을 계산해 보자. 앞의 예에서 보듯이 마지막 행에서 최대 2(n-1) 항을 계산한다. (n은 품목 개수) 따라서, 총 계산하는 항 수는 1 + 2 + 22 +…+ 2n-1 = 2n - 1이 된다. 결국, 계산하는 엔트리 수는 (2n)가 된다. 결국, 최악의 경우 Dynamic Programming 방법의 수행 시간은 (2n)이다. 분할정복 방법으로도 이 알고리즘을 설계할 수도 있고, 그 최악의 경우 수행시간은 (2n)이다. 아직 아무도 이 문제의 최악의 경우 수행시간이 지수(exponential)보다 나은 알고리즘을 발견하지 못했고, 아직 아무도 그러한 알고리즘은 없다라고 증명한 사람도 없다.

배낭 빈틈없이 채우기 문제 (The Fractional Knapsack Problem) 물건의 일부분을 잘라서 담을 수 있다. (보석이 금괴가 아니라 금가루라고 해석하면 된다.) 탐욕적인 접근방법으로 최적 해를 구하는 알고리즘을 만들 수 있다. [선택전략]무게 당 가치가 가장 높은 물건부터 우선적으로 채운다. item1 + item3 + item2 x 1/2 30kg  220만원 최적이다!  증명생략

Appendix

Priority Queue What is Priority Queue? 응급실에서 환자 치료의 예 Priority Queue 큐: 먼저 온 사람을 먼저 치료 스택: 나중에 온 사람을 먼저 치료 우선순위 큐 (Priority Queue) : 우선순위가 높은 사람 (예: 위급한 사람)을 먼저 치료 Priority Queue an abstract data type supporting the following three operations: - add an element to the queue with an associated priority - Remove and return the element from the queue that has the highest priority - (optionally) peek at the element with highest priority without removing it Data Structure

Priority Queue Priority Queue vs. Stack/Queue 스택과 큐 스택과 큐는 시간에 따라 자료구조를 조직화 시간을 포함한 여러 가지 가치를 우선순위로 가지는 자료구조  우선순위 큐 우선 순위 큐는 각 노드에 “우선순위 값” 필드가 필요. 우선순위 큐는 스택이나 큐 보다 일반적인 구조 큐나 스택은 우선순위 큐의 특수한 형태로서 시간에 그 우선순위를 부여한 것임 따라서 우선순위 필드가 불필요 Priority Queue Stack Queue Data Structure

Priority Queue Heap is an excellent structure to implement priority queue Data Structure

Heap Heap: a binary tree structure with the properties … 주의할 특징 Root의 키가 왼쪽자식과 오른쪽 자식의 키보다 크거나 같다. The subtrees are in turn heaps 지원되는 연산: Insertion, Deletion 주의할 특징 왼쪽 자식과 오른쪽 자식 사이에는 어느 쪽 키가 크던 상관이 없다.

Heap 정렬 관점에서… BST는 약한 의미로 정렬. Heap도 약한 의미로 정렬. 왼쪽 자식 키보다 오른쪽 자식 키가 크다. 부모의 키가 자식의 키보다 우선 순위가 높다 왼쪽 자식 키와 오른쪽 자식 키는 무관하다. Heap Binary search tree Data Structure