기록하는 습관 "기습"

동적 프로그래밍 큰 문제에는 닮은 꼴의 작은 문제가 깃들기도 한다. 이를 해결한 것이 재귀적 알고리즘인데, 이 알고리즘은 잘 쓰면 효율적인 보약이지만 잘못 쓰면 치명적인 맹독이다. 재귀적 알고리즘 자체가 심한 중복 호출을 불러올 수 있기 때문이다. 이를 해결하기 위한 방법이 동적 프로그래밍이다. 심한 중복 호출이 일어나는 경우는 피보나치 수열과 행렬곱셈 최적순서 구하기가 있다. 이에 대해 알아보자. 피보나치 수 구하기 피보나치 수열의 정의는 다음과 같다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 이를 프로그램으로 구현하면 fib(n) { if (n = 1 or n = 2) then return 1; else return (fib(n-1) +fib(n-2)); } 여기서 수가 ..

집합의 처리 여기서 다루는 집합은 상호배타적 집합 disjoint set뿐이므로 교집합 연산은 다루지 않는다. 상호배타적 집합을 다루기 위해 필요한 연산은 다음과 같다. makeSet(x) : 원소 x로만 이뤄진 집합을 생성한다. findSet(x) : 원소 x가 속한 집합을 알아낸다. union(x, y) : x와 y가 속한 집합의 합집합을 구한다. 집합의 연산은 위와 같다. 다음은 위 집합의 처리를 할 때 가장 근본적으로 고려해야 할 집합의 구현방법이다. 연결리스트로 구현 : makeSet, findSet은 O(1), union은 O(log n)이 소요된다. tree로 구현 : makeSet, findSet, union에서 O(m)의 시간이 소요된다. 가장 효율적이다. 연결리스트로 집합 처리 각 원소..

해시테이블  지금까지 트리 자료구조는 대부분은 다른 원소와 비교하여 저장할 위치를 찾아갔다. 그러나 해시테이블은, 원소를 저장할 위치가 그 원소 값에 의해 결정되는 자료구조다. 해시테이블의 특징은 다음과 같다. 저장/검색/삭제에 있어서 상수에 가까운 수행시간을 갖는다. = > Θ(1)최소 원소 찾기 같은 연산은 지원하지 않는다. 지금부터 위의 그림을 예시로 해시테이블에 대해 설명하겠다.위와 같은 해시테이블의 크기 m을 7이라 하자. 그렇다면 테이블은 0~6까지의 인덱스를 갖는다. 해시함수 Hash function원소를 저장할 때, 가운데 해시함수 hash function를 거쳐서 적절한 위치에 저장된다. 따라서 해시함수는 검색 키 값을 해시 테이블주소로 매핑하는 함수라는 의미다.  해시함수는 입력원소가 ..

B-Tree 검색트리가 방대하면 모두 메모리에 올려놓고 사용할 수 없다. 따라서 디스크에 넣어둔 상태로 작업해야 한다. 이는, 외부 검색트리에 해당한다. 외부검색트리일 땐 CPU보다는 디스크 접근 횟수가 효율을 좌우한다. 그리고 트리의 높이를 최소화하는 것이 유리하다. 이는 분기수를 늘리면 다진 검색트리가 되고 높이도 줄어든다. 10억 개의 키값을 가진 이진검색트리는 높이가 30이다. 256개의 분기를 가진 트리는 5의 높이를 갖는다. 이러한 분기는 블럭의 크기를 고려하여 결정한다. B-Tree는 결국 트리 균형을 유지하여 최악의 경우 디스크 접근 횟수를 줄인다. 또한, 다진검색트리로써 다음과 같은 특성을 갖는다. 루트노드를 제외한 모든 노드에서 [k/2]~k개의 키를 갖는다. 모든 리프 노드는 똑같은 ..

레드블랙트리 Red-Black Tree 이전 이진검색트리에서, 평균 수행시간이 O(log n)이라 했다. 그러나 트리의 균형이 나쁘다면 최악의 경우 n에 비례한 시간이 걸린다. 이를 보완하기 위한 '균형 잡힌 이진트리'가 바로 레드블랙트리다. 이진검색트리에 몇 가지 조건을 추가해서 균형 잡힌 트리가 되도록 한다. 트리의 높이, 검색/삽입/삭제 연산이 모두 O(log n)의 시간이 걸린다. 레드블랙트리는 모든 노드에 빨강 혹은 검정을 칠하되 다음과 같은 특성을 만족해야 한다. 루트는 블랙이다. 모든 리프(NIL, Null값과 같다)는 블랙이다. 노드가 레드면 그 노드의 자식은 반드시 블랙이다. 루트 노드에서 임의의 리프노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. 참고로 레드블랙트리의 리프노..

