algorithm/theory

문자열 매칭 알고리즘(KMP)

문자열 매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘이다. 워드파일 또는 웹 브라우저 DB에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. 단순 문자열 알고리즘 가장 간단한 문자열 매칭 알고리즘으로, 말 그대로 하나씩 확인하는 방법을 사용한다. 검색할 문자열 ABDEGH 찾는 문자열 DE 가장 앞부분부터 찾는 문자열이 매칭될 때 까지 탐색을 시작한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어지지 않았다면 한 칸씩 옆으로 이동시킨다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어졌으면 탐색을 종료한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 이 알고리즘은 이중포문으로 시간복잡도..

[알고리즘] 위상 정렬 Topological Sort

위상 정렬(Topological Sort) 위상 정렬이란 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 알고리즘이다. 위상 정렬(Topological Sort)의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. 위상 정렬(Topological Sort)을 이용한 기본적인 해결 방법 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을..

Kruskal 알고리즘

Kruskal 알고리즘 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것 탐욕적인 방법 결결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다. 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. MST(최소 비용 신장 트리) 가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다. Kruskal 알고리즘 동작 그래프의 간선들을 ..

Prim 알고리즘

프림 알고리즘(Prim's Algorithm)이란? 최소 신장 트리(Minimum Spanning Tree) 구현에 사용되는 알고리즘으로 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법이다. 프림 알고리즘의 동작 프림 알고리즘은 매 순간 최선의 조건을 선택하는 그리디 알고리즘을 바탕에 둔다. 즉, 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택한다. 시작 단계는 시작 노드만이 MST 집합에 속한다. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점에 대해 간선과 정점을 MST 트리 집합에 넣는다. (사이클을 막기 위해 연결된 정점이 이미 트리가 속한다면 그 다음 순서를 넣는다.) 2번 과정을 MST 집합의 원소 개수..

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리의 필요성 탐색은 프로그램에서 가장 시간이 많이 걸리는 연산 중 하나이기에 효율적인 탐색을 구현하는 것은 굉장히 중요하다. 앞서 살펴본 스택, 큐, 배열, 리스트 구조는 모두 선형적인 구조를 갖고 있다. 선형적인 구조는 탐색 연산시 일일이 순차적으로 접근하여 데이터를 찾는 방식으로 탐색을 진행해야 하기에 탐색에 비효율적이다. 다음과 같이 배열과 연결리스트 모두 앞에서부터 순차적으로 탐색해야 값을 찾을 수 있고 최악의 경우 해당 값이 맨 마지막에 있다면 O(n)의 시간복잡도를 갖는다. 이러한 선형적인 구조의 탐색 비효율성은 데이터의 크기가 증가할수록 선형적으로 증가한다. 이러한 선형구조가 갖는 탐색의 비효율성을 개선한 것이 바로 이진 탐색 트리(Binary Search Tree)이다. 배열을..

벨만-포트 알고리즘

벨만-포드 알고리즘 벨만-포드 알고리즘은 최단 경로를 찾는 대표적인 기법 중 하나이다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리한 https://ratsgo.github.io/에서 발췌하여 정리함을 먼저 밝힙니다. 개념 최단경로 문제의 optimal substructure를 확장하면 최단경로를 다음과 같이 분해(decompostion)할 수 있습니다. 시작노드 s에서 v에 이르는 최단경로는 s에서 u까지의 최단경로에 u에서 v 사이의 가중치(거리)를 더한 값이라는 겁니다. 벨만-포드 알고리즘은 s,u 사이의 최단경로를 구할 때 그래프 내 모든 엣지에 대해 edge relaxation을 수행해 줍니다. 그러면 이를 몇 번 수행해야 할까요? 생각해 보면 s,u..