알고리즘 1장 기본개념

Transcription

1 Video & Image VIPLProcessing Lab Myoung-Jin Kim, Ph.D. Research Professor(Soongsil University)

2 컴퓨터학과이관용교수 Myoung-Jin Kim, Ph.D.

3 알고리즘의기본개념

4 알고리즘의중요성 자료구조파일처리 DB 데이터 컴퓨터시스템디지털논리회로컴퓨터구조 결과 운영체제정보통신컴파일러 프로그램 프로그래밍언어론소프트웨어공학컴퓨터그래픽스 알고리즘 이산구조계산이론인공지능알고리즘오토마타 4

5 알고리즘이란? 주어진문제를풀기위한명령어들을단계적으로나열한것 문제를해결하거나함수를계산하기위해좇아야할모호함이없는간단한명령들로구성된일련의순서적단계 an ordered set of unambiguous, executable steps that produces a result and terminates in a finite time 튜링기계에의해수행가능한프로시저 계산이론 (computational theory) 5

6 알고리즘의중요성 컴퓨터의한계 알고리즘의존재여부 컴퓨터과학 = 알고리즘과학 알고리즘의한계 알고리즘의실행 알고리즘의분석 알고리즘 알고리즘간의통신 알고리즘의개발 알고리즘의표현 6

7 알고리즘의정의와요건 입출력 0개이상의외부입력 1개이상의출력 모호하지않고단순명확한명령 한정된수의작업후에는반드시종료 모든명령은수행가능해야함 ( 실용적관점 ) 효율적이어야함 주어진문제에대한결과를생성하기위해모호하지않고간단하며컴퓨터가수행가능한일련의유한개의명령들을순서적으로구성한것 7

8 알고리즘생성단계 설계 상향식설계하향식설계 표현 / 기술 일상언어, 순서도, 의사코드, 프로그래밍코드등 정확성검증 효율성분석 수학적검증실용적검증 공간복잡도시간복잡도 8

9 알고리즘기술언어 알고리즘기술방법 자연어에의한표현 일상언어 한글또는영문 의사코드 (Pseudo Code) 도형에의한표현 순서도 ( 흐름도 :Flow Chart) 박스 (Box) 다이어그램 C 언어에기반한의사프로그래밍언어 9

10 알고리즘기술언어 (C- 유사 ) 변수선언 지정문 반복문 int min, max; float degree, b; char ch, token; min = 10; degree = a + b; while (age <= adult) { } for (i=1; i < n; i++) { } 10

11 알고리즘기술언어 (C- 유사 ) 조건문 배열 if ( age > adult ) 문장 1 else 문장 2 함수 int num[10]; num[0],, num[9] Power (x, n) { p=1; for (i=1; i<=n; i++) p = p * x; return (p); } printf( Power (2, 5) ); 11

12 기본자료구조

13 자료구조와알고리즘의관계 자료구조 컴퓨터기억공간내에자료를표현하고조직화시키는방법 자료구조의선택과알고리즘의효율성의관계 자료구조단순 연산단계및수행시간의증가 자료구조복잡 연산횟수감소 프로그램 자료구조 + 알고리즘 기본자료구조 배열연결리스트큐스택트리그래프 13

14 기본자료구조 배열 정적구조 배열내의각원소접근시간이동일하므로원소들을임의순서로처리할경우유리 배열의중간에서의삽입 삭제시많은시간소요 A B D E F G H 14

15 기본자료구조 연결리스트 삽입과삭제가용이 동적구조 리스트내의한노드를찾기위해그노드앞에위치하는모든노드를차례대로따라가야만함 헤드포인터 데이터 포인터 데이터 포인터 데이터 NIL 15

16 기본자료구조 스택 큐 top D C B A 삭제 삽입 Head / Front Tail / Rear 16

17 트리 하나이상의노드로구성된유한집합 T T 의원소가운데단하나의루트노드가존재 루트노드를제외한나머지노드는 n 개 (n 0) 의서로분리된부분집합 T 1, T 2,, T n ( 서브트리 ) 으로나누어진다. A T 1 T 2 T 3 B C T 31 D T 11 E F G H I J K L M N T 12 T 32 T 33 17

