탐욕적인 방법(Greedy Approach)

Slides:



Advertisements
Similar presentations
1. 도형의 연결 상태 2. 꼭지점과 변으로 이루어진 도형 Ⅷ. 도형의 관찰 도형의 연결상태 연결상태가 같은 도형 단일폐곡선의 성질 연결상태가 같은 입체도형 뫼비우스의 띠.
Advertisements

이진 나무 구조 강윤섭 2008년 5월 23일.
제2장 주파수 영역에서의 모델링.
되추적(Backtracking).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
컴퓨터 프로그래밍 기초 [Final] 기말고사
Ch.04 Greedy Method (탐욕적 방법)
CHAP 10:그래프 (1) 순천향대학교 하상호.
되추적(Backtracking).
Chapter 02 순환 (Recursion).
07 그룹 함수 그룹 함수의 개념 그룹 함수의 종류 데이터 그룹 생성 HAVING 절.
CHAPTER 02 OpenCV 개요 PART 01 영상 처리 개요 및 OpenCV 소개.
알고리즘(Algorithm) – Greedy Method (탐욕적 방법)
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
강의 #9 그래프(Graph).
Error Detection and Correction
For/While Syntax & Practice!!
컴퓨터과학 전공탐색 배상원.
Ch.04 Greedy Method (탐욕적 방법)
그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문
CHAP 10: 그래프(part 2) 순천향대학교 하상호.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
탐욕적인 방법(Greedy Approach)
별의 밝기와 거리[2] 밝다고 가까운 별은 아니야! 빛의 밝기와 거리와의 관계 별의 밝기 결정.
Ⅲ. 이 차 방 정 식 1. 이차방정식과 그 풀이 2. 근 의 공 식.
CHAP 10:그래프 (2) 순천향대학교 하상호.
C 프로그래밍 C언어 (CSE2035) (Chap11. Derived types-enumerated, structure, and union) (1-1) Sungwook Kim Sogang University Seoul, Korea Tel:
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
27장. 모듈화 프로그래밍.
Ch.03 Dynamic Programming (동적 프로그래밍 or 동적 계획법)
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
제 1 장 알고리즘 : 효율, 분석, 그리고 차수.
쉽게 배우는 알고리즘 7장. 상호 배타적 집합의 처리.
8장. 상호 배타적 집합의 처리.
주요 내용 왜 그래프인가? 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
 Dynamic Programming (동적 프로그래밍)
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
보고서 (due 5/8) 다음과 같은 방식으로 문제를 해결하시오. 문제 분석 알고리즘 작성 프로그램 작성 테스트 및 검증
PADS Logic 회로도.
합집합과 교집합이란 무엇인가? 01 합집합 두 집합 A, B에 대하여 A에 속하거나 B에 속하는 모든 원소로 이루어진 집합을 A와 B의 합집합이라고 하며, 기호 A∪B로 나타낸다. A∪B ={x | x∈A 또는 x∈B}
P 등속 직선 운동 생각열기 – 자동차를 타고 고속도로를 달릴 때, 속력계 바늘이 일정한 눈금을 가리키며 움직이지 않을 때가 있다. 이 때 자동차의 속력은 어떠할까? ( 속력이 일정하다 .)
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
2nd day Indexing and Slicing
알고리즘 알고리즘이란 무엇인가?.
알고리즘 강의 슬라이드 6 분기한정법 Branch-and-Bound
약식 진리표를 이용한 타당성 증명 진리표 그리기 방법의 한계
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
5장. 선택 알고리즘.
05. General Linear List – Homework
빠른정렬(Quick Sort) – 개요 (1/2)
 Dynamic Programming (동적 프로그래밍)
 Branch-and-Bound (분기한정)
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
MST – Kruskal 알고리즘 (추상적)
부분집합의 합 구하기 문제 부분집합의 합 구하기(Sum-of-Subsets) 문제
상관계수.
컴퓨터공학과 손민정 Computer Graphics Lab 이승용 교수님
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
제 29 강 스트링(string) 다루기 s a i s . s T i h t g r i n.
29장. 템플릿과 STL 01_ 템플릿 02_ STL.
수학 2 학년 1 학기 문자와 식 > 미지수가 2개인 연립방정식 ( 1 / 1 ) 연립일차방정식의 해.
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
진리표를 이용한 타당성 증명 진리표(truth table) : 단순 문장들이 진리값을 상이하게 가질 수 있는 가능한 모든 경우를 남김없이 열거한 표 (ex) 오늘은 날씨가 맑거나 비가 올 것이다. 오늘은 날씨가 맑다 비가 온다 오늘은 날씨가 맑거나 비가 올 것이다. T.
C++ Espresso 제15장 STL 알고리즘.
Presentation transcript:

