KMP 알고리즘은 문자열 탐색 알고리즘입니다. KMP는 Knuth–Morris–Pratt의 줄임말로 KMP 알고리즘을 제안한 Donald Knuth, Vaughan Pratt 그리고 James H. Morris의 이름을 따서 이름 지어졌습니다. 기본적으로 가장 간단한 문자열 탐색 알고리즘은 완전 탐색으로 찾았을 때, 문자열 M,N에 대하여 O(|M|*|N|)의 시간 복잡도를 갖게 됩니다. 하지만 KMP 알고리즘은 약간의 메모리 공간을 이용하여 불필요한 비교 연산 횟수를 줄여 시간 복잡도를 줄입니다.예를 들어 설명하자면 samsamsung이라는 단어가 있고 samsamsong라는 단어를 찾는다면 맨 앞부터 탐색하여 u와 o에서 차이가 발생하게 됩니다. 간단한 알고리즘 같은 경우 다음 2번째 문자인 a부터 ..
개발 일지
플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 정점 사이의 최단 거리를 구하는 알고리즘으로 O(V^3)의 시간 복잡도를 가집니다.하나의 정점으로부터 다른 모든 정점사이의 최단 거리를 구하는 다익스트라 알고리즘(Dijkstra Algorithm)과 유사하며 다익스트라를 모든 정점에서 동작시키면 플로이드-워샬 알고리즘과 똑같이 동작하지만, 플로이드-워샬 알고리즘이 훨씬 간결하게 구현됩니다. 또한 다익스트라 알고리즘은 음수 간선치가 있을 시 제대로 동작하지 않지만, 플로이드-워샬 알고리즘은 음의 사이클만 없다면 음수 간선치가 있더라도 잘 동작합니다.플로이드-워샬 알고리즘은 정점 N개의 그래프가 주어졌을 때, 모든 정점쌍 (i,j)에 대하여 k라는 경유지를 거쳤을 때, ..
벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 어느 한 정점에서 나머지 정점까지 거리를 구하는 알고리즘입니다. 하지만 다익스트라와는 다르게 음수 가중치를 갖는 그래프에서도 동작을 하며, 음수 사이클을 찾아내는 기능도 가지고 있습니다.이러한 장점을 갖는 대신에 알고리즘의 수행 시간은 일반적으로 다익스트라보다 느린 단점을 가지고 있습니다.이 알고리즘의 기본적인 아이디어는 다익스트라와 비슷합니다.dist배열을 만들어서 최단 거리에 근접하게 계속 갱신시켜주는 방식입니다.하지만 우선순위 큐를 이용하여 간선에 연결된 정점의 최단 거리를 갱신하는 것이 아니라, 모든 정점의 최단 거리를 구할 때까지 모든 간선들을 여러 번 확인하여 최단 거리를 구한다는 것이 차이점입니다.벨만 포드 알고리즘의 구현 방법은 다익스트..
다익스트라 알고리즘은 그래프의 한 노드에서 연결된 다른 노드들로 가는 최단 거리를 구하는 알고리즘입니다.만약 모든 노드 쌍간의 최단 거리를 구하고 싶다면 N개의 각 정점에 대해 해당 정점을 출발점으로 하는 다익스트라 알고리즘을 수행해야 합니다.이러한 상황에서는 이후에 다룰 플로이드 워셜 알고리즘 알고리즘이 다익스트라를 N번 수행하는 것보다 유효합니다.다익스트라 알고리즘은 한 노드에서 다른 노드로 가는 최단 경로를 구성하는 간선들은 항상 최단 거리를 갖는다는 아이디어를 기반으로 하며 이는 귀류법으로 간단하게 증명 가능합니다.다익스트라의 동작 과정에 대해서 설명하면, 너비 우선 탐색 방법과 비슷합니다.먼저, 해당 노드까지의 최단 거리를 저장할 dist 배열이 필요합니다.또한 이 값은 처음에 방문하지 않았다는..
서로소 집합(Disjoint-Set)은 집합, 혹은 그룹을 관리하는 효율적인 알고리즘입니다.각각의 그룹을 트리 구조로 관리하는 이 알고리즘은 크게 두 가지의 연산을 가집니다. find(x): x번 노드의 최고 조상(루트)을 찾는 함수link(x, y): x노드가 속한 그룹과 y노드가 속한 그룹을 합치는(잇는) 함수또한 위 연산들을 구현하기 위해 par[i]: i번 노드의 부모로 정의되는 배열을 가집니다.예를 들어 1~5번의 번호를 가진 사람이 있다고 합시다.처음에 5명의 사람들은 모두 각자 독립적인 1인 그룹이 됩니다.각 그룹을 정점으로 표현하면 아래와 같습니다.또한 초기 par배열은 다음과 같습니다.이 상태에서 1번이 속한 그룹과 2번이 속한 그룹을 합치는 link(1, 2) 연산을 수행해봅시다.두 정..
Binary Indexed Tree(또는 fenwick tree, 이하 BIT)는 Segment Tree와 비슷하게 구간에 대한 정보를 저장할 수 있는 자료구조입니다. 기본적으로 아래의 그림과 같은 1-based 구조를 가지며, 구간합 등을 알아내는데 사용됩니다.BIT는 위의 그림처럼 세그먼트트리보다 조금 더 단순화된 구조를 가지지만, 구간에 대한 정보를 [1,X]으로 알아낼 수 있다는 점이 다릅니다.위 그림의 2번지에 그려진 1번지~2번지의 박스는 [1,2]의 구간의 정보를 [2,2]에 가지고 있다는 것을 의미합니다. 마찬가지로 12번지는 [9,12]의 구간의 정보를 가지고 있는 것입니다. 이를 적절히 이용하여 원하는 구간의 정보들을 구하는 것입니다.BIT로 구간의 합을 알아보겠습니다.트리의 구성은 먼..
세그먼트 트리(Segment Tree)는 구간에 대한 정보를 빠르게 구해낼 수 있으며 완전 이진트리 형식의 구조를 가지는 자료구조입니다.구간의 최솟값을 구하는 세그먼트 트리는 먼저 구하고자 하는 배열을 완전 이진트리의 최하단에 위치시킨 후, 모든 부모 노드가 자식 노드들 중 작은 값을 가지게 하며 트리를 완성시킵니다.이를 통해 트리의 어떤 노드 X는 X의 하위 노드 중 최솟값을 가지게 됨은 자명합니다.예를 들어 아래 배열을 사용한 세그먼트 트리의 구현에서 Tree[1]은 모든 원소의 최솟값이 오게 되고, Tree[2]는 하위 노드인 8~11번지의 최솟값이 들어있게 됩니다.이들 중 원하는 범위 [L, R]에 필요한 노드를 골라서 구성할 것입니다.위에서 완성된 세그먼트 트리에서 배열 D에 대한 범위 [L, ..
최소 신장트리란최소 신장 트리(Minimum Spanning Tree)는 가중치가 있는 무방향 그래프의 모든 노드를 포함하면서 사이클이 없고 가중치의 합이 최소가 되는 트리입니다. 연결그래프가 주어질 때, MST를 구하는 알고리즘은 대표적으로 크루스칼, 프림 2가지가 있습니다.두 알고리즘은 비슷한 시간 복잡도를 가지지만 나름의 장, 단점이 있으므로 모두 알아봅시다. 1. 프림 알고리즘프림 알고리즘은 일단 시작점을 아무 정점을 선택하고, 이는 MST를 구성하는 첫 원소가 됩니다.그리고 현재까지 구성된 MST의 원소(시작점)에 연결된 간선 중 가장 가중치가 작은 값을 가지는 간선을 골라 이어준 후 MST의 원소로 추가합니다.그리고 MST가 완벽하게 완성될 때까지 현재까지 구성된 MST의 원소들에 연결된 간..
연산자의 종류와 우선 순위연산자 (Operator) : 변수나 상수에 미리 약속된 연산을 하는 명령어연산 기능에 따른 분류이름연산자부호 연산자+ -산술 연산자+ - * / %증감 연산자++ --대입 연산자= += -= *= /= %= &= |= ^= >>= >>>= 관계 연산자 >= == !=논리 연산자&& || !비트 연산자& | ~ ^ >> >>> 조건 연산자?:캐스트 연산자(type)피연산자의 개수에 따른 분류이름연산자단항 연산자+(부호) -(부호) ++ -- ! ~ (type)이항 연산자+ - * / % = += -= *= /= %= &= |= ^= >>= >>>= 삼항 연산자?:연산자 우선 순위종류연산자결합 방향우선 순위일차식( ) [ ]→높다단항 연산자! ~ ++ -- -(부호) +(부호) (..
목차동적 계획법이란Top-Down와 Bottom-UpCoin Change ProblemKnapsack Longest Common Subsequence Longest Increasing Subsequence Edit Distance Matrix Chain Multiplication 1. 동적계획법이란 흔히 DP라 불리는 동적 계획법이란, 복잡한 문제를 여러 개의 작은 부분 문제(sub-problem)로 나누어 해결하는 문제 해결 기법입니다. 동적 계획법의 특징 중 하나는 이미 계산된 부분 문제가 다시 발생하면 새롭게 계산하지 않고 이전의 계산값을 참조하여 이용하는 것입니다. 이 방법은 부분 문제를 다시 해결하는 데 필요한 시간을 절약할 수 있지만, 이전 계산값을 저장해 둘 공간이 필요하므로 시간과 메..
위상 정렬이란 유향 그래프에서 정해진 순서를 위배하지 않도록 나열하는 것입니다.예를 들면 전략 게임에서의 빌드 오더나 선수강과목을 예로 들 수 있습니다.전략 게임의 빌드 오더에서 A를 짓지 않으면 B를 지을 수 없고, B를 짓지 않으면 C를 지을 수 없다와 같은 규칙이 있을 수 있고, 선수강과목은 자료구조 과목을 듣지 않으면 알고리즘 과목을 수강할 수 없다는 규칙이 있을 수 있습니다.이러한 순서에 따라서 나열하는 것이 바로 위상 정렬입니다.만약에 이런 규칙에 순환이 생긴다면 순환이 생긴 그 무엇도 나열할 수 없기 때문에 DAG(directed acylic graph)에서만 위상 정렬이 가능합니다. 구현 방법에 대해서 설명을 하자면, 먼저 그래프를 구성할 때 간선의 의미는 A->B 라면, A를 방문해야 ..
퀵 정렬(Quick Sort)은 배열에 있는 수 중 사용자가 지정한 규칙대로 임의의 pivot을 잡고, 해당 pivot을 기준으로 작거나 같은 수를 왼쪽 파티션, 큰 수를 오른쪽 파티션으로 보내고 다시 왼쪽 파티션 구간에 한하여 pivot을 잡고 파티션을 나누고 오른쪽 파티션 구간에서도 pivot을 잡고 파티션을 나누는 과정을 반복하여 정렬시키는 정렬 알고리즘입니다.이 알고리즘의 핵심은 pivot을 잘 설정하여 왼쪽 파티션과 오른쪽 파티션을 적절하게 나누는 것입니다.왜냐하면 pivot을 해당 구간의 중앙값으로 잘 설정하면 합병 정렬과 같은 시간 복잡도 O(nlogn)에 수행할 수 있지만, 만약 매 케이스마다 구간의 가장 큰 값이나 가장 작은 값으로 나눠버리면 O(n^2)의 수행 시간을 갖게 됩니다. (1..
분할정복(Divide and Conquer)은 말 그대로 문제를 분할한 다음, 분할한 문제들 (sub-problems)을 해결하고, 그 결과를 합쳐서 원래의 문제를 해결하는 것입니다.분할정복의 대표적인 예로는 합병 정렬, 고속 푸리에 변환 등이 있습니다.합병정렬을 예로 설명해보겠습니다.영역을 나눈 후, 나누어진 영역을 투 포인터(Two Pointer) 알고리즘으로 합병하는 방식으로 동작합니다.투 포인터 알고리즘을 사용하려면 나눠진 영역이 정렬이 되어있어야 하기 때문에 먼저 영역을 작게 나눈 후 합치는 재귀적인 방법이 사용됩니다.이진탐색과 유사하게 전체 영역을 [L, R], M = (L + R) / 2이라고 할 때 [L, M], [M+1, R] 두 개의 영역으로 분할하겠습니다. 왼쪽 부분을 다시 분할해 보..
너비 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점들을 발견하면 그 간선을 통해 방문하지 않은 정점들을 자료구조 큐에 넣습니다. 그리고 큐의 front 정점을 방문하고 pop합니다.또 해당 정점에서 인접한 간선을 검사해 방문하지 않은 정점들을 큐에 넣고 방문하기는 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없으면 종료합니다. 이러한 과정을 반복하여 큐에 더 이상 정점이 존재하지 않을 때까지 실행하여 그래프의 모든 정점을 방문하는 알고리즘이 BFS 알고리즘입니다위의 그림과 같은 유향 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작은 쪽을 먼저 방문한다고 가정..
해싱은 임의의 길이의 데이터(키, Key)를 고정된 길이의 데이터(해시값, Hash value)로 변환해 작은 크기의 해시 테이블로 대응(Mapping)시켜 식별하는 하나의 기법입니다. 해시 테이블은 M개의 버킷으로 이루어져 있으며, 이 글에서 다루는 해시값은 해당 키가 저장될 버킷의 번호(해시 테이블의 인덱스)를 나타냅니다. 키에서 해시값을 추출하는 일련의 과정을 해시 함수(Hash function)라고 합니다. 해시 함수는 같은 키에 대해서는 동일한 해시값을, 다른 키에 대해서는 다른 해시값을 추출해야 합니다. 하지만 일반적으로 해싱에서 해시값의 범위(M)는 키의 범위보다 작기 때문에 어떤 이상적인 해시 함수라도 비둘기집의 원리에 의해 서로 다른 두 키가 같은 해시값을 가질 수 있습니다. 이런 경우..
