본문 바로가기

전체 글

 (97)
[알고리즘] 병합 정렬(Merge Sort) - 코딩밥상 병합 정렬(Merge Sort)이란? 병합 정렬은 앞서 배운 퀵 정렬과 같이 분할 정복에 기반한 알고리즘으로 성능도 퀵 정렬만큼 우수합니다. 이는 직역한 그대로 '나누고 조건에 맞게 합치는' 알고리즘입니다. 간략하게 동작 방식을 정리하자면, 정렬할 데이터를 반으로 나눈다 나뉜 하위 데이터의 크기가 2 이상이면 이 하위 데이터에 대해 첫번째 과정(반으로 나눔)을 반복한다 동일 데이터에서 나뉜 하위 데이터 둘을 병합하여 원래대로 하나의 데이터로 만든다. 단, 병합할 때 데이터의 원소는 정렬 기준에 따라 정렬한다 데이터가 원래대로 모두 하나가 될 때까지 세번째 과정(병합)을 반복한다. 이 병합 정렬을 구현할 때 두 하위 데이터를 병합하는 부분에 관심을 더욱 기울여야 합니다. 병합하는 과정이 성능을 좌우하기 때..
[알고리즘] 보이어-무어(Boyer-Moore) 알고리즘 - 코딩밥상 보이어-무어(Boyer-Moore) 알고리즘이란? 보이어-무어 알고리즘은 독특하게도 문자열을 오른쪽에서 왼쪽으로 비교해나갑니다. 하지만 '이동'만큼은 왼쪽에서 오른쪽을 이루어집니다. 패턴의 오른쪽 끝에 있는 문자와 본문의 문자가 불일치하고 그 본문의 문자가 패턴 내에 존재하지 않는 경우 이동 거리는 무려 패턴의 길이와 같습니다. 우리가 사용하고 있는 대부분의 프로그램의 문자열 탐색 기능은 이 알고리즘을 사용하고있습니다. 보이어-무어 알고리즘에는 크게 두 종류의 이동이 있습니다. 나쁜 문자 이동(Bad Character Shift)과 착한 접미부 이동(Good Suffix Shift)이 그것입니다. 완전히 반대 개념인 것처럼 이름이 붙여졌즈만, 이 둘의 목적은 같습니다. 불일치가 발생한 경우 최대의 효율로..
[알고리즘] KMP(Knuth-Morris-Pratt) 알고리즘 - 코딩밥상 KMP(Knuth-Morris-Pratt) 알고리즘이란? KMP 알고리즘은 '부르트 포스'처럼 탐색 위치를 본문 왼쪽부터 시작해서 오른쪽으로 옮겨가며 문자를 직접 비교하는 방식으로 작동합니다. 하지만 처음부터 끝까지 하나하나 모든 경우의 수를 다루는 부르트 포스 탐색과 달리 KMP 알고리즘은 비교할 필요 없는 부분은 지나치고 비교가 필요한 부분만 비교를 수행하는데에 차이점이 있습니다. 패턴과 본문 내 문자열을 한 차례 비교하고 나면, 다음 단계 탐색에서 사용할 수 있는 '정보'가 남으며 이 정보를 이용하면 불필요한 비교를 피할 수 있습니다. KMP 알고리즘은 이 '정보'가 무엇인지와 이 정보를 '어떻게 활용하는가'에 대한 것입니다. KMP 알고리즘의 동작 방식 어느 문자열이든 접두부(Prefix/문자열의..
[알고리즘] 카프-라빈(Karp-Rabin) 알고리즘 - 코딩밥상 카프-라빈(Karp-Rabin) 알고리즘이란? 카프-라빈 알고리즘은 문자열 탐색을 위해 해시 함수를 이용합니다. 패턴 내의 문자들을 일일이 비교하는 대신 패턴의 해시값과 본문 내의 있는 하위 문자열의 해시값만 비교하는 방식입니다. 해시 함수를 다음과 같이 임의로 정의해보겠습니다. 문득 여기서 궁금점은 각 패턴 문자열마다 해시값을 부여하면 문자열의 각 요소에 일일이 접근하여 곱셈연산을 하고 덧셈까지 하는 '비용'이 추가적으로 발생하기때문에 오히려 부르트 포스 알고리즘이 유리해 보입니다. 하지만 여기서 해시 함수의 비용을 획기적으로 줄이는 방법이 추가됩니다. 앞 단계에서 계산된 해시함수 값으로 다음 단계의 해시값을 간추리는 것입니다. 이렇게 되면 원래의 해시 함수로는 비교할 때마다 매번 패턴 길이 M 만큼 ..
[알고리즘] 부르트 포스(Brute-Force) 알고리즘 - 코딩밥상 부르트 포스(Brute-Force)란? 부르트 포스란 일차원적으로 앞에서부터 끝까지 차근차근 탐색하는 알고리즘입니다. 즉 모든 경우의 수를 모두 따지는 것입니다. 이 알고리즘은 마치 요령 부리지 않고 우직하게 일하는 일꾼처럼 동작합니다. 따라서 고지식한 탐색이라고도 합니다. 이를 문자열 탐색에 사용한다면, 본문의 길이를 M, 패턴 길이를 N이라고 했을 때 본문 속에 있는 패턴을 찾기 위해 최악의 경우 N*M번의 비교를 수행합니다. 구현 int BruteForce(char* Text, int TextSize, int Start, char* Pattern, int PatternSize){ for(int i=Start; i
[알고리즘] 최단 경로 탐색(데이크스트라 알고리즘) - 코딩밥상 데이크스트라(Dijkstra) 알고리즘이란? 최단 경로 탐색이란 그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최솟값인 경로를 찾는 알고리즘입니다. 그 중 대표적인 알고리즘으로 데이크스트라 알고리즘이 있습니다. 이는 프림 알고리즘과 동작 방식이 상당히 비슷합니다. 다만 프림 알고리즘이 단순히 간선의 길이를 이용하여 어떤 간선을 먼저 연결할지 결정하는 데 비해 데이크스트라 알고리즘은 경로의 길이를 감안해서 간선을 연결한다는 점이 다릅니다. 또 다른 중요한 차이점은 데이크스트라 알고리즘의 경우 사이클이 없는 방향성 그래프에 한해서만 사용할 수 있다는 것입니다. 간단하게 데이크스트라 알고리즘에대해 정리하자면, 각 정점에는 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 각 정..
[알고리즘] 최소 신장 트리 알고리즘(Minimum Spanning Tree Algorithm) - 코딩밥상 최소 신장 트리(Minimum Spanning Tree)란? 각 간선 마다 가중치(Weight)를 갖는다면 표현할 수 있는 요소가 훨씬 다양해집니다. 신장 트리(Spanning Tree)의 'Spanning'의 뜻은 '떨어져 있는 둘 사이를 다리 등으로 연결한다'라는 뜻입니다. 즉, 신장 트리는 그래프의 모든 정점을 연결하는 트리입니다. 최소 신장 트리(Minimum Spanning Tree)란 여러 간선 중 가중치의 합이 최소가 되는 간선만 남긴 신장 트리입니다. 따라서 최소 가중치 신장 트리(Minimum Weight Spanning Tree)라고도 부릅니다. 이러한 특징을 가지는 최소 신장 트리를 만드는 알고리즘에는 대표적으로 프림(Prim)과 크루스칼(Kruskal)알고리즘이 있습니다. 먼저 프림..
[알고리즘] 위상 정렬(Topological Sort) - 코딩밥상 위상 정렬(Topological Sort)이란? '위상'이란 '어떤 정점이 다른 정점과의 관계 속에서 가지는 위치'라는 의미입니다. 이는 그래프 내 서로 인접한 정점 사이의 관계에 '위치'라는 속성이 존재한다는 뜻입니다. 이 위치는 간선 방향에 의해 결정됩니다. 간선을 뻗어내는 정점이 앞이 되고, 간선을 받는 정점이 뒤가 됩니다. 이 앞/뒤 또는 위/아래 관계를 차근차근 정렬하는 작업이 바로 위상 정렬입니다. 그런데 모든 그래프에 대해 위상 정렬을 할 수 있는 것은 아닙니다. 위상 정렬을 하기 위해선 몇가지 조건이 있습니다. 첫째로 그래프에 방향성이 있어야 하고, 둘째로 그래프 내에 사이클이 없어야 합니다. 이러한 조건을 만족하는 그래프를 DAG(Directed Acyclic Graph)라고 합니다. 정..

티스토리툴바