검색트리 데이터의 저장과 검색은 자료구조와 알고리즘 분야에서 매우 중요하다. 수행시간에서 커다란 차이를 보이기 때문이다. 데이터의 저장과 검색을 효율적으로 하기 위해서는 적절한 자료구조 및 알고리즘의 사용을 필요로 한다는 사실은 자명하다. 만약 데이터가 들어오는 순서대로 배열에 저장한다고 가정해보자. 자료수가 n개일 때 수행시간은 다음과 같다. 새로운 자료 하나를 저장하는 시간은 Θ(1) 자료를 검색하는 시간은 Θ(n) 보다시피 검색에는 비효율적이다. 허나, 트리 모양 구조의 검색 트리에 저장한다면 어떨까? 저장과 검색, 둘 모두 Θ(log n)의 시간이 걸린다. 검색트리는 자식노드 갯수에 따라, 저장장소에 따라, 검색키에 포함된 필드수에 따라 분류된다. 다만 여기서는 언급하지 않겠다. 이진 검색트리 이..

선택 알고리즘 Selection algorithm 눈 앞에서 각각 숫자가 놓여 있다. 1, 3, 5, 6, 7 ... 여기서 만약 3번째로 큰 원소를 찾아야 한다. 여기서 보통 O(n log n) 시간이 걸리는 정렬 알고리즘을 사용하여 정렬해놓고 위치를 찾을 수 있다. 하지만, 더 빠르게 찾을 수도 있다. 더욱 n에 비례하는 시간에 근접할 수 있는 알고리즘이 선택 알고리즘 selection algorithm이다. 선택 알고리즘에는 두 가지 유형이 있다. 평균적으로 선형시간(n에 비례한 시간)이 소요되는 선택 알고리즘을 말한다. (select라 보통 표현한다.) '최악'의 경우에도 선형시간이 보장되는 선택 알고리즘이다. (linearselect라 보통 표현한다.) 여기서는 일반적인 선택 알고리즘을 먼저 설..

특수 정렬 지금까지 봐온 정렬들은 모두 원소끼리 비교해서 정렬하는 비교 정렬 comparison sort이었다. 이 비교 정렬은 최악의 경우, 아무리 빨라도 수행시간이 Θ(nlogn)이다. Ω(nlogn)이라고도 할 수 있다. 다시 말해, '하한'이 존재한다. 그러나 원소들이 특수한 성질을 만족하면 다른 기법으로 O(n) 정렬이 가능하다. 계수 정렬 Counting Sort 기수 정렬 Radix Sort 계수 정렬 counting sort 원소들의 값이 모두 O(n) 범위에 있을 때 사용가능하다. 또는 -O(n)~O(n) 범위에 있을 때도 가능하다. 이를 전제로 하는 과정은 다음과 같다. 배열 A[1~n]의 원소들이 k(상수)를 넘지 않는 자연수인 경우, 배열에서 1에서 k까지 자연수가 몇 번씩 나타나는..

고급 정렬 고급 정렬들은 평균 수행시간이 Θ(nlogn)이다. 이 중에 퀵 정렬이 가장 많이 사용된다. 병합 정렬 merge sort 정렬할 대상을 반으로 나누고, 반으로 나눈 전반부와 후반부를 독립적으로 정렬한다. 정렬된 두 부분을 합치면서 정렬된 배열을 얻는다. 병합정렬 또한 재귀알고리즘이다. 수행시간은 두 부분을 각각 정렬하는 시간과 병합시간을 합하면 된다. 점화식으로 표현하면 다음과 같다. T(n) = 2T(n /2) + Θ(n) 마스터정리를 이용한 점근적 표기로는, a=2, b=2 f(n)=n h(n)=nlog2 =n 따라서, h(n)이 더 크므로 T(n)=Θ(nlogn) 병합 정렬을 자바 코드로 구현해보자. public class MergeSort { public static void sort..

정렬 알고리즘 정렬이란, n의 개의 원소를 기준에 따라 순서대로 배열하는 것을 의미한다. 정렬 알고리즘의 수행시간은 대부분 O(nlogn)~O(n²)을 지닌다. 다만, 정렬하고자 하는 값이 특수한 성질을 만족하면 O(n) 수행시간도 가능하다. 정렬 알고리즘 분류 기본적인 정렬 -평균 θ(n²) 선택 정렬 selection sort 버블 정렬 bubble sort 삽입 정렬 insert sort 고급 정렬 - 평균θ(nlogn) 병합정렬 merge sort 퀵 정렬 quick sort 힙 정렬 heap sort 특수 정렬 - 평균 θ(n) 계수 정렬 기수 정렬 기본적인 정렬 알고리즘 단어 그대로 기본적이며 간단히 구현 가능한 알고리즘이다. 계수가 작을 때는 타 알고리즘에 비해 더 빠른 결과를 얻을 수도 있..