최대 힙 (Heap) 이란? 최대 힙 (Max Heap) 은 아래 그림과 같이, 부모의 값이 자식의 값보다 항상 큰 자료구조이다. 항상 루트에 최대 값을 가지기 때문에, 이를 이용해서 우선순위 큐 (Priority Queue) 를 구현할 수 있다. 최대 힙의 시간 복잡도는 삽입 (Push) 할 때 O (log N), 삭제 (Pop) 할 때 O (log N) 이므로, 굉장히 합리적인 자료구조임을 알 수 있다. * 참고로 위의 그림에서 루트가 최소가 되는 구조라면 최소 힙 (Min Heap) 이 된다. 동작 원리 최대 힙은 배열을 통해서 구현한다. 위의 최대 힙을 배열로 나타내면 다음과 같다. 이 그림에서 알 수 있듯이, 배열을 통해서 구현하면 다음의 사실을 이용할 수 있다. - 부모의 인덱스 * 2 = 왼..

Convex Hull 이란? Convex Hull은 우리말로 번역하면 '볼록외피' 라는 뜻입니다. 말로는 잘 이해되지 않으니, 다음 그림을 보며 설명드리겠습니다. 7개의 노드가 있습니다. 여기에서, 가장 바깥의 노드들로만 전체를 감싸면, 그것이 Convex Hull이 됩니다. 아래와 같이 말이죠. 이러한 Convex Hull을 구하는 알고리즘은 여러가지 종류가 있습니다. Graham's Scan, Andrew Algorithm 등이 있는데, 오늘 여기에서는 Graham's Scan 알고리즘에 대해서 알아보겠습니다. 동작 원리 Convex Hull을 구현하기에 앞서, 계산기하학에서 자주 사용되는 CCW (Counter Clock Wise) 라는 용어에 대해 이해할 필요가 있습니다. 우리는 3개의 노드가 있..

퀵 정렬 (Quick Sort)이란? 이름부터가 퀵 정렬 (Quick Sort) 입니다. 빠르다는거겠죠? 맞습니다. 일반적인 상황에서 빠른 정렬 시간을 보장해준다고 합니다. 버블정렬, 삽입정렬, 선택정렬 등은 O(N²) 의 시간을 가지지만, 퀵 정렬은 평균적인 상황에서 O(N * log N) 의 시간을 가집니다. 그러므로 빠른 정렬이라고 할 수 있겠죠. 최악의 경우에서는 O(N²) 의 시간복잡도를 가집니다. 이 경우는 이미 정렬이 완료되어있는 경우로, 이런 경우에는 합병정렬을 사용하는 것을 고려해볼 수 있습니다. 동작 원리 아래와 같은 배열이 있다고 가정해보겠습니다. 퀵 정렬을 사용하기 위해서는 피벗 (Pivot) 이라는 기준점을 잡아주어야 합니다. 즉, 피벗을 기준으로 작은 것과 큰 것을 구분해서 정렬..

합병정렬이란? 퀵정렬 (Quick Sort) 와 함께 대표적으로 사용되는 빠른 정렬 알고리즘입니다. 얼마나 빠르냐구요? 퀵정렬과 동일하게 O(N * log N) 입니다. 물론 완전히 동일한 시간이 걸린다는 것은 아닙니다. 퀵정렬은 최악의 경우 (이미 정렬되어있는 경우) 에서는 O(N²) 까지 걸릴 수 있거든요. 하지만 합병정렬은 나누고 병합하는 과정에서 O(N * log N)이 거의 보장됩니다. 그러므로, 특정한 경우에서는 퀵정렬 대신 병합정렬을 사용하기도 합니다. 동작 원리 다음과 같은 배열이 있다고 가정해볼게요. 우리는 병합정렬을 하기 위해서, 크게는 아래 그림과 같은 과정을 거칠 것입니다. 그림에서 보시는 것처럼, 합병정렬은 크게 3가지의 과정을 가집니다. (1) 분할 - N 길이의의 배열을 N /..

플로이드-와샬 알고리즘이란? 다익스트라, 벨만포드 알고리즘과 더불어 대표적인 최단거리 찾기 알고리즘이다. 플로이드-와샬 알고리즘은 그 중에서도 모든 정점끼리의 최단거리를 한번에 계산할 때 사용한다. 즉, 다익스트라 알고리즘은 어떤 정점 A에서 다른 정점들까지의 최단거리를 계산한다면, 플로이드-와샬 알고리즘은 전체 정점에서 다른 정점들까지의 최단거리를 한번에 계산한다는 것이다. 다익스트라 알고리즘은 특정 정점을 중심으로 식을 계산시켜 나간다면, 플로이드-와샬 알고리즘은 계산을 위해 거쳐가는 정점을 중심으로 계산해나간다는 것이다. 또한, 플로이드-와샬 알고리즘의 중요한 특징 중 하나는 동적 계획법을 이용하여 최단 거리를 계산해나간다는 것이다. 동작 원리 위와 같은 초기 상황이 주어졌다고 가정하자. 일반적인 ..

기수정렬이란? 기수정렬은 영어로 'Radix Sort' 이다. 여기에서 'Radix'가 의미하는 바는 각 자리를 이루고 있는 숫자들을 말한다. 즉, 각각의 수의 자릿수를 대상으로 정렬한다는 것이다. 기수정렬을 다른 정렬들(버블정렬, 퀵정렬 등) 과는 다른 특성이 있다. 첫 번째는 비교가 이루어지지 않는 정렬이라는 것이고, 두 번째는 정렬의 이론상 한계인 O(N * log N)을 뛰어넘는 O(N)이라는 것이다. 이렇게만 보면 어떤 정렬보다 좋을 것 같지만 실제로는 생각보다 많이 쓰이지않는데, 이는 적용 범위가 한정적이기 때문이다. 반대로 말하면, 최적의 상황에서 사용하면 최적의 효율을 보여준다는 것이기도 하다. (실제로, 알고리즘 풀이 중에서는 쓰이는 경우가 간간히 있다.) 동작 원리 다음과 같은 배열을 ..