탐욕적인 방법(Greedy Approach)

탐욕적인 알고리즘? Greedy algorithm 결정을 해야 할 때마다 미래에 대한 생각 없이 그 순간에 가장 최선의 선택을 하는 알고리즘 순간 선택은 그 당시 최적(locally optimal)이다. 하지만, 최종적으로 최적(globally optimal)이라는 보장은 없다. 따라서, 탐욕적인 알고리즘은 항상 최적의 해를 주는지 검증해야 한다.

탐욕적인 알고리즘 설계 절차 선정과정(selection procedure) 적정성점검(feasibility check) 현재 상태에서 가장 좋으리라고 생각되는(greedy) 해답을 찾아서 해답모음(solution set)에 포함시킨다. 적정성점검(feasibility check) 새로 얻은 해답모음이 적절한지를 결정한다. 해답점검(solution check) 새로 얻은 해답모음이 최적의 해인지를 결정한다.

거스름돈 문제 문제: 동전의 개수가 최소가 되도록 거스름 돈을 주자. 탐욕적인 알고리즘 최적일까? 거스름돈을 x라 하자. 미국? 우리나라?

36 센트 거슬러 주기

16 센트 거슬러주기 (12센트 동전이 있을때)

우리나라의 경우 (210원에 대한 거스름) 현재의 동전체계 120원짜리 동전이 있다면? 100원, 100원, 10원 120원, 50원, 10원x4개

신장 트리(Spanning Tree)

그래프 용어 복습 비방향성 그래프(undirected graph) 경로(path) 연결된 그래프(connected graph) G = (V,E) V는 정점(vertex)의 집합 E는 이음선(edge)의 집합 경로(path) 연결된 그래프(connected graph) 어떠한 두 정점 사이에도 경로가 존재 부분그래프(subgraph) 가중치 포함 그래프(weighted graph) 순환경로(cycle) 순환적 그래프(cyclic graph), 비순환적 그래프(acyclic graph). 트리(tree) 비순환적이며, 비방향성 그래프 뿌리 있는 트리(rooted tree) 한 정점이 뿌리로 지정된 트리

연결된 가중치 비방향 그래프

신장트리 (Spanning Tree) 연결된, 비방향성 그래프 G에서 순환경로를 제거하면서 연결된 부분그래프가 되도록 이음선을 제거하면 신장 트리(spanning tree)가 된다. 따라서 신장 트리는 G안에 있는 모든 정점을 다 포함하면서 트리가 되는 연결된 부분그래프이다.

최소비용 신장 트리(Minimum Spanning Tree) 신장 트리가 되는 G의 부분그래프 중에서 가중치가 최소가 되는 부분그래프를 최소비용 신장 트리(minimum spanning tree)라고 한다. 최소의 가중치를 가진 부분그래프는 반드시 트리가 되어야 한다. 왜냐하면, 만약 트리가 아니라면, 분명히 순환경로(cycle)가 있을 것이고, 그렇게 되면 순환경로 상의 한 이음선을 제거하면 더 작은 비용의 신장 트리가 되기 때문이다. 최소비용 신장 트리를 구하는 무작정 알고리즘의 시간복잡도는 지수시간 이상이다.

