본문 바로가기

Dot Algo∙ DS/알고리즘 개념

[알고리즘] 접미사 배열(Suffix Array)와 LCP 배열(Lognest Common Prefix Array) (Java)
Dot Algo∙ DS/알고리즘 개념 2022. 4. 7. [알고리즘] 접미사 배열(Suffix Array)와 LCP 배열(Lognest Common Prefix Array) (Java) 접미사(Suffix) 접미사(suffix)는 파생어를 만드는 접사로 단어 뒤에 붙어 새로운 단어가 되게 하는 말이다. 문자열 s의 i번째 접미사란, s 의 i번째 글자부터 마지막 글자까지 포함되는 부분문자열을 뜻한다. 문자열 "alohomora" A[i] S[A[i]···] 0 a l o h o m o r a 1 l o h o m o r a 2 o h o m o r a 3 h o m o r a 4 o m o r a 5 m o r a 6 o r a 7 r a 8 a 접미사 배열(Suffix Array) 문자열을 다룰 때 빼놓을 수 없는 자료 구조로 접미사 배열(Suffix Array)가 있다. 접미사 배열은 흔히 '문자열의 맥가이버 칼'이라고 불리며, 굉장히 다양한 문제를 푸는 데 쓸 수 있다. 접미사 배..
[알고리즘] 균형잡힌 이진 검색 트리 Balanced BST - 트립(Treap) (Java)
Dot Algo∙ DS/알고리즘 개념 2022. 1. 17. [알고리즘] 균형잡힌 이진 검색 트리 Balanced BST - 트립(Treap) (Java) 균형잡힌 이진 검색 트리 (Balanced Binary Search Tree) 표준 라이브러리의 이진 검색 트리는 대부분 X보다 작은 원소의 수를 계산하거나 k번째 원소를 찾는 연산을 지원하지 않기 때문에 이진 검색 트리를 직접 구현해야 할 경우가 종종 있다. 단순한 이진 검색 트리는 특정 형태의 입력에 대해 편향트리와 같은 연결 리스트가 되어 버리는 문제가 있기 때문에, 균형잡힌 이진 검색 트리를 구현해야 한다. AVL 트리나 레드 블랙 트리 등 교과서에 실리는 대부분의 균형잡힌 이진 검색 트리들은 구현이 매우 까다롭다. 다양한 경우의 수를 따져서 구현해야 하기 때문에 코드도 길고, 한정된 시간 안에 코드를 작성해야 하는 프로그래밍 대회에서 사용하기엔 부적합하다. 따라서 대회에서는 구현이 간단한 트립(..
[알고리즘] 펜윅 트리(Fenwick Tree) 빠르고 간단한 구간 합 구하기 (Java)
Dot Algo∙ DS/알고리즘 개념 2022. 1. 3. [알고리즘] 펜윅 트리(Fenwick Tree) 빠르고 간단한 구간 합 구하기 (Java) 펜윅 트리(Fenwick Tree) : 빠르고 간단한 구간 합 세그먼트 트리의 가장 흔한 사용 예는 바로 구간 합을 빠르게 구하는 것이다. 이 경우 세그먼트 트리 대신 쓸 수 있는 세그먼트 트리의 궁극적인 진화 형태로 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(binary indexed tree)라고 불리는 것이 있다. 펜윅 트리가 사용하는 중요한 아이디어는 구간 합 대신 부분 합만을 빠르게 계산할 수 있는 자료구조로 만들어도 구간 합을 계산할 수 있다는 것이다. arr[]의 위치 pos에 대해 배열의 부분합 psum[pos] = arr[0] + arr[1] + ··· + a[pos]를 빠르게 계산할 수 있다고 하자. 그러면 [i, j] 구간의 합은 psum[j] - psum[i-1]로 ..
[알고리즘] 이분 매칭 (Bipartite Matching) 알고리즘 (Java)
Dot Algo∙ DS/알고리즘 개념 2022. 1. 1. [알고리즘] 이분 매칭 (Bipartite Matching) 알고리즘 (Java) 매칭 문제 (Matching Problem) N명의 유치원생이 소풍을 가는데, 단독 행동을 막기 위해 둘씩 짝을 이뤄 같이 다니게 하려고 한다. 단 서로 사이가 안 좋은 학생끼리 짝을 지어 주면 떨어져서 따로 다니기 때문에, 사이가 좋은 학생끼리만 짝을 지어 주고 싶다. 이런 규칙 하에서 모든 학생에게 짝을 지어 줄 수 있을까? 불가능하다면 최대 몇 쌍이나 만들 수 있을까? 그래프로 간단하게 표현할 수 있다. 각 학생을 표현하는 정점을 만든 뒤, 사이 좋은 학생들을 간선으로 연결한다. 이때 서로 짝을 이룬 학생들을 연결하는 간선들을 모아 보면, 이들은 끝점을 공유하지 않는 간선의 집합이 된다. 이런 간선의 집합을 이 그래프의 매칭(matching)이라고 부른다. (a) 굵은 회색으로 표시한 간선들은 끝점..
[알고리즘] 네트워크 유량, 포드-폴커슨(Ford-Fulkerson) 알고리즘 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 12. 27. [알고리즘] 네트워크 유량, 포드-폴커슨(Ford-Fulkerson) 알고리즘 (Java) 네트워크 유량 그래프 문제에는 경로의 길이 외에도 그래프에 대해 정의할 수 있는 중요한 개념이 있다. 바로 그래프의 ‘용량’이다. 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 ‘흐름’ 혹은 ‘유량’을 보낼 수 있는지를 계산하는 문제를 네트워크 유량(network flow) 문제라고 부른다. 교통망에서 두 도시 사이를 이동할 수 있는 시간당 차량의 수, 송유관 네트워크에서 두 도시 사이에 보낼 수 있는 석유의 양 등 네트워크 유량은 현실에서 자주 찾을 수 있는 문제들이다. 또한 네트워크 유량은 굉장히 강력한 최적화 문제로, 그래프와 별 상관이 없어 보이는 다양한 최적화 문제들을 푸는 데도 이용할 수 있다. 유량 네트워크(flow network)란 각 간선에 용량(capacity)이라는 추..
[알고리즘] SCC(Strongly Connected Component) (백준 2150번 풀이)
Dot Algo∙ DS/알고리즘 개념 2021. 12. 5. [알고리즘] SCC(Strongly Connected Component) (백준 2150번 풀이) #2150 Strongly Connected Component 난이도 : 플레 5 유형 : 그래프 이론 / SCC 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net ▸ 문제 방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오. 방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는..
[알고리즘] 단절점 (백준 11266번 풀이)
Dot Algo∙ DS/알고리즘 개념 2021. 12. 3. [알고리즘] 단절점 (백준 11266번 풀이) #11266 단절점 난이도 : 플레 5 유형 : 그래프 이론 / 단절점 / DFS 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net ▸ 문제 그래프가 주어졌을 때, 단절점을 모두 구해 출력하는 프로그램을 작성하시오. 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말한다. ▸ 입력 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000..
[알고리즘] 다중 문자열 검색 아호 코라식(Aho-Corasick) 알고리즘 정리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 11. 29. [알고리즘] 다중 문자열 검색 아호 코라식(Aho-Corasick) 알고리즘 정리 (Java) 아호 코라식(Aho-Corasick) 알고리즘 아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)이다. (위키 참고) 패턴 1개를 탐색하는 매칭 알고리즘은 선형 시간에 구현됨을 KMP 등 여러 알고리즘을 통하여 증명되었다. 하지만 패턴 집합에 대하여 이러한 알고리즘을 수행하게 되면 패턴 개수에 비례하여 그 속도가 느려지게 된다. m = 모든 패턴들의 길이 합, p = 패턴수, n = text 크기 즉 , O(m + p*n)의 시간 복잡도를 가지게 된다. 하지만 아호 코라식 알고리즘을 이용하면 O (m + p + n)의 시간복잡도로 패턴 집하에 대하여 패..

티스토리툴바

티스토리툴바