본문 바로가기

Library/Algorithm

Heap Sort (이진) 힙 자료 구조는 완전 이진 트리로 볼 수 있는 배열 객체다. 트리의 각 노드는 배열에서 그 노드의 값을 저장하는 원소와 대응한다. 이 트리는 가장 낮은 층을 빼고는 완전히 차 있고, 가장 낮은 층은 왼쪽부터 채운다. 힙을 나타내는 배열 A는 두 가지 인자를 갖는다. 배열 A에 있는 원소의 개수를 나타내는 length[A]와 배열 A의 원소 중 힙에 속하는 원소의 개수를 나타내는 heap-size[A]다. 그리고 heap-size[A] ≤ length[A]다. 다시 말해서 A[1..length[A]]에 있는 값들이 다 유용할 수는 있지만, A[heap-size[A]] 뒤에 있는 것들은 힙의 원소가 아니다. 트리의 루트는 A[1]이다. 그리고 노드의 인덱스 i가 주어지면 부모 Parent(i), 왼.. 더보기
최소 신장 트리(Minimal Spanning Tree) 신장 트리(Minimum Spanning Tree)란, 주어진 그래프에서, 서브 그래프지만 그래프의 모든 정점을 포함하고, 각 정점들은 모두 경로를 가지고 있어야 하지만 모든 경로를 포함하고 있지는 않은 그래프를 말한다.따라서, 신장 트리는 유일하지 않을 수도 있다. 최소 신장 트리란, 이들 경로에 가중치가 주어졌을 때, 경로의 가중치의 합이 가장 작은 트리를 말한다. (트리와 그래프의 차이는, 트리는 사이클이 존재할 수 없으며 그래프는 사이클이 존재할 수 있다는 점이다) 예를 들어, 전자 회로를 설계할 때, 요소 몇 개의 핀을 전선으로 연결해 전기적으로 동등하게 만들어야 하는 경우가 있다. n개의 핀을 서로 연결하기 위해, n - 1개의 전선을 사용할 수 있는데, 여기서 하나의 전선이 2개의 핀을 연결.. 더보기
강한 연결 요소(Stronlgly Connected Components) 강한 연결 요소(Strongly Connected Components)란 무엇인가? 방향 그래프에서, 임의의 두 정점을 선택했을 때 경로가 존재하며, 서로 반사관계(reflexible)라면, Strong Connected 되었다고 한다. Strongly Connected Components란, 어떤 그래프 G에서 Strongly Connected 되어 있는 그래프의 부분집합을 말한다. 방향 그래프 G = (V, E)의 강한 연결 요소는 정점의 집합 C ⊆ V인데, C에 있는 정점들 u와 v의 모든 쌍에 대해 u → v와 v → u 둘 다 존재하는, 다시 말해서 정점 u와 v는 서로 도달 가능하다. 그래프 G = (V, E)의 강한 연결 요소를 찾는 알고리즘은 G의 전치 그래프를 사용하는데, 여기서 G의 .. 더보기
Dynamic Programming 다이나믹 프로그래밍(Dynamic Programming)이란 무엇인가? 이것은 다이나믹 플래닝(Dynamic Planning)이란 개념과 비슷하다고 할 수 있다. 간단히 이야기해서, 실행 시간의 정보를 기록한다는 의미이다. 즉, 중복되는 계산 결과를 기록해서 중복된 계산 결과가 필요한 경우, 최대한 재계산을 피하고자 하는 것이다. 예를 들어서, 피보나치 수열의 경우, n항의 값을 알려주는 함수 fib(n)을 작성한다고 하자. f(n) = f(n - 2) + f(n - 1)이다. f(n)을 알기 위해서는, 앞의 두 항의 값을 알고 있어야 한다. f(5), f(6)을 계산할 때, fib(n)을 재귀호출 방식으로 작성한다면, 같은 항에 대해 연속적으로 재계산을 하게 된다. 만약, f(n)을 어딘가에 저장해두고.. 더보기
Greedy Algorithm Greedy Algorithm 방식에서는, 단계적으로 최선의 것을 선택하더라도, 최종적으로 최적의 해를 얻는 것은 아니다. 최적화 문제란, 소모비용을 최소로 하거나, 최대의 이익을 가져오는 문제를 말한다. 이런 최적화 문제는, 언제나 완전한 최적의 해를 얻을 수 있는 것은 아니다. 최적의 해를 얻는다고 하더라도 필요 이상의 시간이 소모된다면, 이런 경우 최적에 가까운 근사해를 얻는 것이 더 유용할 수 있다. Greedy Algorithm은 많은 경우 좋은 근사해를 얻을 수 있다. Prims' Algorithm이 그런 방식이라고 할 수 있는데, 이 방식은 최소 신장 트리를 만들기 위해서 트리를 키워나가는 방법을 사용하고 있다. Prims' Algorithm 해결 단계는 다음과 같다. step1. 정점 하나.. 더보기
Graph Traversal 그래프 G = (V, E)를 표현하는 표준 방법에는 인접 리스트와 인접 행렬, 두 가지 방법이 있다. 두 가지 모두 방향 및 무방향 그래프에 적용할 수 있다. 하지만 인접 리스트 방법이 희소 그래프에 대해 훨씬 효율적이기 때문에 일반적으로 많이 사용한다. 그리고 희소하다는 것은 ｜E｜ = ｜V｜^2보다 훨씬 작음을 의미한다. 하지만, ｜E｜값이 ｜V｜^2과 거의 비슷한, 조밀한 그래프일 경우, 또는 주어진 두 정점을 연결하는 간선이 있는지를 빠르게 확인할 필요가 있을 때는 인접 행렬 표현법이 더욱 선호되기도 한다. 그래프 탐색 기법은 너비 우선 검색과 깊이 우선 검색이 있다. 너비 우선 검색은, 주어진 그래프 G = (V, E)와 구별되는 출발점(source) s에 대해, 너비 우선 검색은 s로부터 닿을.. 더보기
Radix Sort and Array Doubling 기수정렬에서 가장 중요한 것은, 이미 정렬된 순서를 흐트러트리지 않아야 하는, 안정성(stability)이다. 다시 말해서, 다음 자리를 정렬한다고 할 때, 이미 정렬된 순서대로 꺼내와서 배치해야 한다. 배열을 늘려가는 전략에는 여러가지가 있을 수 있다. 즉, 메모리 할당 전략이 어떤 것이 더 좋은가라는 것으로 바꿔 말할 수 있다. 문자 배열의 메모리를 할당 받는 전략에서는, 지수 형식으로 블럭을 할당하는게 더 효율적일 수 있지만, 이것은 메모리의 적절한 사용량을 생각한 것은 아니다. 다만, 단지 효율적인 시간에 대해서만 생각한 것이다.그렇다면, 한번에 대량의 메모리를 할당받는 것이 RAM이란 기계에서 최선의 할당전략이라고 할 수 있는데, 옳은 이야기인가? 앞서 이야기했던 배열 상황에서는, 줄어들지 않고.. 더보기
Quick Sort and Merge Sort 퀵소트(Quick Sort)의 가장 핵심적인 것은 피벗 엘리먼트(Pivot Element)와 파티션 프로시저(Partition Procedure)이다. 피벗을 선택하고, 피벗 요소가 마지막으로 남을 때까지 계속해서 파티션을 하는 것이 전부이다. Quick Sort의 최악의 경우는 n^2이지만, 평균 수행 시간은 대단히 효율적이다. 퀵소트는 in-place 정렬이 가능한 알고리즘이다. 병합 정렬(Merge Sort)의 대략적인 흐름은 다음과 같다. Mergesort(begin, end) { mergesort(begin, mid) mergesort(mid, end) merge(begin, end) } 따라서, w(n) = w(n / 2) + w(n / 2) + Θ(n) = 2W(n / 2) + Θ(n)이며,.. 더보기
Insertion Sort 입력값이 정렬되어 있는 경우, Dictionary Data Structure를 구현하는데 유용하다. 대표적으로는 Hasing, Lookup Table과 같은 방법을 사용 할 수 있다. 삽입 정렬은, 기본적으로 정렬된 집합의 엔트리를 점차 늘려가는 방식이다. 삽입 정렬의 최악의 경우 Ο(n^2)의 복잡도를 가진다. 그렇다면 평균 수행 시간은 어떻게 되는가? n개의 엔트리를 가지는 배열에서, i 위치에 있는 엔트리가 자기 자신의 위치를 찾는 연산 횟수를 생각해보자. 먼저, 전체 n 개의 엔트리이므로, 이 값이 특정 위치에 존재할 확률은 1/n이다. 그리고, 이 위치에서 소모된 연산 수는 SIGMA(FROM j = 1 TO n - 1)(j)이다. 여기서 생각해봐야 할 것은 i위치까지 왔을 때 결정 할 수 있는.. 더보기
Divide and Conquer 가능한 작게 쪼개서 하나씩 해결하는 방식의 대표적인 형태가 이진 탐색(Binary Search)이다. 특히, 주어진 입력값이 정렬되어 있다면, 이진 탐색은 검색 공간을 반으로 줄여가면서 원하는 값의 범위를 좁혀간다. 이런 알고리즘을 구현하기 위해 재귀(recursive)를 사용할 수도 있고, 반복(Iterate)를 사용할 수도 있다. 이진 탐색 알고리즘의 값의 정확성을 제외하고, 수행 성능을 분석해보자. 수행 성능은 최악의 경우와 평균 수행 시간을 측정하는 것이 일반적이다. 먼저, 최악의 경우를 생각해본다면, 이진 탐색의 경우 최악의 경우라고 하더라도 n의 입력이 들어왔을 때 log(n) 이상의 시간을 소모하지 않는다(Ο(log(n))). 그렇다면 이진 탐색의 평균 수행 시간은 어떻게 측정 할 수 있는가.. 더보기

티스토리툴바