알고리즘 (Algorithm) 알고리즘개요 ( 효율, 분석, 차수 ) Part 1 2011년봄학기 강원대학교컴퓨터과학전공문양세
강의내용 프로그램과알고리즘순차검색과이진검색피보나찌수구하기알고리즘분석차수 (O,, ) Part 2 Page 2
프로그램의설계과정 설계분석예문제알고리즘만족? 프로그램 아니오 재설계 알고리즘은주어진문제를논리적으로해결하는과정이다. 분석을통해작성한알고리즘의정확성을파악할수있고, 효율성을정량적으로나타낼수있다. ( 일반적으로 ) 알고리즘은프로그래밍언어에독립적이다. Page 3
알고리즘과목의학습목표 Design( 설계 ): 다양한문제에대해, 알고리즘을설계하는기법을배운다. Analysis( 분석 ): 알고리즘을분석하여시간 / 공간복잡도를구하는방법을배운다. Computational Complexity( 계산복잡도 ): 문제를분석하여계산복잡도를구하는방법을배운다. Page 4
설계 ( 알고리즘 ) 가없다면 Page 5
알고리즘이란? 정의 : 문제에대한답 ( 해결책 ) 을찾기위해서계산하는절차이다. 좀더구체적인정의 알고리즘은단계별로주의깊게설계된계산과정이다. 알고리즘은입력을받아서출력으로전환시켜주는일련의계산절차이다. 음. 결국, 알고리즘이라는것은어떤절차를기술하는것이다. 또한번음 주어진입력이있을때, 원하는해답을출력하기위해서, 어떻게계산하면되는지그절차를기술하는것이다. Page 6
알고리즘의예 주어진문제 : 전화번호부에서 홍길동 의전화번호찾기 알고리즘 ( 해결책 ) 순차검색 (sequential search): 전화번호부의첫쪽부터홍길동이라는이름이나 올때까지순서대로찾는다. ( 수정된 ) 이진검색 (binary search): 전환번호부는 가나다 순으로되어있으므로먼저 ᄒ 이있을만한곳으로넘겨본후앞뒤로뒤적여가며찾는다. 분석 : 어떤알고리즘이더좋은가? Page 7
문제 (Problem) 의표기 / 표현방법 문제 : 해결책을찾고자던지는질문 매개변수 ( 파라미터, parameter): 문제에서어떤특정값이주어지지않은변수 (variable) 문제의사례 (instance) = 입력 (input): 문제에주어진파라미터에특정값을지정한것 ( 예 ) 사례에대한해답 (solution) = 출력 (output): 주어진사례에관한질문에대한답 Page 8
문제의표기예 문제 : n 개의수로된리스트 S 에 x 라는수가있는지알아내시오. 그결과, x 가 S 에있으면 예,, 없으면 아니오 로답하시오. 파라미터 : S, n, x 입력의예 1: S = [10711538] [10,7,11,5,3,8], n = 6, x = 5 출력의예 1: 예 입력의예 2: S = [10,7,11], n = 3, x = 5 출력의예 2: 아니오 Page 9
알고리즘의표기 ( 기술 ) 자연어 : 한글또는영어 ( 부정확하고모호함 ) 프로그래밍언어 : C, C++, Java, Pascal 등 ( 특정언어에의존적이어서일반적인알고리즘기술에부적합 ) 의사코드 (Pseudo-code): d) 직접실행할수있는프로그래밍언어는아니지만, 실제프로그램에 거의가깝게계산과정을표현할수있는언어 알고리즘은보통의사코드로표현한다. 본강의에서는 C++( 혹은 C) 에가까운의사코드를사용한다. Page 10
프로그래밍언어 vs 알고리즘 / 자료구조 Page 11
C/C++ 와의사코드의차이점 (1/3) 배열인덱스의범위에제한없음 C/C++ 는반드시 0 부터시작 의사코드는임의의값사용가능 ( 예 : int x[5..10];) 프로시저의파라미터에 2 차원배열크기의가변성허용 예 : void pname(a[][]) { } C/C++ 에서는다음과같이제한이필요함 : void pname(a[][10]){ } 지역배열에변수인덱스허용 예 : keytype S[low..high]; C/C++ 에서는숫자인덱스만가능함 Page 12
C/C++ 과의사코드의차이점 (2/3) 수학표현식및간단한자연어허용 low <= x && x <= high low x high temp = x; x = y; y = temp; exchange x and y; C/C++ C 에없는타입사용가능 index: 첨자로사용되는정수변수 number: 정수 (int) 또는실수 (float) 모두사용가능 bool: true 나 false 값을가질수있는변수 이외에도잘알려진키워드 ( 예 : record, list) 는별도정의없이사용 Page 13
C/C++ 과의사코드의차이점 (3/3) 제어구조 repeat (n times) { } 프로시저와함수의구분 프로시저 : void pname( ) { } 함수 : returntype fname ( ) { return x;} 참조파라미터 (reference parameter) 를사용하여프로시저의결과 값전달방법 (call by reference 를설명하고있음 ) 배열 : ( 기본적으로 ) 참조파라미터로전달 나머지 : 데이터타입이름뒤에 & 를붙임 const 배열 : 전달되는배열의값이불변 Page 14
강의내용 프로그램과알고리즘순차검색과이진검색피보나찌수구하기알고리즘분석차수 (O,, ) Part 2 Page 15
순차검색 (Sequential Search) (1/3) 문제 : 크기가 n 인배열 S 에 x 가있는가? 입력 ( 파라미터 ): (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력 : x 가 S 의어디에있는지의위치, 만약없으면 0 알고리즘 ( 자연어 ): x 와같은아이템을찾을때까지 S 에있는모든아이템을차례로검사한다. 만일 x 와같은아이템을찾으면 S 에서해당위치를출력하고, S 를모두검사하고도찾지못하면 0을출력한다. 자연어알고리즘은문제를풀기는하였으나, 프로그램으로전환하기에는용이하지않다. Page 16
순차검색 (Sequential Search) (2/3) 알고리즘 ( 의사코드 ) void seqsearch(int n, // 입력 (1) const keytype S[], // 입력 (2) keytype x, // 입력 (3) index& location) // 출력 { } location = 1; while (location <= n && S[location]!= x) location++; if (location > n) location = 0; while- 루프 : 아직검사할항목이있고, x 를찾지못하였나? if- 문 : 모두검사하였으나, x 를찾지못했나? Page 17 돌아가기
순차검색 (Sequential Search) (3/3) 순차검색알고리즘으로키를찾기위해서 S에있는항목을몇개나검색해야하는가? 키와같은항목의위치에따라다름 최악의경우 : n 평균의경우 : n/2 좀더빨리찾을수는없는가? 더이상빨리찾을수있는알고리즘은존재하지않는다. 배열 S에있는항목에대한정보가전혀없는상황에서, 모든항목을검색하지않고임의의항목 x를항상찾을수있다는보장이없기때문이다. 만약, 배열 S 가정렬되어있다는정보가존재한다면? 이진검색 Page 18
순차검색 -- C Program 실제 C 프로그램을봅시다. 알고리즘과는어떤차이가있는지확인합시다. Page 19
이진검색 (Binary Search) (1/3) 문제 : 크기가 n 인정렬된배열 S 에 x 가있는가? 입력 : (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력 : x 가 S 의어디에있는지의위치, 만약없으면, 0 순차검색의문제와다른점은배열 S 가 정렬 되어있다는정보를알고있다는점이다. 순차검색의문제가보다일반적이므로, 순차검색을사용하여이문제를풀수있다. 그러나, 순차검색을사용하면 정렬 되어있다는정보를를사용하지못하는것이된다. Page 20
이진검색 (Binary Search) (2/3) 알고리즘 ( 의사코드 ) void binsearch(int n, // 입력 (1) const keytype S[], // 입력 (2) keytype x, // 입력 (3) index& location) o // 출력 { index low, high, mid; low = 1; high = n; location = 0; while (low <= high && location == 0) { mid = (low + high) / 2; // 정수나눗셈 if (x == S[mid]) location = mid; else if (x < S[mid]) high = mid 1; else low = mid + 1; } } while- 루프 : 아직검사할항목이있고, x 를찾지못하였나? Page 21
이진검색 (Binary Search) (3/3) 비교횟수를 ( 개략적으로 ) 분석해본다. 배열의크기가 32 라면 6 번의비교가필요하다. 이때, 6 = lg 32 + 1 이다. 배열의크기가 64라면 7번의비교가필요하다. 이때, 7 = lg 64 + 1이다. 배열의크기가 2 k 라면 k+1번의비교가필요하다. 이때, k+1 = lg 2 k + 1이다. 이분검색알고리즘으로키를찾기위해서 S 에있는항목을몇개나검색해야하는가? while 문을수행할때마다검색대상의크기가절반으로감소하기때문에최악의경우라도 lg n + 1번만비교하면된다. 상기횟수분석에서 n = 2 k 라하면, 비교횟수는 lg n + 1 이된다. Page 22
순차검색 vs. 이진검색 배열의크기순차검색이진검색비고 n n lg n + 1 128 128 8 1,024 1,024 11 1,048,576 1,048,576 21 두방법모두최악의경우에대한비교횟수임 4,294,967,296 4,294,967,296 33 Page 23
강의내용 프로그램과알고리즘순차검색과이진검색피보나찌수구하기알고리즘분석차수 (O,, ) Part 2 Page 24
피보나찌 (Fibonacci) 수열 피보나찌수열의정의 f 0 f 1 0 1 f, for 2 n fn 1 fn 2 n 예 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, Page 25
자연계의피보나찌수열 Page 26
피보나찌수구하기 재귀알고리즘 (1/4) 문제 : n 번째피보나찌수를구하라. 입력 : 양수 n 출력 : n 번째피보나찌수 재귀 (recursive) 알고리즘 : int fib(int n) { if (n <= 1) return n; else return (fib(n-1) + fib(n-2)); } Page 27
피보나찌수구하기 재귀알고리즘 (2/4) 분석 : 피보나찌수구하기재귀알고리즘은수행속도가매우느리다. 이유: 같은피보나찌수를중복하여계산한다. 예 : fib(5) 계산을위해서는 fib(2) 를세번이나중복계산한다. 함수 fib(5) 호출시의재귀트리 (recursive tree) 실제호출되는상황을봅시다! Page 28
피보나찌수구하기 재귀알고리즘 (3/4) fib(n) 함수호출횟수계산 T(n) ( ) = fib(n) ( ) 을계산하기위하여 fib() 함수를호출하는횟수 즉, T(n) 은재귀트리상의마디의개수 T (0) 1; T(1) 1; Tn ( ) Tn ( 1) Tn ( 2) 1 for n 2 2 Tn ( 2) since Tn ( 1) Tn ( 2) 2 2 Tn ( 4)... 3 2 Tn ( 6) T n/2 2 (0) 2 n/2 Page 29
피보나찌수구하기 재귀알고리즘 (4/4) 정리 : 재귀적알고리즘으로구성한재귀트리의마디의수를 T(n) 이라하면, n 2 인모든 n 에대하여 T(n) ( ) > 2 n/2 이다. 증명 : (n 에대한수학적귀납법으로증명 ) Induction base: T(2) = T(1) + T(0) + 1 = 3 > 2 = 2 2/2 T(3) = T(2) + T(1) + 1 = 5 > 2.83 2 3/2 Induction hypothesis: 2 m < n인모든m에대해서 T(m) > 2 m/2 이라가정 Induction step: T(n) > 2 n/2 임을보인다. T(n) = T(n -1) + T(n -2) + 1 > 2 (n -1)/2 + 2 (n -2)/2 + 1 [ 귀납가정에의하여 ] > 2 (n -2)/2 + 2 (n -2)/2 = 2 2 (n / 2)-1 = 2 n/2 Page 30
피보나찌수구하기 반복알고리즘 (1/2) 문제 : n 번째피보나찌수를구하라. 입력 : 양수 n 출력 : n 번째피보나찌수 반복 (iterative) 알고리즘 : int fib2 (int n) { index i; int f[0..n]; f[0] = 0; if (n > 0) { f[1] = 1; for (i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2]; } return f[n]; } Page 31
피보나찌수구하기 반복알고리즘 (2/2) 분석 : 반복알고리즘은수행속도가훨씬더빠르다. 이유 : 재귀알고리즘과는달리중복계산이없다. 계산하는항 (f[i]) 의총개수 T(n) = n + 1 즉, f[0] 부터 f[n] 까지단한번씩만계산한다. Page 32
피보나찌수구하기 재귀 vs. 반복 (1/2) 노드하나 ( 혹은항하나 ) 계산에 1 ns 걸린다고가정하자. n n+1 2 n/2 반복 재귀 ( 하한 ) 40 41 1,048,576 41ns 1048 s 60 61 1.1 10 9 61ns 1s 80 81 1.1 10 12 81ns 18min 100 101 1.1 10 15 101ns 13days 120 121 12 10 1.2 10 18 121ns 36years 160 161 1.2 10 24 161ns 3.8 10 7 years 200 201 1.3 10 30 201ns 4 10 13 years Page 33
피보나찌수구하기 재귀 vs. 반복 (2/2) 재귀알고리즘보다는반복알고리즘이항상효율적이다? 꼭그렇지만은않다. 특히, 설계단계에서재귀알고리즘은매우유용하다. 피보나찌수구하기의재귀알고리즘은 Ch. 2에서다루는분할정복 (Divide & Conquer) 의전형적인예이다. 피보나찌수구하기의반복알고리즘은 Ch. 3 에서다루는동적프로그래밍 (Dynamic Programming) 의간단한보기이다. Page 34
강의내용 프로그램과알고리즘순차검색과이진검색피보나찌수구하기알고리즘분석차수 (O,, ) Part 2 Page 35
알고리즘의분석 (analysis) 시간복잡도 (Time Complexity) 분석 입력크기에따라서단위연산이몇번수행되는지결정하는절차 표현척도 단위연산 (basic operation): 비교문 (comparison), 지정문 (assignment) 등 입력크기 (input size): 배열의크기, 리스트의길이, 행렬에서행과열의크기, 트리에서꼭지점과에지의수 Page 36
분석방법의종류 (1/2) 모든경우분석 (Every-case analysis) 복잡도는입력크기에만종속 (dependent) 적임 입력값과는무관 (independent) 하게복잡도는항상일정 예 : 평균을구하라. 최악의경우분석 (Worst-case analysis) 복잡도는입력크기와입력값모두에종속 단위연산이수행되는횟수가최대 ( 최악 ) 인경우선택 Page 37
분석방법의종류 (2/2) 평균의경우분석 (Average-case analysis) 입력크기와입력값모두에종속 모든입력에대해서단위연산이수행되는기대치 ( 평균 ) 각입력값에대해서확률할당이가능 확률에따라기대치가다르게계산될수있음 일반적으로최악의경우보다계산이복잡 최선의경우분석 (Best-case analysis) 입력크기와입력값모두에종속 단위연산이수행되는횟수가최소 ( 최선 ) 인경우선택 Page 38
배열덧셈알고리즘 문제 : 크기가 n 인배열 S 의모든수를더하라. 입력 : 양수 n, 배열 S[1..n] 출력 : 배열 S 에있는모든수의합 알고리즘 : number sum (int n, const number S[]) { index i; number result; } result = 0; for (i = 1; i <= n; i++) result = result + S[i]; return result; Page 39
배열덧셈알고리즘 : 시간복잡도분석 단위연산 : 덧셈 입력크기 : 배열의크기 n 모든경우분석 : 배열내용에상관없이 for- 루프가 n 번반복된다. 각루프마다덧셈이 1 회수행된다. 단위연산 : 지정문 (for-루프의첨자지정문포함 ) 입력크기 : 배열의크기 n 모든경우분석 : 배열내용에상관없이 for- 루프가 n번반복된다. 따라서, n에대해서덧셈이수행 따라서, 지정문이 되는총횟수는 T(n) = n 이다. T(n) = n + n + 1번수행된다. 기본동작을다르게함으로써, 시간복잡도가다르게나왔다. 그러나, 사실둘모두는같은복잡도카테고리에속한다. Page 40
버블정렬 (Bubble Sort) 알고리즘 문제 : 비내림차순으로 n 개의키를정렬 입력 : 양수 n, 배열 S[1..n] 출력 : 비내림차순으로정렬된배열 알고리즘 : void exchangesort (int n, keytype S[]) { index i, j; } for (i = 1; i <= n-1; i++) for (j = i+1; j <= n; j++) if (S[j] < S[i]) exchange S[i] and S[j]; for(j = 1;j <= (n-i); j++) if (S[j] > S[j+1]) exchange S[j] and S[j+1]; Page 41 exchange sort bubble sort
버블정렬알고리즘 : 시간복잡도분석 I 단위연산 : 조건문 (S[j] 와 S[i] 의비교 ) 입력크기 : 정렬할항목의수 n 모든경우분석 : j- 루프가수행될때마다조건문을 1 번씩수행 조건문의총수행횟수 i = 1 : j- 루프 n 1 번수행 i = 2 : j- 루프 n 2 번수행 i = 3 : j- 루프 n 3 번수행 i = n 1 : j- 루프 1 번수행 따라서 Tn ( ) ( n 1) ( n 2) 1 ( n 1) n 2 Page 42
버블정렬알고리즘 : 시간복잡도분석 II 단위연산 : 교환하는연산 (exchange S[j] and S[i]) 입력크기 : 정렬할항목의수 n 최악의경우분석 : 조건문의결과에따라서교환연산의수행여부가결정된다. 최악의경우 = 조건문이항상참 (true) 이되는경우 = 입력배열이거꾸로정렬되어있는경우 Tn ( ) ( n 1) n 2 Page 43
순차검색알고리즘 : 시간복잡도분석 (1/4) 단위연산 : 배열의아이템과키 x 와비교연산 (S[location]!= x) 입력크기 : 배열안에있는아이템의수 n 최악의경우분석 : x가배열의마지막아이템이거나, x가배열에없는경우, 단위연산이 n번수행된다. 따라서, W ( n ) n 순차검색알고리즘의경우입력배열의값에따라서검색하는횟수가달 라지므로, 모든경우 (every-case) 의시간복잡도분석은불가능하다. 순차검색알고리즘보기 Page 44
순차검색알고리즘 : 시간복잡도분석 (2/4) 단위연산 : 배열의아이템과키 x 와비교연산 (S[location]!= x) 입력크기 : 배열안에있는아이템의수 n 가정 : 배열의아이템이모두다르다. 평균의경우분석 ( 경우 1): x 가배열 S 안에있는경우만고려 1 k n 에대해서 x 가배열의 k 번째있을확률 = 1/n x 가배열의 k 번째있다면, x 를찾기위해서수행하는단위연산의횟수 = k 따라서, n n 1 1 1 nn ( 1) n 1 An ( ) k k n n n 2 2 k 1 k 1 Page 45
순차검색알고리즘 : 시간복잡도분석 (3/4) 평균의경우분석 ( 경우 2): x 가배열 S 안에없는경우도고려 x 가배열 S 안에있을확률을 p 라고하면, x 가배열에있을확률 = p (x 가배열의 k 번째있을확률 = p/n) x 가배열에없을확률 = 1 p 따라서, 참고 : n p An ( ) k n (1 p ) k 1 n p nn ( 1) n 1 n(1 p) p n(1 p) n 2 2 p p n 1 2 2 p 1 An ( ) ( n 1)/2 p 1/2 A( n) 3 n/4 1/4 Page 46
순차검색알고리즘 : 시간복잡도분석 (4/4) 단위연산 : 배열의아이템과키 x 와비교연산 (S[location]!= x) 입력크기 : 배열안에있는아이템의수 n 최선의경우분석: x 가 S[1] 일때, 입력의크기에상관없이단위연산이 1 번만수행된다. 따라서, B(n) = 1 Page 47
계산 ( 시간 ) 복잡도 : 어떤것을사용하지? 최악, 평균, 최선의경우분석방법중에서어떤분석이가장정확한가? ( 분석자체야모두정확해야한다.) 최악, 평균, 최선의경우분석방법중에서어떤분석을사용할것인가? ( 응용에따라다르나, 대개최악 / 평균을사용한다.) Page 48
정확도분석? 알고리즘이의도한대로수행되는지를증명하는절차 ( 즉, 알고리즘이정확하게수행되는지를증명하는절차 ) 정확한알고리즘이란? 어떠한입력에대해서도답을출력하면서멈추는알고리즘 정확하지않은알고리즘이란? 어떤입력에대해서멈추지않거나, 또는 틀린답을출력하면서멈추는알고리즘 정확도분석은프로그램증명 (Program Verification) 과마찬가지로 매우이론적인분야로서, Dijkstra 등에의해서연구되었다. Page 49
Who is Dijkstra? Page 50
Homework #1 Page 51