알고리즘/Algorithm Theory
-
[Master Theorem] 마스터 이론(정리)알고리즘/Algorithm Theory 2022. 6. 20. 23:32
1. 일반적인 마스터 정리 T(n) = rT(n/c) + O(f(n))을 만족 하는 경우 3가지의 경우로 복잡도를 구할 수 있다. 2. 등차수열의 경우, T(n-2) + T(2) + O(n)과 같은 경우 3. 마스터정리를 만족하지 않는 경우, recursion tree를 그려서 복잡도를 구하는 경우 3_1. 만약 트리의 각 층의 너비가 같은 경우 : 트리의 높이 * 너비 3_2. 만약 트리의 너비가 작아질 경우 : 등비가 1보다 작은 등비수열의 합으로 표현가능, 즉 특정 상수에 수렴한다. 3_3. 만약 트리의 너비가 커질 경우 : 트리의 잎의 개수, (나누어지는 자식노드의 개수)^트리의 높이 3_2와 3_3의 예제. (algorithms-Jeff 49p 7번 의 (k), (l)) K(n). 공비가 1보다..
-
[Divide-and-Conquer] 분할정복알고리즘/Algorithm Theory 2022. 6. 20. 22:49
분할 정복 : 말그대로 문제를 분할하여 정복하여 풀이 - 분할 정복의 대표적인 예시 : Merge Sort 병합정렬 1. 주어진 배열을 두 부분으로 나눈다. 2. 두 부분배열을 각각 Mergesort한다. 3. 정렬된 부분배열을 합쳐서(merge) 하나의 정렬된 배열로 만든다. MergeSort(A[1...n]): if n > 1: m = [n/2] MergeSort(A[1...m]) MergeSort(A[m+1...n]) Merge(A[1...n], m) - Divide and Conqur의 설계 1. 문제를 동일한 작은 문제들로 나누어라 2. 각각의 작은 문제들을 재귀요정에게 맡겨라(일단 같은 작은 문제들을 던져주면 알아서 해결해준다.) 3. 최종 해결법은 작은 문제들에 대한 답을 결합해라. * 어떤..
-
[Recursion] 재귀 with Hanoi Tower알고리즘/Algorithm Theory 2022. 6. 17. 04:29
재귀.!, 알고리즘의 이해와 설계에 매우 중요한 기술 Recursion의 예. 1. 팩토리얼 연산 2. 자연수의 정의 - 1은 자연수이다. (Base case) - n이 자연수이면, n보다 1큰수도 자연수이다. Reduction (= 축소) 어떤 문제X에 대해 Y로 축소해라. X라는 문제를 풀기위해, Y를 푸는 함수를 호출한다. 이때 Y를 어떻게 풀것인지는 신경쓰지않는다. 이때, Y를 푸는 함수는 어떻게 작동하는지는 모르지만(신경x), 항상 옳게 Y를 풀어낸다. Example - 배열 A[0...n-1]에서 최소값 찾기 1. A를 정렬한다. 2. return A[0] - Selction(A[0...n-1], k) 배열 A[0...n-1]에서 k번째로 작은 값 찾기 1. A를 정렬한다. 2. return ..
-
[Time Complexity] 시간 복잡도알고리즘/Algorithm Theory 2022. 6. 17. 02:46
Algorithm의 수행시간을 이론적으로 분석하기 위한 개념 수행시간은 환경에 따라 달라진다.(구현한 언어, 컴파일러, 컴퓨터의 스펙 등) 즉, 같은 환경적 요인들을 가졌을 때의 수행시간을 비교 아래 3가지에 대한 시간 복잡도를 주로 분석한다. ● Big-Oh Notation 빅오 표기법, 주로 사용하는 표기법이다. 왜 빅오표기법을 주로 사용하는가? - 'A라는 알고리즘이 최선의 경우 1초만에 문제를 해결한다.' 하지만, 최악의 경우 inf의 시간이 걸린다면, 의미가 있다고 할 수 있을까? 이보다는 'A라는 알고리즘은 최악의 경우에도 10초만에 문제를 해결해' 가 더 의미있을 것이다. - 두 함수 간의 관계를 나타내는 표기법 시간복잡도를 나타내는데 주로 쓰이지만, 별개로 함수의 증가속도(growth ra..