1. Trie(트라이)란? 다음과 같은 문자열 집합이 있습니다. S = {"HE", "HELLO", "WORLD", "SHE"} 위 문자열 집합에 "SHE"라는 문자열이 포함되어 있는지 확인하고 싶다면 어떻게해야 할까요? 🤔 Naive한 방법으로는 이중 반복문으로 일일이 비교하는 방법이 있습니다. 문자열 집합의 갯수를 N, 문자열의 최대길이를 M이라고 했을 때, 이 방법의 시간 복잡도는 O(NM)입니다. Trie는 문자열 집합에서 특정 문자열이 존재하는지 찾을 때 O(M)의 시간 복잡도로 해결할 수 있습니다. Trie는 문자열을 트리의 형태로 자료구조화하는 자료구조입니다. 위 문자열 집합을 Trie로 표현하면 다음과 같습니다. 이해가 되시나요? 위 트리에서 빨간색 테두리로 된 노드는 문자열의 마지막 지점..
1. 개요 다음과 같은 두 개의 문자열이 있습니다. S = "abababdddd" (String의 약자를 따서 S라 표현) W = "bab" (Word의 약자를 따서 W라 표현) 아시는거처럼 S에서 W가 존재하는지를 찾아내는, 이른바 일대일 문자열 패턴 매칭 알고리즘으로는 KMP 알고리즘이 있습니다. 그런데 매칭에 사용될 패턴이 다음과 같이 여러 개라면 어떨까요? 🤔 S = "abababdddd" W = {"bab", "bd", "ab"} 즉, 하나의 문자열 안에서 여러 개의 부분 문자열이 존재하는지 찾아내는 일대다 문자열 패턴 매칭이라면 어떻게 할 수 있을까요? 물론 W 집합 안의 문자열에 대해 하나씩 KMP 알고리즘을 돌려보는 방법도 가능합니다. KMP 알고리즘의 시간 복잡도는 니깐,..
1. 개요 문자열 매칭을 생각해보면, ABABABAC // 원본 문자열 (S[i], 원본 문자열 길이 n) ABAC // 찾을 문자열 (P[i], 찾을 문자열 길이 m) 위의 S 문자열에서 P 문자열을 찾는 패턴 매칭에서 가장 단순(Naive)한 방법은 다음과 같습니다. 첫 번째 인덱스부터 P 문자열의 길이인 m만큼 비교해보고 불일치하면 다음 인덱스로 이동한 후 다시 첫 문자부터 비교합니다. 이 똑같은 행동을 n-m-1 인덱스까지 반복하기에 총 시간 복잡도는 O(nm) 이 걸리게 됩니다. 2. KMP (Knuth-Morris-Pratt) 알고리즘이란? 문자열 매칭(또는 패턴 매칭) 알고리즘은 대표적으로 3가지가 있습니다. KMP 알고리즘 Rabin-Karp 알고리즘 Boyer-Moore 알고리즘 KMP ..
1. 개요 구간 합 문제에서 세그먼트 트리가 사용됩니다. (꼭 합이 아니어도 구간의 최솟값이라든가 어떤 구간의 정보를 저장할 때 사용합니다. 🧐 ) 다음의 두 가지 요구사항을 가지는 문제가 있습니다. (start, end) 구간에서 구간의 합을 구해야한다. (arr[start] + arr[start + 1] + ... + arr[end - 1] + arr[end]) 특정 위치의 값이 빈번히 변경된다. (start + 10의 위치값을 v로 변경하기 등등) 요구사항 자체는 아주 간단하지만, 문제는 성능입니다. 단순 반복문을 이용하게 되면 위의 1번 연산은 , 2번 연산은 이 걸리게 됩니다. 위 연산이 최대 M번 수행된다고 할때 총 시간 복잡도는 $\m..
LIS(Longest Increasing Subsequence_가장 긴 증가하는 부분 수열)이란? 백준의 다음 문제를 가지고 LIS를 정리해보자 ---> www.acmicpc.net/problem/11053 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 찾아야한다. 예를 들어, A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다. DP를 이용하여 풀 수 있다. DP 배열에는 해당 인덱스까지의 최대 길이를 저장한다. 먼저 첫 번째 인덱스에서는 당연히 자기 자신밖에 없기 때문에 최장 길이가 1이다. 두 번째 인덱스를 보면, 해당 값이 이전의 값보다 크기 때문에 이전 인덱스의 DP 배열의 ..
슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 개념이 유사하다. 투 포인터 알고리즘 같은 경우 left와 right라는 처음과 끝을 가리키는 포인터가 서로 독립적으로 움직이는데에 반해, 슬라이딩 윈도우 알고리즘은 처음과 끝을 가리키는 포인터가 서로 같이 움직인다. 슬라이딩 윈도우라는 이름 그대로 고정된 윈도우가 슬라이딩하는 것처럼 움직인다. 처음과 끝에 대해서 삽입과 삭제가 빈번히 이뤄지기 때문에 디큐(Deque) 자료구조가 대게 같이 사용된다.
1차원 배열이 주어졌을 때, 특정 연속된 구간의 합이 M이 되는 경우의 수를 구하려면 어떻게 해야 할까? 가장 단순하게 생각해볼 수 있는 방법은 2중 반복문을 돌리는 것이다. public class Main { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2}; // 크기가 10인 1차원 배열 int m = 5; // 연속된 구간의 합이 5인 경우를 찾는다. int count = 0; for (int i = 0; i ..
최단 경로 알고리즘은 크게 두 가지로 분류된다. one-to-all : 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구한다. (다익스트라 알고리즘, 벨만-포드 알고리즘) all-to-all : 모든 정점에 대해 자신을 제외한 다른 모든 정점으로의 최단 경로를 구한다. (플로이드-와샬 알고리즘) 벨만 포드 알고리즘은 one-to-all에 속하며, 이 외에도 다익스트라 알고리즘이 있다. 벨만 포드(Bellman-Ford) 알고리즘 벨만 포드 알고리즘의 특징은 다음과 같다. one-to-all (하나의 정점에서 다른 모든 정점으로의 최단 경로를 구한다.) 음의 가중치일 경우에도 사용이 가능하다. (다익스트라는 가중치가 음수이면 사용이 불가능) 시간 복잡도가 로 ..
1. 개요 최단 경로 알고리즘은 크게 두 가지로 분류됩니다. one-to-all : 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구한다. (Dijkstra 알고리즘, 벨만-포드 알고리즘) all-to-all : 모든 정점에 대해 자신을 제외한 다른 모든 정점으로의 최단 경로를 구한다. (Floyd-Warshall 알고리즘) Dijkstra 알고리즘은 one-to-all에 속하며, 이 외에도 벨만 포드 알고리즘이 있습니다. 벨만 포드는 음의 가중치일 때 사용되는데, 실세계에서 음의 가중치를 가질만한 것들이 잘 없기 때문에 잘 쓰이진 않습니다. 2. 다익스트라(Dijkstra) 알고리즘이란? Dijkstra 알고리즘의 특징은 다음과 같습니다. one-to-all (하나의 정점에서 다른 모든 정점으로의 ..
1. Floyd-Warshall 알고리즘이란? 최단 경로는 크게 두 가지 경우로 나눌 수 있습니다. one-to-all : 하나의 출발지에 대해 나머지 모든 노드까지의 최단 경로를 구한다. (Dijkstra 알고리즘, 벨만-포드 알고리즘) all-to-all : 모든 노드에 대해 다른 모든 노드까지의 최단 경로를 구한다. (Floyd-Warshall 알고리즘) 플로이드 와샬은 all-to-all 에 대한 최단 경로를 구할 때 사용되는 알고리즘입니다. 5개의 노드가 있다고 가정했을 때, 1번 노드에서 2, 3, 4, 5번 노드까지의 최단 경로, 2번 노드에서 1, 3, 4, 5번 노드까지의 최단 경로, ...처럼 모든 노드에 대해 최단 경로를 구하기 때문에 비용을 저장하기 위해 2차원 배열이 필요합니다. ..
순열()과 조합() 특정 수열에 대해 순열과 조합을 구하는 방법을 알아보자. 먼저 순열은 Permutation의 앞 글자를 따서 로 나타내고, n개의 수열에서 r개의 수를 뽑아 정렬하는 가짓수이다. 예를 들어, { 1, 2, 3 }이란 수열이 있고, 를 구해보면 다음과 같다. {1, 2}, {2, 1}, {1, 3}, {3, 1}, {2, 3}, {3, 2}
LCS (Longest Common Subsequence_최장 공통 부분 수열)이란? 먼저, Subsequence가 무엇인지 이해해야 한다. 일반적으로 부분 문자열을 다룰 때 사용하는 Substring이라는 개념을 살펴보자. 가나다라마바사 가파나카마바사 위의 예시로 든 두 문자열 간의 Substring은 "마바사" 이다. 그렇다면 Subsequence는? 가나다라마바사 가파나카마바사 위의 예시로 든 두 문자열 간의 가장 긴 Subsequence는 '가', '나', '마', '바', '사' 이다. 즉, Substring은 연속된 부분 문자열이고, Subsequence는 연속되지 않은 부분 문자열이다. 개념을 확실히 하기 위해 마지막으로 하나 더 해보자. 아래의 문자열에서 LCS(가장 긴 Subsequenc..