탐욕법개념 1 2

(1)

알고리즘과 문제해결

6강 탐욕법

- 01 -

(2)

1차시

탐욕법 개념

학습목표

탐욕법 개념 을 이해 할 수 있다.

1

(3)

1

^{탐욕법 사례}

휴가전까지 모든 일을 끝내기

1

^• 한가지 일을 잠시 하다가 다른 일을 한다.

• 그 일을 잠시 하다가 또 다른 일을 한다.

1

^{탐욕법 사례}

• 일들을 쉬운 것에서부터 어려운 것 순서로 정렬한다.

• 가장 쉬운 일부터 시작한다.

• 순서대로 일을 한다.

2

휴가전까지 모든 일을 끝내기

- 03 -

(4)

1

^{탐욕법 사례}

• 일들을 우선순위에 따라 정렬한다.

• 가장 우선 순위가 높은 일부터 시작한다.

• 순서대로 일을 한다.

3

휴가전까지 모든 일을 끝내기

1

^{탐욕법 개요}

가장 직관적인 알고리즘 설계 패러다임C

각 단계마다 지금 당장 가장 좋은 방법만을 선택 많은 경우 최적해를 찾지 못함

탐욕법 Greedy algorithm

(5)

1

^{탐욕법 개요}

탐욕법 활용

탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제에 적용

1

₁

수행 시간이 다른 알고리즘에 비해 훨씬 빠름

시간이나 공간적 제약으로 인해 다른 방법으로 최적해를

1

₂

찾기 너무 어려운 경우

‘최적해’ 대신 ‘근사해’로 대체

1

^{탐욕법 개요}

한 문제를 탐욕적으로 해결하는 방법이 한가지만 있는 것이 아님

1

₁

어느 방법을 선택해야 최적해를 구할 수 있을지 검토 필요

1

₂

탐욕법 특성

- 05 -

(6)

1

^{탐욕법 개요}

가장 큰 동전으로 거스르면 최적해임

3620 =16 20

1610 = 6 20

6 - 5 = 1 1 - 1 = 0

10 20 10 5

20 10 5 1

1

^{탐욕법 개요}

int coin[4] = {20, 10, 5, 1};

int count[4];

