📂 알고리즘

보이어-무어(Boyer-Moore) 알고리즘

1. 개념 📸 보이어-무어(Boyer-Moore) 알고리즘은 skip이라는 것을 활용한 문자열 매칭 알고리즘이다. 여기서 skip이란 문자열을 비교할 때 불필요한 비교가 있다면 건너뛸 수 있도록 도와주는 것이다. (정확한 명칭은 아니지만 아래의 동작방식을 본다면 왜 skip이라고 불리는지 알 수 있을 것이다.) 보이어-무어 알고리즘은 문자열을 비교할 때 일반적으로 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 그래서 비교할 문자열과 패턴을 앞부분부터 확인하는 것이 아닌 뒷부분부터 확인하게 된다. 2. 동작방식 🎬 기본적인 동작방식은 일치하지 않은 문자를 만난 경우 패턴에서 일치하는 문자를 찾아서 이동한 후 비교를 다시 시작한다는 것이다. 본문은 'abphone' 패턴은 'phon..

라빈-카프(Rabin-Karp) 알고리즘

1. 개념 ⚽ 라빈-카프(Rabin-Karp) 알고리즘이란 해싱(Hashing)을 이용한 문자열 매칭 알고리즘이다. 비교하고자 하는 문자들과 패턴의 문자들을 일일이 비교하는 대신에 문자열의 해시값을 비교하는 방식으로 진행된다. 2. 동작방식(연습용) 🏀 동작 방식은 아래와 같다. 해시 함수를 설정한다. 해시 함수를 이용하여 패턴의 해시값을 구한다. 비교하고자 하는 문자열의 해시값을 구한다. 일치하면 패턴과 찾은 문자열을 1:1 비교한다. 일치하지 않으면 비교하고자 하는 문자열을 한 칸 뒤로 옮겨서 3번부터 다시 시작한다. 해시값이 같더라도 1:1 매칭을 통해서 최종적으로 패턴과 비교하고자 하는 문자열이 일치하는지 확인하는 절차가 필요하다. 그 이유는 해시값이 같다고 해서 무조건 같은 문자열이라고 보장할 ..

플로이드-와샬(Floyd-Warshall) 알고리즘

1. 개념 🐕‍🦺  플로이드-와샬(Floyd-Warshall) 알고리즘이란 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 다익스트라(Dijkstra) 알고리즘과 다르게 음의 가중치를 허용한다는 게 특징이라고 할 수 있다.  다익스트라 알고리즘을 간단하게 설명하자면 출발 정점으로부터 모든 정점까지의 최단경로를 구하는 알고리즘이다. 다익스트라를 이용하여 플로이드-와샬 알고리즘을 구현한다고 하면 출발 정점을 모든 정점의 개수만큼 설정해 주면 된다.  순차 탐색 방법으로 다익스트라를 구현하면 O(V^2)이고, 모든 정점을 출발 정점으로 한다고 하면 O(V * V^2) = O(V^3)이 되게 된다. 플로이드-와샬 알고리즘의 시간복잡도 또한 O(V^3)으로 같다. 하지만 플로이드-와샬 알..

최장공통부분수열(Longest Common Subsequence - LCS)

1. 개념 🐢 최장공통부분수열(Longest Common Subsequence)이란 주어진 수열의 부분 수열에서 가장 긴 것을 의미한다. 위의 그림에서 알 수 있는 것처럼 부분 수열이 연속적일 필요는 없다. 2. 동작방식 🦎 동작 방식은 DP를 이용한다. 문자열 A와 문자열 B가 주어졌다고 하자. 문자열 A와 문자열 B를 한 글자씩 비교한다. 비교하는 문자가 같다면 DP[i][j] = DP[i - 1][j - 1] + 1이 된다. 비교하는 문자가 다르다면 DP[i][j]는 DP[i-1][j]와 DP[i][j-1] 중에 큰 값으로 설정한다. 1번과 2번 과정을 반복한다. 여기서 말하는 DP[i][j]는 문자열 A는 i번째까지 문자열 B는 j번째까지 고려하였을 경우에 얻을 수 있는 최장공통부분수열의 길이이다..

최장공통문자열(Longest Common Substring - LCS)

들어가기에 앞서 LCS를 구별하도록 하자. 일반적으로 LCS라고 하면 최장공통부분수열(Longest Common Subsequence)을 뜻하지만, 최장공통 문자열(Longest Common Sustring)도 LCS라고 부르기도 한다. 둘의 차이점은 구하고자 하는 부분 문자열의 연속성이라고 할 수 있다. 이번 글에서는 최장공통 문자열(Longest Common Substring)에 대해서 먼저 알아보자 1. 개념 🦆 최장공통부분문자열(LCS)은 연속된 부분 문자열 중 가장 길이가 긴 문자열을 말한다. 2. 동작 방식 🐓 동작 방식은 DP를 이용한다. 문자열 A와 문자열 B가 주어졌다고 하자. 문자열 A와 문자열 B를 한 글자씩 비교한다. 비교하는 문자가 같다면 DP[i][j]는 DP[i-1][j-1] ..