최소비용 신장 트리(MST)의 예 도로 건설 통신(telecommunications) 배관(plumbing) 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제 통신(telecommunications) 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제 배관(plumbing) 파이프의 총 길이가 최소가 되도록 연결하는 문제

탐욕적 알고리즘: 최소비용 신장 트리 추상적 기술 F = ∅ 사례가 해결될 때까지 다음을 반복 지역적으로 최적인 간선을 선택한다. (선정절차) 선택한 간선이 순환경로를 만드는지 검사한다. (적정성 검사) 만들지 않으면 F에 추가한다. T = (V, F)가 신장 트리 인지 검사한다. (해답 검사)

Prim의 알고리즘(추상적 기술) F = ∅ Y = {v1} 사례가 해결될 때까지 다음을 반복 V-Y에서 가장 Y와 가까운 정점을 선택한다. (선정절차+ 적정성 검사) 선택한 정점을 Y에 추가하고, 해당 간선을 F에 추가한다. Y = V이면 종료한다. (해답 검사)

Prim의 알고리즘(세부적 기술) Prim 알고리즘의 자료구조 인접행렬W[i][j]: Floyd의 최단경로 알고리즘에서 사용한 행렬과 같은 행렬 (n × n 행렬) nearest[i]: Y에 속한 정점 중 vi와 가장 가까운 정점의 색인 distance[i]: vi와 nearest[i]를 잇는 간선의 가중치

Prim의 알고리즘

Prim의 알고리즘

Prim의 알고리즘

Prim의 알고리즘 분석 모든 경우 시간 복잡도 분석 단위 연산: 비교 연산 입력크기: n 분석 for(j=1; j<=n-1; j++)문: (n-1)번 반복 2개의 for(i=2; i<=n; i++)문: 각 (n-1)번 반복