18 트리 뿌리나무 (rooted tree) 나무의정점중하나가뿌리 (root) 로지정된것 A B E F C D G H I 18

19 기본자료구조 뿌리가 r 인뿌리나무 T 의어떤노드 x 에대하여 조상 (ancestor) 과자손 (descendant) r 로부터 x 까지의경로상에존재하는노드 y 는 x 의조상이고, x 는 y 의자손 부분나무 (subtree) 뿌리 x 와 x 의자손들로이루어진나무 부모 (parent) x 의바로위쪽에연결된노드 자식 (child) x 의아래쪽에연결된노드 동기 (sibling) 부모가같은노드들 잎 (leaf) 자식이없는노드 19

20 기본자료구조 차수 (degree) 뿌리나무 T 에서노드 x 의자식의개수 깊이 (depth) 뿌리 r 에서노드 x 까지의경로의길이 높이 (height) 뿌리나무 T 에서가장큰깊이 수준 (level) 깊이가같은노드들을동일한수준에있는노드들이라함 순서나무 (ordered tree) 노드의각자식에순서가부여된뿌리나무 이진나무 (binary tree) 각노드의자식이 2 개이하인순서나무 20

21 이진트리 각노드의차수가 2 이하인순서트리 A A A A B B B C A A A B C B B D E C C 21

22 이진트리의종류 A A B C B C D E F G D E F G H I J K L M N O 포화 perfect 이진트리 A H I J K 전 full 이진트리 A B C B C D E F G D E F G H I J 완전 complete 이진트리 N 균형 balanced 이진트리 O 22

23 이진트리의구현 A B C D E F G H I J K 일차원배열을이용한구현 A B C D E F G H I J K 연결리스트를이용한구현 23

24 그래프 그래프 G=(V,E) V : 정점의집합, E : 간선의집합 무방향그래프 방향그래프 1 (1,2) = (2,1) 3 <1,2> <2,1> 가중그래프 17 A B E C C

25 그래프 주요용어 인접 adjacent, 부속 incident 부분그래프 subgraph 경로 path, 경로의길이 length 차수 degree 진입차수 in-degree, 진출차수 out-degree 단순경로 simple path, 사이클 cycle, 루프 loop 연결 connected 강력연결 strongly connected 25

26 그래프의구현 인접행렬 head[] 인접리스트

27 알고리즘의설계

28 알고리즘설계 창조적활동 최대값찾기 : 방법 1 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 28

29 알고리즘설계 최대값찾기 : 방법 2 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 방법 1 & 2 가장작은횟수의비교 (n-1 번 ) 로최대수를찾는효율적인알고리즘 29

30 뒤섞인카드에서 K 찾기 30

31 뒤섞인카드에서 K 찾기 (1) (2) (3) 31

32 뒤섞인카드에서 K 찾기 (4) (5) (6) 32

33 순차탐색 SeqSearch (A, n, x) /* 입력 : A, n, x 출력 : j */ 1 { 2 j = 1; 3 while (j n && A(j)!=x) 4 j = j + 1; 5 return (j); 6 } 33

34 순서대로나열된카드에서 J 찾기 이진탐색 34

35 이진탐색알고리즘 BinarySearch (A[], key, left, right) // A[mid]=key인인덱스 mid를반환 { 1 mid = (left + right)/2; 2 if (A[mid] = key) return(mid); 3 else if (A[mid] > key) BinarySearch(A, key, left, mid-1) 4 else BinarySearch(A, key, mid+1, right); } 35

36 알고리즘설계 설계방법은다양하며, 일정한틀을제시하기곤란 대표적인설계기법 욕심쟁이방법 greedy method 분할정복방법 divide and conquer method 동적프로그래밍방법 dynamic programming method 36

37 분할정복방법 순환적으로문제를푸는방법 분할 정복 주어진문제를여러개의작은문제로분할 작은문제들을순환적으로처리하여정복. 만약작은문제의크기가충분히작다면순환호출없이작은문제에대한해가구해짐 결합 작은문제에대해정복된해를결합하여원래문제의해를구함 2 장 ( 퀵정렬, 합병정렬 ), 3 장 ( 이진탐색 ) 37