int main() {

int m, i = 0, f = 0;

scanf("%d", &m);

while (i < 4) {

if (coin[i] > m) i++;

else if (coin[i] < m) { m -= coin[i];

count[i]++;

동전 거스르기 소스코드

(7)

1

^{탐욕법 개요}

else {

f = 1;

count[i]++;

break; } }

if (f) printf("%d coin %d, %d coin %d, %d coin %d,

%d coin %d.\n", coin[0], count[0], coin[1], count[1], coin[2], count[2], coin[3], count[3]);

else printf("No answer.\n");

return 0;

}

동전 거스르기 소스코드

1

^{탐욕법 개요}

컴파일 하기 (윈도우용 gcc or Linux 활용) gcc coin.c -o coin.exe

실행결과

- 07 -

(8)

핵심 키워드 이 시간을 통해 꼭 기억해야하는 ‘핵심 키워드’입니다.

탐욕법

1

(9)

2차시

최단경로찾기

학습목표

탐욕법 ^{을 활용한}

최단경로찾기 를 이해 할 수 있다.

1

- 09 -

(10)

1

^{다익스트라 알고리즘}

다익스트라 ^Dijkstra

탐욕법 활용

음수 값을 가지지 않는 그래프에서 최단경로탐색 구글 웹사이트 지도서비스, 자동차 네비게이션, 네트워크 등

1 다익스트라 알고리즘 동작

아직 방문하지 않은 정점들 중 가장 거리가 짧은 정점을 방문 정점에서 인접하고 아직 방문하지 않은 정점들의 거리 갱신

(11)

1

알고리즘 동작

5

4

3

1 2 0

14 9

7 10 15

2 11

6 9

5

4

3

1 2 0

14 9

7

10 15

2 11

6 9

1

알고리즘 동작

5

4

3

1 2 0

14 9

7 10 15

2 11 6

9

5

4

3

1 2 0

14 9

7

10 15

2 11 6

9

- 11 -

(12)

1

알고리즘 동작

5

4

3

1 2 0

14 9

7 10 15

2 11

6 9

5

4

3

1 2 0

14 9

7

10 15

2 11

6 9

1

입력 문자열

1

int graph[V][V] = { {0, 4, 0, 0, 0, 0, 0, 8, 0}, {4, 0, 8, 0, 0, 0, 0, 11, 0}, {0, 8, 0, 7, 0, 4, 0, 0, 2}, {0, 0, 7, 0, 9, 14, 0, 0, 0}, {0, 0, 0, 9, 0, 10, 0, 0, 0}, {0, 0, 4, 14, 10, 0, 2, 0, 0}, {0, 0, 0, 0, 0, 2, 0, 1, 6}, {8, 11, 0, 0, 0, 0, 1, 0, 7},

4

8 7

9

10 4 14

2

6 2 1

7 11 8

1 2 3

4

7 6 5

0 8

최단경로찾기 소스코드슼

(13)

1

아직 방문하지 않은 최단거리 지점 확인

2

int minDistance(int dist[], bool sptSet[]){

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v;

return min_index;

}

1

최단거리 계산

3

void dijkstra(int graph[V][V], int src){

for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false;

dist[src] = 0

for (int count = 0; count < V-1; count++) { int u = minDistance(dist, sptSet);

sptSet[u] = true;

for (int v = 0; v < V; v++)

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX

&& dist[u]+graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v];

}

- 13 -

(14)

1

실행결과

컴파일 하기 (윈도우용 gcc or Linux 활용) g++ dijkstras.cpp -o dijkstras.exe

1

최악의 경우 가정 (정점의 수가 N개)

N개의 정점에 대해서 인접된 N개 중에서 최단거리를 계산

O(N

²

)

시간복잡도 분석

(15)

최단경로찾기

1

다익스트라 알고리즘

2

참고문헌

http://cowking.tistory.com/entry/%EB%A7%A8%EB%82%A0-%EC%86%8C-

%EA%B1%B1%EC%A0%95%EB%A7%8C-

%ED%95%98%EC%A7%80%EB%A7%90%EA%B3%A0

- 15 -

(16)

3차시

작업스케줄링

학습목표

탐욕법 ^{을 활용하여}

작업스케줄링 문제 를 해결 할 수 있다.

1

(17)

1

^{회의실 예약}

회의실 하나, n(≤100)개 팀이 사용 회의는 서로 겹치지 않아야 함

최대로 선택할 수 있는 회의 수는?

활동 선택 문제

(Activity selection problem)

문제설명

1

^{회의실 예약}

출처 : https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188

문제설명

- 17 -

(18)

1

^{회의실 예약}

완전탐색 풀이

2^N탐색필요 è n 커질 수록 소요시간 매우 커짐 회의들이 겹치지 않는 모든 부분 집합을 만듦

가장 큰 부분 집합을 찾기

해결방법

1

^{회의실 예약}

탐욕법 적용

① 목록에 남은 회의 중 가장 일찍 끝나는 회의 선택

② 선택된 회의와 겹치는 것은 목록에서 삭제

③ 목록이 빌 때까지 반복 회의를 최대한 많이 개최

사용시간이 긴 것은 중요하지 않음

해결방법

(19)

1

^{회의실 예약}

nlog₂n (정렬 수행) + n (겹치지 않는 것 선택) 시간복잡도: O(nlog₂n)

모은 회의를 종료 시간의 오름차순으로 정렬 첫번째 것을 선택, 겹치지 않는 회의 바로 선택

해결방법

1

^{회의실 예약}

회의실 예약 소스코드 int schedule(void) {

for (int i = 0; i < N; i++)

order.push_back(make_pair(cEnd[i], cBegin[i]));

sort(order.begin(), order.end());

int earliest = 0, selected = 0; // 가장빠른회의,선택한 회의 for (int i = 0; i < order.size(); i++) {

int meetingBegin = order[i].second, meetingEnd

= order[i].first;

if (earliest <= meetingBegin) {

earliest = meetingEnd; selected++; } } return selected; }

- 19 -

(20)

1

^{회의실 예약}

회의실 예약 소스코드 int main(void) {

cin >> N;

for (int i = 0; i < N; i++)

cin >> cBegin[i] >> cEnd[i];

cout << schedule() << endl;

return 0;

}

1

^{회의실 예약}

실행결과

컴파일하기(윈도우용gccor Linux 활용)

g++ roomschedule.cpp -o roomschedule.exe

(21)

2

^{작업스케줄링}

스케줄링 문제

임의의 작업이 서비스를 받기 위해 대기하는 시간을 최소화 작업 마다 가중치가 다르고 가중치를 최대로 하는 문제 작업 수가 많은 경우 완전 탐색에 많은 시간 소요

2 마감시간이 있는 스케줄링 문제

작업 초기시작 시간 시점 1, 작업 1 단위시간 소요 마감시간 è 작업이 반드시 시작되어야 하는 마지 노선

총 이익이 최대가 되도록 작업 스케줄 작성

작업 T1 마감시간 2 è 작업 T1은 시점1 혹은 시점2 시작 가능 작업 T2 마감시간 1è 작업 T2은 시점1에서만 시작 가능 문제설명

- 21 -

(22)

2

문제설명

가능한 스케줄

• [1,3] 30+25=55, [3,1] 25+30=55

• [2,1] 35+30=65, [4,1] 40+30=70

• [1,3] 35+25=60, [4,3] 40+25=65

이익이 가장 큰 작업4는 최적 스케줄에 포함 작업2는 작업4와 마감시간이 같아 포함 안됨

2

문제설명

• 작업을 이윤이 큰 순서로 정렬

• 작업1을 선택 {1}

• 작업2를 추가 {2,1}

• 작업3을 추가 불가

• 작업4를 추가 {2,1,4}

•

탐욕법 적용

(23)

2

해결방법

모든 작업을 이윤 크기로 정렬한 후에

하나의 작업에 데드라인을 맞출 수 있는 작업 탐색

nlog

₂

n

^{(정렬수행)}⁺

n

²(데드라인맞는작업탐색)

시간복잡도: O(n²)

2

작업스케줄링 소스코드

void printJobScheduling(Job arr[], int n){

sort(arr, arr+n, comparison);

int result[n];

// 결과 저장

bool slot[n];

// 슬롯이 비었는지 여부

for (int i=0; i<n; i++) slot[i] = false;

for (int i=0; i<n; i++) {

for (int j=min(n, arr[i].dead)-1; j>=0; j--) { if (slot[j]==false) {

result[j] = i; // Add this job to result slot[j] = true; // Make this slot occupied break; } } }

- 23 -

(24)

2 for (int i=0; i<n; i++) if (slot[i])

cout << arr[result[i]].id << " ";

}

2 int main() {

Job arr[] = { {'1', 3, 40}, {'2', 1, 35}, {'3', 1, 30},

{'4', 3, 25}, {'5', 1, 20}, {'6', 3, 15}, {'7', 2, 10}};

int n = sizeof(arr)/sizeof(arr[0]);

cout << "Following is maximum profit sequence of jobs: ";

printJobScheduling(arr, n);

return 0;

}

(25)

2

실행결과

컴파일 하기 (윈도우용 gcc or Linux 활용) g++ jobschedule.cpp -o jobschedule.exe

작업스케줄링

1

- 25 -

(26)

확장하기 1

탐욕 알고리즘

http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC

%EC%A6%98-Greedy-Algorithm-%ED%83%90%EC%9A%95-

%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

확장하기 2

최단경로문제

https://ko.wikipedia.org/wiki/%EC%B5%9C%EB%8B%A8_%EA%B2%BD%

EB%A1%9C_%EB%AC%B8%EC%A0%9C

확장하기 3

생산 스케줄링에 의한 기계의 효율적인 배치

http://www.lean-manufacturing-japan.co.krimprove/post_2.html

참고문헌

• http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6

%98-Greedy-Algorithm-%ED%83%90%EC%9A%95-

%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

• https://ko.wikipedia.org/wiki/%EC%B5%9C%EB%8B%A8_%EA%B2%BD%EB%A1%

9C_%EB%AC%B8%EC%A0%9C

• http://www.lean-manufacturing-japan.co.kr/improve/post_2.html

탐욕법개념 1 2

알고리즘과 문제해결

6강 탐욕법

1차시

탐욕법 개념

탐욕법 개념 을 이해 할 수 있다.

1

휴가전까지 모든 일을 끝내기

1

1

2

휴가전까지 모든 일을 끝내기

1

3

휴가전까지 모든 일을 끝내기

1

탐욕법 Greedy algorithm

1

탐욕법 활용

1

1

1

1

1

탐욕법 특성

1

가장 큰 동전으로 거스르면 최적해임

36­20 =16 20

16­10 = 6 20

6 - 5 = 1 1 - 1 = 0

10

20 10 5

20 10 5 1

1

1

else {

f = 1;

count[i]++;

break; } }

if (f) printf("%d coin %d, %d coin %d, %d coin %d,

%d coin %d.\n", coin[0], count[0], coin[1], count[1], coin[2], count[2], coin[3], count[3]);

else printf("No answer.\n");

return 0;

}

1

탐욕법

2차시

최단경로찾기

탐욕법 을 활용한

최단경로찾기 를 이해 할 수 있다.

1

다익스트라 Dijkstra

1

다익스트라 알고리즘 동작

1

1

1

1

1

int minDistance(int dist[], bool sptSet[]){

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v;

return min_index;

}

1

1

1

O(N

)

최단경로찾기

다익스트라 알고리즘

3차시

작업스케줄링

탐욕법 을 활용하여

작업스케줄링 문제 를 해결 할 수 있다.

1

활동 선택 문제

1

1

3620 =16 20

1610 = 6 20

탐욕법 ^{을 활용한}

다익스트라 ^Dijkstra

탐욕법 ^{을 활용하여}