1. 행렬 곱셈(matrix multiplication) [단순한 행렬곱셈 알고리즘] - 문제: $ n \times n $ 크기의 행렬의 곱을 구하시오. - 입력: 양수 n, $ n \times n $ 크기의 행렬 A와 B - 출력: 행렬 A와 B의 곱인 C - 알고리즘 void matrixmult (int n, const number A[][], const number B[][], number C[][]){ index i, j, k; for (i = 1; i
1. 빠른 정렬(Quick Sort) - 절대적으로 가장 빠른 정렬 알고리즘은 아님 - 분할교환정렬(partition exchange sort)의 명칭이 더 정확함 [빠른 정렬 알고리즘] - 문제: n개의 정수를 비내림차순으로 정렬 - 입력: 정수 n > 0, 크기가 n인 배열 S[1...n] - 출력: 비내림차순으로 정렬된 배열 S[1...n] - 알고리즘 void quicksort (index low, index high){ index pivotpoint; if (high > low){ // 데이터가 두 개 이상 존재 partition(low, high, pivotpoint); quicksort(low, pivotpoint - 1); quicksort(pivotpoint + 1, high); } }..
1. 분할정복법: 큰 문제를 작은 문제로 나누고 작은 문제의 해를 통해 큰 문제의 해를 구하는 방식 - 큰 문제의 형태가 작은 문제의 형태와 동일함 -> 재귀적 방법 많이 사용한다. 분할정복(divide-and-conquer)식 설계 전략 - 분할(divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다. - 정복(conquer): 나눈 작은 문제를 각각 해결한다. - 통합(combine): 해결된 해답을 모은다. (필요 시) -> 하향식 접근 방법 (Top-down) 2. 이분검색(binary search): 재귀적 방식 [설계 전략] - x(key)가 배열의 중간에 위치하고 있는 항목과 같으면, x 찾음 - 그렇지 않다면 분할 정복법을 이용하여 해를 찾음 - 분할: 배열을 반으로 나누어..
1. 차수의 주요 성질 1) $ g(n) \in O(f(n)) \ if \ and \ only \ if \ f(n) \in \Omega (g(n)) $ if and only if: 필요 충분 조건 $ g(n) \in O(f(n)) $ 이 성립하면, $ f(n) \in \Omega (g(n)) $ 도 성립한다. 2) $ g(n) \in \Theta (f(n)) \ if \ and \ only \ if \ f(n) \in \Theta (g(n)) $ $ g(n) \in \Theta (f(n)) $ 이 성립하면, $ f(n) \in \Theta (g(n)) $ 도 성립한다. 3) b > 1 이고 a > 1 이면, $ log_{a}{b} \in \Theta (log_{b}{n}) $ 은 항상 성립 - 로그 복잡..
1. 정확도(correctness) 분석 - 정확한 알고리즘 -> 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘 - 정확하지 않는 알고리즘 -> 어떠한 입력에 대해서 멈추지 않거나, 틀린 답을 출력하는 알고리즘 2. 차수: 시간 복잡도 함수 ->$ \Theta (lg n)$, $ \Theta (n)$, $\Theta (n lg n) $등 3. 복잡도 함수 표기법 1) $ O() $ : big oh - 점근적 상한(asymptotic upper bound) - $ g(n) \in O(f(n)) $ - $ n \geq N$ 인 모든 정수 n에 대해서 $ 0 \leq g(n) \leq c\times f(n) $ 이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재한다. - $ g(n) $은 $c\t..
1. 알고리즘 분석 => 공간 복잡도 분석, 시간 복잡도 분석 1) 공간 복잡도(space(memory) complexity) 분석 - 입력 크기에 따라서 작업공간(메모리)이 얼마나 필요한 지 분석 2) 시간 복잡도(time complexity) 분석 - 입력 크기에 따라서 단위연산이 몇 번 수행되는 지 분석 ※ 시간 복잡도가 공간복잡도보다 더 알고리즘 분석하는데에 많이 쓰인다. 2. 분석 방법의 종류 1) 모든 경우 분석(every-case analysis) - 입력 크기에만 종속하고 입력값과는 무관하다. - 입력 값과는 무관하게 결과 값은 항상 일정함 ex. n개의 자연수를 단순 더할 때 2) 최악의 경우 분석(worst-case analysis) - 입력 크기와 입력 값 모두에 종속 - 단위연산이 ..
1. 피보나치(Fibonacci) 수열 $$ f_{0} = 0 $$ $$ f_{1} = 1 $$ $$ f_{n} = f_{n-1} + f_{n-2} $$ $$ for\ n\geq2 $$ ex) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... $$ f_{n} = \frac{[\frac{(1+\sqrt{5})}{2}]^{n} - [\frac{(1-\sqrt{5})}{2}]^{n}}{\sqrt{5}} $$ 2. 피보나치 수 구하기 - 재귀적 방법(recursion) - 문제: n번째 피보나치 수를 구하라 - 입력: 양수 n - 출력: n번째 피보나치 수 int fib (int n){ if (n 2\times\ T(n-2) $$ $$ >2^{2}\times\ T(n-4) $$ $$ >2^{3}\..
1. 순차 검색 알고리즘(Sequential Search) - 문제: 크기가 n인 배열 S에 x가 있는가? - 입력(parameter): 양수 n, 배열 S[1..n], 키 x - 출력: x가 S의 어디에 있는지의 위치 (없으면 0) - 알고리즘(자연어): x와 같은 아이템을 찾을 때까지 S에 있는 모든 아이템을 차례로 검사 -> x와 같은 아이템을 찾으면 S에서 위치를 리턴하고 모두 검사해도 찾지못하면 0을 리턴한다. void seqsearch(int n, const keytype S[], keytype x, index& location){ //location: call by reference location = 1; while(location n) // x가 S에 없을 경우 location = 0; ..