38 욕심쟁이방법 해를구하는일련의선택과정마다그단계에서 가장최선 이라고여겨지는국부적인최적해를선택해나가면결과적으로전체적인최적해를구할수있을것이라고희망적인전략을취하는방법 희망적 각단계마다선택한최적해가전체최적해를만들어내지못할수있음을의미 1 장. 거스름돈문제, 배낭문제 4 장. 프림알고리즘, 크루스칼알고리즘, 데이크스트라알고리즘 39

39 욕심쟁이방법의한계 욕심쟁이가세상에서가장멋진상의와바지, 세상에서가장멋진넥타이를구입하는경우, 욕심쟁이는세상에서으뜸가는멋쟁이? 욕심쟁이방법으로해를구할수없는문제도있다. 그러나욕심쟁이방법을적용할수있다면아주간단하게알고리즘을만들수가있다. 40

40 거스름돈문제 고객에게돌려줄거스름돈이 T 만큼있을때고객이받을동전의개수를최소로하면서거스름돈을돌려주는문제 동전의종류 : 500 원, 100 원, 50 원, 10 원, 5 원, 1 원 단순히액면가가큰동전부터최대한뽑아서거스름돈을제공 870 원 370 원 70 원 20 원

41 배낭문제 최대용량 M 인하나의배낭과각각무게 w i 와이익 p i 가부여되어있는 n 개의물체가있다고가정 배낭문제 배낭의용량을초과하지않는범위에서배낭에들어있는물체의이익의합이최대가되는해를찾아내는것 물체를쪼갤수있다고가정 42

42 배낭문제 P 1 = 15 w 1 = 3 P 2 = 20 w 2 = 5 M=10 n=4 P 3 = 9 w 3 = 3 P 4 = 14 w 4 = 4 43

43 배낭문제 문제 M = 10, n = 4 (p 1, p 2, p 3, p 4 )= (15, 20, 9, 14) (w 1, w 2, w 3, w 4 ) = (3, 5, 3, 4) 각물체의가중치 ( 단위무게당이익 ) p w 1 1, p w 2 2, p w 3 3, p w 4 4 (5, 4, 3, 3.5) 최대이익 최대이익 = w 1 + w 2 + w 4 * ½ = 42 44

44 0/1 배낭문제 물체를쪼갤수없는경우 M = 10, n = 4 (p 1, p 2, p 3, p 4 )= (15, 20, 9, 14) (w 1, w 2, w 3, w 4 ) = (3, 5, 3, 4) p w 1 1, p w 2 2, p w 3 3, p w 4 최대이익 = W 1 + W 2 = 35 실제최대이익 = W 1 + W 3 + W 4 = 38 욕심쟁이방법적용불가 4 (5, 4, 3, 3.5) 46

45 알고리즘의분석

46 알고리즘분석 정확성분석 유효한입력, 유한시간, 정확한결과산출여부 실용적 이론적 테스트데이터에 대한디버깅결과 수학적증명 논리적으로정확함을보임 프로그램이정확하다는것을증명하지못함 48

47 알고리즘분석 효율분석 알고리즘수행에필요한컴퓨터자원의양을측정 시간복잡도 (time complexity) 알고리즘이필요로하는수행시간의크기 공간복잡도 (space complexity) 알고리즘이필요로하는메모리공간의크기 ( 정적공간 + 동적공간 ) 49

48 시간복잡도 알고리즘의수행시간 실제실행시간을측정 일반성결여 수행하는기본연산의수행회수로계산 알고리즘의수행시간 = { 각문장 ( 연산 ) 의수행회수 해당문장의수행시간 } 모두동일하다고생각함 50