최적 여부의 검증(Optimality Proof) 정의: 비방향 그래프 G = (V, E)가 주어졌을 때, E의 부분집합 F에 MST가 되도록 간선을 추가할 수 있으면 F는 유망하다(promising)고 한다. 보조정리: G = (V, E)가 연결된 가중치 비방향 그래프이고, F가 E의 유망한 부분집합이며, Y는 F에 의해 연결되는 정점들의 집합이라 하자. Y와 V-Y를 연결하는 간선 중 가중치가 최소인 간선이 e라고 하면, F∪{e}는 유망한 부분집합이다. 증명: F가 유망한 집합이므로 F ⊆ F'이고 (V, F')이 G의 MST인 F'이 존재한다. 이 때 e ∈ F이면 F∪{e} ⊆ F'이다. 이것이 성립하지 않는다고 하자. (V, F')은 MST이므로 e가 F'에 포함되지 않으면 F'∪{e}는 순환 경로를 가지게 된다. 따라서 Y와 V-Y를 연결하는 또 다른 정점 e'이 F'에 있어야 한다. 그러므로 F'∪{e}에서 e'을 제거하면 ST가 된다. e의 가중치는 e'보다는 같거나 작기 때문에 F'∪{e}-e'은 MST이다. 그런데 F∪{e} ⊆ F'∪{e}-e'이므로 e' ∉ F이다. 즉, F∪{e}는 유망하다.

최적 여부의 검증(Optimality Proof) 정리: Prim의 알고리즘은 항상 최소비용 신장 트리를 만들어 낸다. 증명: (수학적귀납법) 매번 반복이 수행된 후에 집합 F가 유망하다는 것을 보이면 된다. 출발점: 공집합은 당연히 유망하다. 귀납가정: 어떤 주어진 반복이 이루어진 후, 그때까지 선정하였던 이음선의 집합인 F가 유망하다고 가정한다 귀납절차: 집합 F ∪ {e}가 유망하다는 것을 보이면 된다. 여기서 e는 다음 단계의 반복 수행 시 선정된 이음선 이다. 그런데, 위의 보조정리에 의하여 F ∪ {e}은 유망하다고 할 수 있다. 왜냐하면 이음선 e는 Y에 있는 어떤 정점을 V - Y에 있는 어떤 정점으로 잇는 이음선 중에서 최소의 가중치를 가지고 있기 때문이다. Q.E.D.

Kruskal의 알고리즘 아이디어 단계 1. 각 정점 하나만을 포함하는 n개의 집합을 만든다. 단계 2. 모든 간선을 가중치 값을 기준으로 오름차순으로 정렬한다. 단계 3. 가중치가 가장 작은 것부터 검사하여 간선이 서로소(disjoint)인 두 집합을 연결하면 그 간선을 F에 추가하고, 연결된 두 집합을 하나의 집합으로 결합한다. 단계 4. F가 MST가 될 때까지 단계 3을 반복한다.

Kruskal의 알고리즘

Kruskal의 알고리즘

Kruskal의 알고리즘 분석 단위연산: 비교 입력크기: 정점의 수 n, 간선의 수 m 간선 정렬 시간: Θ(mlgm) while 루프: Θ(mlgm) V[i]집합 초기화 시간: Θ(n) n < m, W(m,n) = Θ(mlgm) m이 최악의 경우일 때, 최적 여부의 검증(Optimality Proof) 과제

Prim vs. Kruskal

단일 출발점 최단경로 문제 Floyd의 최단경로 알고리즘 Dijkstra 알고리즘 모든 정점간의 최단 경로 시간복잡도? 단일 출발점 최단 경로(Single-source shortest path) Prim의 MST 알고리즘과 유사 자료구조 W[i][j] touch[i]: Y에 있는 정점들만을 이용하여 v1에서 vi로 가는 현재 최단경로 상의 마지막 간선 (v, vi)라고 할 때, Y에 있는 정점 v의 색인 length[i]: Y에 있는 정점들만을 이용하여 v1에서 vi로 가는 현재 최단경로의 길이

Dijkstra 알고리즘

Dijkstra 알고리즘

Dijkstra 알고리즘

기말 프로젝트 12/8 까지 그래프 알고리즘 구현 발표 (5분) Floyd, Prim, Kruskal, Dijkstra, TSP 중 택 1 이 외의 주제를 하고자 할 경우, 미리 상담 언어 사용 자유 발표 (5분) 발표 슬라이드 + 프로그램 데모 적절한 사례를 선택

스케줄링 시스템 내부 시간(time in the system) 서비스를 받기 위해 대기하는 시간 + 서비스를 받는 시간 스케줄링 문제: 모든 사용자의 전체 시스템 내부 시간이 최소화되도록 일정을 구성하는 문제 마감시간이 있는 스케줄링 문제 서비스를 받는 시간은 작업마다 항상 같지만 각 작업마다 마감시간(서비스가 반드시 시작되어야 하는 시간)이 다르며, 발생되는 이윤이 다른 경우 3개의 작업에 소요되는 시간 5, 10, 4 [1, 2, 3]: 5+(5+10)+(5+10+4) = 39, [1, 3, 2]: 33 [2, 1, 3]: 10+(10+5)+(10+5+4) = 44, [2, 3, 1]: 43 [3, 1, 2]: 4+(4+5)+(4+5+10) = 32, [3, 2, 1]: 37

스케줄링: 탐욕적인 알고리즘 증명 정리 시스템 내부 시간의 총 시간이 최소가 되도록 하는 유일한 스케줄은 작업의 서비스 시간에 따라 오름차순으로 구성한 스케줄이다. (증명) 최적의 스케줄 T에서 ti가 i번째로 스케줄된 작업의 서비스 시간이라 하자. 이 최적의 스케줄이 서비스 시간에 따라 오름차순으로 구성되어 있지 않다고 하면 ti>ti+1인 부분스케줄이 존재한다. T에서 이 두 작업의 순서만을 바꾼 스케줄을 T'이라 하면 다음이 성립한다. T' = T+ti+1-ti 그런데 ti>ti+1이므로 T'<T이다. 따라서 오름차순으로 구성하지 않은 스케줄은 최적의 스케줄이 될 수 없다.

마감시간이 있는 스케줄 무작정 알고리즘의 시간복잡도? 이익이 가장 큰 것은 최적 스케줄에 포함되었지만 두 번째는 포함되지 않았다. 그 이유는 작업 4와 작업 2의 마감시간이 같아 둘 중 하나만 포함할 수 있기 때문이다.

마감시간이 있는 스케줄링 알고리즘 이익을 기준으로 오름차순으로 작업을 정렬한다. 정렬된 순서로 작업을 선택한다. 선택한 작업이 적정성을 검사한다. 가능한 스케줄이면 스케줄에 포함한다. 고려할 작업이 남아 있으면 단계 2부터 다시 반복한다.

마감시간이 있는 스케줄링 알고리즘

허프만 코드(Huffman Code) a, b, c를 코드화 할 수 있는 방법? Ex) ababcbbbc 000100011101010111 1001001100011

