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

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

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

트라이 (Trie) 자료구조란? 문자열 검색에 최적화된 트리 형태의 자료구조이다. 상위 문자가 하위 문자들의 부모 노드가 되는 트리 구조를 가지고 있다. 'tree', 'trie', 'trim' 이렇게 3개의 문자열을 포함하는 트라이의 예시를 보자. 그림에서 보는 것과 같이, 't' 밑에 'r' 이 하위 노드로 들어가 있고, 'r' 밑에 'i' 와 'e' 가 하위 노드로 들어가 있는 것을 볼 수 있다. 이와 같은 구조를 가지고 있기 때문에, 길이 m의 특정 문자열이 존재하는지 판단하는 것이 O(m) 시간으로 가능하다. 트라이에 필요한 기능 트리 구조에 익숙한 분들이라면 위의 그림만으로도 구현의 방법이 그려졌을 것이다. 트라이의 구현에서는 다음과 같은 기능이 필요하다. (1) 해당 단어가 존재하는지 판단하..

유클리드 호제법 (Euclidean Algorithm) 이란? 두 개의 자연수의 최대공약수(GCD) 를 빠르게 찾는 알고리즘이다. 유클리드 호제법이 유명한 또 다른 이유는, 이 방법이 인류 최초의 알고리즘이라고 소개되고 있기 때문이다. 최대공약수를 찾는 알고리즘은 여러가지가 있겠지만, 시간복잡도 면에서 가장 훌륭한 알고리즘이기 때문에 PS 과정에서 필요하다면 적극 활용하는 것을 추천한다. 계산 과정 유클리드 호제법은 매우 단순하다. 자연수 A, B가 있다고 가정하고, 다음과 같은 과정을 반복하기만 하면 된다. (1) A를 B로 모듈러 연산한다. (A % B) (2) 만약 나머지가 0이라면, B가 최대 공약수이다. (3) 만약 나머지가 0이 아니라면, A를 B로 바꾸고, B를 나머지로 바꾼다. 만약 A =..

코딩테스트 문제 중, 가끔 수학적인 기초를 묻는 문제에 약수, 배수 등의 문제가 출제된다. 이러한 유형의 문제를 접해본 경험이 없는 사람들은 최악의 시간복잡도를 갖는, 모든 경우를 찾는 순차적인 알고리즘으로 문제를 풀게 된다. 그러므로 PS를 준비하는 사람이라면 '모든 약수를 찾는 효율적인 알고리즘' 정도는 익혀두는 것이 좋다. 가장 단순하게 약수를 찾는 알고리즘 가장 단순한, 누구나 쉽게 생각할 수 있는 방법을 고안해보자. 만약 10의 약수를 찾는다고 했을 때, 1~10까지의 수 중에서, 10을 0으로 나누어 떨어지게 하는 수를 찾는 알고리즘을 생각할 수 있을 것이다. 10 % 1 = 0 10 % 2 = 0 10 % 3 = 1 10 % 4 = 2 10 % 5 = 0 10 % 6 = 4 10 % 7 = ..