최장증가부분수열(Longest Increasing Subsequence - LIS)

1. 개념 🌠 최장 증가 부분 수열(LIS - Longest Increasing Subsequence)이란 임의의 수열로 만든 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 의미한다. '3 2 6 4 5 1'이 있다고 하자. 해당 수열의 부분 수열은 {3}, {2}, {6},... {3, 2}, {2, 1},... {2, 6, 4}, {2, 4, 5},... {3, 2, 5, 1},... {2, 6, 4, 5, 1},... {3, 2, 6, 4, 5, 1} 등이 존재한다. 여기서 최장 증가 부분 수열은 {2, 4, 5}이며 그 길이는 3이 되게 된다. 이번 글을 통해 최장 증가 부분 수열의 길이를 구하는 3가지 방법을 알아보자. 순서는 시간복잡도가 큰 것에서부터 작은 것으로 진행된다. 2. 방법 1 ..

다익스트라(Dijkstra) 알고리즘

1. 기본 개념 🍄 1. 최단 경로 가중치 그래프에서 두 정점 사이의 경로들 중에서 가중치의 합이 최소가 되는 경로 2. 대표적인 최단 경로 알고리즘 다익스트라(Dijkstra) 벨만포드(Bellman-Ford) 플로이드 와샬(Floyd-Warshall) 정의 출발 정점로부터 모든 정점까지의 최단 경로를 구하는 알고리즘 출발 정점로부터 모든 정점까지의 최단 경로를 구하는 알고리즘 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘 특징 음의 가중치를 허용 X 음의 가중치를 허용 O 음의 가중치를 허용 O 사용하는 알고리즘 그리디 알고리즘 그리디 알고리즘 DP 알고리즘 시간복잡도 O(V ^ 2) 또는 O(E log V) O(V ^ 2) 또는 O(E log V) O(V ^ 3) 2. 다익스트라(..

PRIM 알고리즘

최소신장트리를 만드는 두 번째 방법인 PRIM 알고리즘에 대해서 알아보자. (첫 번째 방법으로는 KRUSKAL 알고리즘이 있었다.) 1. PRIM 알고리즘 👓 1. 기본 개념 그리디 방식을 이용하여 최소 신장 트리를 찾는 방식 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 만들어 나가는 방식 2. 동작 방식 그래프에서 하나의 정점을 선택하여 트리를 만든다. 트리와 연결되어 있지만 아직 선택되지 않은 정점들 중에서 간선의 가중치가 가장 낮은 정점을 트리에 포함시킨다. 트리가 N-1의 간선을 가질 때까지 2번을 반복한다. 2. 구현 (JAVA) 🤿 구현 방식으로는 아래의 2가지 방법이 있다. 반복문을 통해 다음 정점을 찾는 방식 PriorityQueue를 이용해 다음 정점을 찾는 방식 위의 예시를 통..

KRUSKAL 알고리즘

1. 기본 개념 🧪 1. 신장 트리 (Spanning Tree) n개의 정점을 가지는 그래프에서 n개의 정점을 모두 연결할 수 있는 n-1개의 간선으로 이루어진 트리 (간선은 n-1개 이상일 수 있다.) 물론 n-1개 이상의 간선을 가져도 신장 트리가 될 수 있다. 2. 최소 신장 트리(Minimum Spanning Tree) 무향 가중치 그래프에서 가중치의 합이 가장 작은 신장 트리를 최소 신장 트리라고 한다. 2. KRUSKAL 알고리즘 🧫 1. 기본개념 그리디 방식을 이용하여 최소 신장 트리를 찾는 방식 그리디한 방식 자체가 항상 최적의 해답을 제공한다는 보장은 없지만, KRUSKAL 알고리즘에서는 최적의 해답을 제공하는 것으로 증명되어있다. 2. 동작 방식 모든 간선들을 가중치에 따라 오름차순으로..

서로소 집합(Disjoint-sets)

1. 서로소 집합의 개념 및 이해 🛺 1. 개념 서로소 집합이란 서로 중복 포함된 원소가 없는 집합을 말한다. 교집합이 없는(null) 집합이다. 2. 대표자 집합에 속한 하나의 특정 멤버를 대표자라고 한다. 이는 집합을 구분하기 위해 사용된다. 3. 예시 빠른 이해를 위해 간단한 예시를 살펴보자. 5명의 학생(A, B, C, D, E)이 있다고 하자. {A}, {B}, {C}, {D}, {E} 아래와 같은 친구 관계가 있다고 하자. A - B B - C D - E 친구 관계를 통해서 2개의 집합을 만들 수 있다. G1 = {A, B, C} G2 = {D, E} 서로 중복 포함된 원소가 없으므로 이는 서로소 집합이다. (한 사람이 분신술을 써서 양쪽 집합에 포함될 수 없으므로 당연한 결과이다.) 2. 표..