허프만 알고리즘

탐욕적 방법 Vs. 동적 프로그래밍 최적화 문제를 위해 사용할 수 있는 기법 보통 탐욕적 방법이 보다 효율적 탐욕적 방법은 알고리즘의 결과가 최적인지 증명 동적 프로그래밍은 최적화 문제가 최적의 원칙에 적용되는지 검사

0-1 배낭 채우기 문제 0-1 Knapsack problem 무작정 알고리즘 S = {item1, item2, …, itemn} wi: itemi의 무게 pi: itemi의 가치 W: 배낭이 수용할 수 있는 총 무게 A: S의 부분집합으로 선택된 item들의 집합 목표: 를 만족하면서 가 최대가 되도록 A⊆S를 만든다. 0-1? itemi는 A에 포함되거나 포함되지 않는다. 무작정 알고리즘 S의 가능한 모든 부분집합을 고려한다. 시간 복잡도?

탐욕적 알고리즘 -첫번째 가장 비싼 item 순으로 채운다. 최적? 30kg

탐욕적 알고리즘 - 두번째 가장 무게가 적은 item순으로 채운다. 최적? 30kg

탐욕적 알고리즘 - 세번째 무게당 가치가 가장 높은 물건부터 채운다. 최적? 30kg

만약, 빈틈없이 채우기라면? 배낭 빈틈없이 채우기 문제: item의 일부도 담을 수 있다. 금괴 vs. 금가루 탐욕적 알고리즘 3이 최적이다.

동적 프로그래밍으로 가능? 최적의 원칙이 성립되는가? 재귀 관계식

동적 프로그래밍 알고리즘 P[0..n][0..W] 총 계산하는 항 수:nW 시간 복잡도: Θ(nW) W = n! ? 개선방향 P[0][w] = 0, P[i][0] = 0 총 계산하는 항 수:nW 시간 복잡도: Θ(nW) W = n! ? 개선방향 아이디어: P[i][W]를 계산하기 위해서 (i-1)번째 행을 모두 계산할 필요가 없다.

예 P[3][30] P[2][30], P[2][10] P[2][30] P[1][30], P[1][20] P[2][10] P[1][10], P[1][0] P[1][0] = 0, P[1][10] = 50, P[1][30] = 50, P[1][20] = 50 P[2][10] = max(50,60+0) = 60 P[2][30] = max(50, 60+50) = 110 P[3][30] = max(110, 140+60) = 200 줄어든 항 수: 3x30=90에서 7로

개선된 알고리즘 분석 최악의 경우 계산되는 항 수 따라서, 시간복잡도? NP 문제