합병정렬이란? 퀵정렬 (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)이라는 것이다. 이렇게만 보면 어떤 정렬보다 좋을 것 같지만 실제로는 생각보다 많이 쓰이지않는데, 이는 적용 범위가 한정적이기 때문이다. 반대로 말하면, 최적의 상황에서 사용하면 최적의 효율을 보여준다는 것이기도 하다. (실제로, 알고리즘 풀이 중에서는 쓰이는 경우가 간간히 있다.) 동작 원리 다음과 같은 배열을 ..

원형 큐를 사용하는 이유 자료구조를 배우셨다면 큐 (Queue) 에 대해서 배우셨을 겁니다. 선입선출 (FIFO) 의 구조를 가지기 때문에, 수많은 알고리즘에서 큐가 사용됩니다. 만약 큐를 배열에 저장한다면 다음과 같은 상황이 만들어집니다. 이 상황은 어떤 상황일까요? 현재 큐에는 7, 5 라는 값이 들어있고, 출력 시 순서대로 7, 5 이 출력됨을 아실겁니다. (만약 이 부분이 이해가지 않는다면, 큐를 공부하시면 되겠습니다.) 이 상황에서, 인덱스가 0인 공간을 활용하려면 어떻게 해야 할까요? 물론 배열의 모든 원소들을 앞당겨줄수도 있지만, 비용상의 문제로 이러한 작업은 비효율적입니다. 즉, 앞당김 작업없이 지속적인 큐의 사용을 위해서 우리는 원형 큐를 사용해야 합니다. 동작 원리 큐를 이해하고 있다면..

계수정렬 (Counting Sort) 이란? 굉장히 빠른 속도를 자랑하는 정렬 (Sort) 이다. 배열에 들어있는 원소의 최대값을 k 라고 가정하면 O(k + n) 의 시간복잡도로 정렬할 수 있다. 그러므로 최선의 경우에서는 퀵정렬보다도 빠르다. 하지만 k 값이 클 경우, 예를 들어서 배열 내의 원소의 최대값이 매우 큰 숫자일 경우 비효율적인 알고리즘이다. 그러므로 배열 내의 원소의 값이 간단한 경우 (예, 1~2자리의 숫자) 에 효율적인 알고리즘이다. 실행 과정 계수정렬은 배열 내에 속해있는 모든 원소를 인덱스로 가지는 배열을 생성한다. 그리고, 각각의 인덱스에 배열 내의 원소가 몇번 들어가는지 계산한다. 아래와 같은 정렬하기 원하는 배열이 있다고 가정하자. 배열 내의 각 원소가 몇번 나오는지 계산하기..

문제 해설 나에게 엄청난 좌절을 안겨준 문제이다. 처음 문제를 훑어보았을 때는 1시간이면 풀 수 있을 것이라고 착각했지만, 내 구현 능력이 아직 많이 부족하다는 것을 여실히 보여주었다. 장장 이틀에 걸친 삽질을 통해 풀 수 있었던 문제이다. 앞으로도 열심히 공부해야겠다는 자극을 받았다. 어쨌든, 이 문제는 이해를 바탕으로 구현하는 시뮬레이션 문제이다. 다만, 조건이 조금 까다롭기 때문에 적절한 분기 처리를 해주어야 테스트 케이스를 모두 통과할 수 있다. 나의 경우도 이 조건, 저 조건을 따지다가 시간을 모두 날려먹은 케이스이다. 어쨌든, 내가 풀었던 문제 풀이에 대해서 설명해보겠다. 다음과 같이 3, 2, 2, 1, 1, 1, 1, 2, 2, 3 의 높이를 가진 길과 길이 2의 경사로를 생각해보자. 왼쪽..