컴공생 일상 블로그 컴공생 일상 블로그

- Disjoint-Sets (서로소 집합들) 교집합이 존재하지 않는 집합 - UnionFind 로 해결 가능한 문제 - 특정 집합에 몇 개의 원소가 속해있는지 - 특정 원소가 같은 집합에 속해있는지 https://www.acmicpc.net/problem/10775 https://www.acmicpc.net/problem/1717 - Union 연산과 Find 연산 1. union(A, B) : B가 A의 밑으로 들어감, A와 B가 같은 조직이됨. find(B) : B의 최상위 부모를 찾음 = A 2. union(C, D) : D가 C의 밑으로 들어감, C와 D가 같은 조직이됨. 3. union(D, B) : B가 D의 밑으로 들어감, - UnionFind의 저장 각 - 코드 구현 #include us..

Subset Sum(부분 합 문제) : 양의 정수들의 배열이 들어 올때, 배열의 부분합으로 일정 수를 만들 수 있으면 TRUE를, 만들 수 없으면 FALSE를 돌려준다. Ex) X = {8, 6, 7, 5, 3, 10, 9} T = 15이면, {8,7}, {5,10}, {6,9}, {7,5,3} > TRUE - Base Cases T = 0 이면, 선택하지않으면 항상 TRUE 이다. T < 0 이면, 항상 FALSE이다. - General Case(점화식) 총합이 T인 부분집합에 대해, 해당 부분집합은 X의 원소 x에 대해 x를 포함하거나, 포함하지않거나의 두가지로 나뉜다. 1. x를 포함할 경우, T-x 인 X-{x}의 부분집합이 존재한다. 2. x를 포함하지 않을 경우, T 인 X-{x}의 부분집합이..

이진 탐색 정렬된 A[0...n-1]의 배열에 대해 k값을 찾을 때, a의 중간값(median)을 k 와 비교하여 같으면 종료. 이진탐색은 실은 분할정복기법이다. 중간값을 k와 비교한 뒤에 배열의 절반에 대해서만 탐색을 계속한다. 즉 문제의 크기가 n/2인 동일한 작은 문제를 해결하다보면, 문제를 해결 할 수 있다. 이진탐색 # A가 정렬된 배열일때 A[a...b]에서 k값을 탐색 int binary_search(A[a...b], k, a, b): if a>b: return -1 mid = (a+b)/2 if A[mid] > k: return binary_search(A, k, a, mid-1) elif A[mid] < k: return binary_search(A, k, mid+1, b) else re..

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보다..

분할 정복 : 말그대로 문제를 분할하여 정복하여 풀이 - 분할 정복의 대표적인 예시 : 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의 예. 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 ..

Algorithm의 수행시간을 이론적으로 분석하기 위한 개념 수행시간은 환경에 따라 달라진다.(구현한 언어, 컴파일러, 컴퓨터의 스펙 등) 즉, 같은 환경적 요인들을 가졌을 때의 수행시간을 비교 아래 3가지에 대한 시간 복잡도를 주로 분석한다. ● Big-Oh Notation 빅오 표기법, 주로 사용하는 표기법이다. 왜 빅오표기법을 주로 사용하는가? - 'A라는 알고리즘이 최선의 경우 1초만에 문제를 해결한다.' 하지만, 최악의 경우 inf의 시간이 걸린다면, 의미가 있다고 할 수 있을까? 이보다는 'A라는 알고리즘은 최악의 경우에도 10초만에 문제를 해결해' 가 더 의미있을 것이다. - 두 함수 간의 관계를 나타내는 표기법 시간복잡도를 나타내는데 주로 쓰이지만, 별개로 함수의 증가속도(growth ra..