49 시간복잡도 입력크기의함수로표현 입력크기 : 입력되는데이터의크기 문제가해결하고자하는대상이되는개체의개수 행렬의크기, 리스트원소의수, 그래프정점의수등 입력상태에종속적 평균수행시간 A(n) 최악수행시간 W(n) 최선수행시간 B(n) A ( n) P( I ) t( I ) I S n W ( n) max t( I ) IS n B( n) min t( I ) IS n S n : 크기가 n 인입력들의집합 P(I) : 입력 I 가발생할확률 t(i) : 입력 I 일때알고리즘의수행시간 51

50 순차탐색의수행시간 SeqSearch (A, n, x) /* 입력 : A, n, x 출력 : j */ 1 { 1 n+1 n 1 2 j = 1; 3 while (j n && A(j)!=x) 4 j = j + 1; 5 return (j); c 1 c 2 c 3 c 4 k 번 k-1 번 T(n) = 2n+3 6 } c 1 c 2 k c 3 ( k 1) c4 ( c2 c3 ) k ( c1 c3 c4 ) ak b O(n) 52

51 53 순차탐색의수행시간 평균 : k = n/2 최악 : k=n b ak c c c k c c c k c k c c ) ( ) ( 1) ( ( 상수 ) 상수 n b n a n A 2 ) ( b n a n W ) (

52 순차탐색의수행시간 ( 상수 n+ 상수 ) 하나의상수항은몇개의명령문들의수행시간을합쳐놓은것 컴퓨터의성능 / 종류에종속적이므로각명령마다부여한상이한수행시간이별의미가없음 간단히명령마다동일한시간내에처리된다고가정해도무방 54

53 순차탐색의수행시간 상수항보다 n 의차수가더중요 상수값을무시하고단지입력크기에대한차수만고려 데이터의개수가많을경우알고리즘의수행시간이보다중요한의미를가짐 이경우상수항이아닌 n 의최고차수에좌우 하위차수는무시 55

54 순차탐색의수행시간 5 개알고리즘의 n 값에따른수행시간비교 알고리즘 시간 (µs) 33n 46nlgn 13n 2 3.4n 3 2 n n=10 n=100 n=1000 n=10,000 n=100,000 처리가능최대입력개수 1 초 1 분 초.003 초.033 초.33 초 3.3 초 30,000 1,800, 초.03 초.45 초 6.1 초 1.3 분 2,000 82, 초.13 초 13 초 22 분 1.5 일 280 2, 초 3.4 초.94 시간 39 일 108 년 초 4x10 4 세기

55 점근성능

56 점근성능 입력크기 n 이커질때의알고리즘의성능 입력의크기 n 이커짐에따라상수항과차수가낮은항들의역할이감소 n 의최고차수에의존 10n+9 n 2 /2+3n n=5 n=10 n=15 n=16 n= 실제로알고리즘의수행시간이문제가되는것은입력크기가커질때이며따라서점근성능을알고리즘의시간복잡도로쓰는것이다. 58

57 점근성능의표기법 정의 Big-oh 점근적상한 (1) n n 0 인모든 n에대하여 f(n) c g(n) 을만족하는양의상수 c, n 0 이존재하면 f(n)=o(g(n)) 이다. cg(n) f(n) n 0 n 59

58 점근성능의표기법 정의 Big-omega 점근적하한 (2) n>n 0 인모든 n 에대하여 f(n) c g(n) 을만 족하는양의상수 c, n 0 이존재하면 f(n)=ω(g(n)) 이다. f(n) cg(n) n 0 n 60

59 점근성능의표기법 정의 (3) n n 0 인모든 n에대하여 Big-theta 점근적상하한 c 1 g(n) f(n) c 2 g(n) 을만족하는양의상수 c 1, c 2, n 0 이존재하면, 즉 f(n)=ω(g(n))=o(g(n)) 이면 f(n) =(g(n)) c 1 g(n) f(n) c 2 g(n) n 0 n 61

60 점근성능의표기법 f(n)=3n+3, g(n)=n (c=5, n0=2 일때 ) n 2 에대해서 3n+3 5 n f(n)=o(g(n))=o(n) (c=3, n0=1 일때 ) n 1 에대해서 3n+3 3 n f(n)=ω(g(n))=ω(n) f(n)=o(n) and f(n)=ω(n) f(n)=θ(n) f(n)=3n 3 +3n-1, g(n)=n 3 (c=7, n0=1 일때 ) n 1 에대해서 3n 3 +3n-1 7 n f(n)=o(n 3 ) (c=2, n0=2 일때 ) n 3 에대해서 3n 3 +3n-1 2 n f(n)=ω(n 3 ) f(n)=o(n 3 ) and f(n)=ω(n 3 ) f(n)=θ(n 3 ) n n 0 인모든 n 에대하여 f(n) c g(n) 을만족하는양의상수 c, n 0 이존재하면 f(n)=o(g(n)) 이다. 62

61 점근성능의표기법 f(n)=2n 3 +3n 2 -n+10, g(n)=n 3 (c=5, n0=5일때 ) n>5에대해서 2n 3 +3n 2 -n+10 5 n 3 (2x5 3 +3x ) (5x5 3 ) f(n)=o(n 3 ) 336=((2x125)+75+5) 625=(5x125) (c=2, n0=3일때 ) n>3에대해서 2n 3 +3n 2 -n+10 2 n 3 (2x3 3 +3x ) (2x3 3 ) f(n)=ω(n 3 ) 91=((2x27)+27+5) 54=(2x27) f(n)=o(n 3 ) and f(n)=ω(n 3 ) f(n)=θ(n 3 ) 63

62 점근성능의표기법 주요함수간의연산시간의크기관계 O(1) < O(logn) < O(n) < O(nlogn) < O(n 2 ) < O(n 3 ) < O(2 n ) < O(n!) 효율적 비효율적 10n+9 n 2 /2+3n O(n) O(n 2 ) 64

63 입력크기에따른연산의증가추세 logn n nlogn n 2 n 3 2 n

64 함수의증가율 ( 수행시간 ) 값 2 n n 3 n 2 n nlog 2 n log 2 n 입력크기 (n) 66

65 시간복잡도와표기법 알고리즘의시간복잡도를구하려면 알고리즘계산시간 ( 연산의수행빈도수 ) f(n) 을구한후 f(n)=o(g(n)) 을만족하는최소의 g(n) 을찾음 실용적인접근방법 알고리즘에나타난루프의반복회수를조사 g(n) 은최고차수에지배 67

66 시간복잡도와표기법 i = 1; while (i <= n) { x = x + 1; i = i + 1; } int i, j; for (i=1; i<=n; i++) for (j=1; j<=n; j++) if ( j > i) C[i,j] = A[i]*B[j]; 3n+2 O(n) O(n 2 ) 68

67 순환알고리즘의성능

68 순환알고리즘의성능 BinarySearch (A[], key, left, right) { 1 mid = (left + right)/2; 2 if (A[mid] = key) return(mid); 3 else if (A[mid] > key) BinarySearch(A, key, left, mid-1) 4 else BinarySearch(A, key, mid+1, right); } 순환알고리즘의수행시간을나타내기위한방법으로점화식이사용됨 T ( n) T ( n / 2) O(1) 70

69 점화식 T ( n) T ( n / 2) c, T (1) c T ( n) T ( n / 2) c T ( n / 4) c c T ( n / 2 ) 2c T ( n / 8) c c c T ( n / 2 ) 3c k 1 T ( n / 2 ) ( k 1) c2 k T ( n / 2 ) kc2 T (1) kc2 c kc 1 2 c c log n (log n) k n 2 인경우에만정의가능 ( k=log n) 2 71

70 기본점화식과폐쇄형 (1) (1), T ( n) T ( n 1) (1), n 1 n 2 T ( n) ( n) (2) T ( n) (1), T ( n 1) ( n), n n 1 2 T ( n) ( n 2 ) (3) T ( n) (1), T ( n / 2) (1), n n 1 2 T ( n) (log n) (4) T ( n) (1), T ( n / 2) ( n), n n 1 2 T ( n) ( n) (5) (6) (1), T ( n) 2T ( n / 2) (1), (1), T ( n) 2T ( n / 2) ( n), n 1 n 2 n 1 n 2 T ( n) ( n) T ( n) ( n log n) 72