hellogaon

위상정렬(Topological Sort)은 의존성이 있는 작업들이 주어질 때이들을 어떤 순서로 수행해야 하는 지를 순서대로 나열하는 것을 의미합니다.사용법의 예로 대학의 선수과목 구조에서 특정 수강과목에 선수과목이 있다면 선수과목을 먼저 수강해야 하므로선후관계가 있는 이 구조를 그래프로 만들어 위상정렬하게 된다면 올바른 수강 순서를 찾을 수 있습니다.위상정렬이 가능하려면 유향그래프(Directed Graph)에 순환(cycle)이 존재하지 않아야하며이는 DAG(Directed Acylic Graph)여야 한다는 것을 알 수 있습니다.위상정렬은 아래의 2가지 방법을 사용하여 구할 수 있습니다. 1. DFS의 종료하는 순서를 기록한 뒤 뒤집는다.2. 들어오는 간선이 없는 정점을 큐에 넣은 뒤 큐에서 하나를 ..

접미사 배열(Suffix Array)은 어떤 문자열의 모든 접미사를 사전순으로 정렬해 둔 배열입니다.이를 구하기 위해 문자열의 접미사들을 모아놓은 뒤 정렬을 하게 되면길이가 N인 문자열의 접미사의 개수는 N개 이므로 O(NlgN)번 비교연산을 진행하지만string은 한 번 비교연산을 할 때마다 틀릴 때까지 앞글자부터 하나하나 비교를 하기에 시간복잡도가 O(N^2 lgN)입니다.이 때 좀 더 빠르게 접미사 배열을 만들기 위하여 맨버-마이어스 알고리즘을 사용합니다.접미사들의 특성을 이용하여 매번 접미사를 첫 한글자, 두글자, 네글자, 여덟글자... 기준으로 정렬하며매번 이전 정렬에서 얻은 정보를 이용하여 두 문자열을 빠르게 대소 비교합니다.이러한 과정으로 진행하면 비교연산을 O(lgN)번으로 줄일 수 있으며..

아호-코라식(Aho-Corasick)은 다중 문자열 검색을 하게 해주는 알고리즘입니다.이전의 KMP 알고리즘에서 길이가 N인 문자열에서 길이가 M인 문자열 하나를 검색하는 데의 시간복잡도가 O(N + M) 였기에길이가 N인 문자열에서 길이가 각각 m1, m2, m3...인 문자열 여러 개를 검색할 경우이에 대한 시간 복잡도는 O(N + m1 + N + m2 + N + m3...)입니다.이 때 아호-코라식 알고리즘은 이를 P는 검색할 문자열의 출현 횟수 일 때O(N + m1 + m2 + m3... + P)와 같은 시간 복잡도로 N을 1번만 본 뒤 계산을 합니다.그렇기에 이는 긴 문자열에서 많은 문자열을 찾아야 할 경우 사용하면 효율적인 알고리즘입니다.아호-코라식 알고리즘은 아래와 같은 정보들을 추가적으로 ..

트라이(Trie)는 문자열의 집합을 표현하는 트리 자료구조입니다.STL로 문자열의 집합을 표현하려면 set을 사용합니다.set에서 검색할 때는 O(lgN)번 비교연산을 진행하지만string은 한 번 비교연산을 할 때마다 틀릴 때까지 앞글자부터 하나하나 비교를 하기에문자열의 길이가 M일 경우 시간복잡도가 O(MlgN)이 됩니다.이를 O(M)만에 탐색하기 위해 트라이 자료구조를 사용합니다.트리 형태를 이용하여 다음에 나올 글자에 해당하는 노드가 있을 경우그 노드로 바로 이동하여 다음 글자를 탐색합니다.그 노드로 바로 이동하기 위해 다음 글자를 가능한 글자들을 가리키는 여러 개의 포인터 배열이 필요한데이는 많은 메모리를 낭비하게 되는 단점이 있습니다.이렇기 때문에 트라이를 사용해야하는 문제에서는 입력 데이터의..

KMP(Knuth Morris Pratt)는 문자열 검색 알고리즘입니다.길이가 H인 문자열에서 길이가 N인 문자열을 검색하고 싶을 경우완전탐색으로 보게 된다면 시간복잡도가 O(HN)이 되지만KMP는 O(H + N)만에 문자열을 검색하게 해주는 알고리즘입니다.기본적인 원리는 문자열을 검색하다가 일치하지 않는 부분이 나왔을 경우H의 다음 글자와 N의 처음부터 비교하는 것이 아닌지금까지 일치했던 부분의 접미사도 되고 접두사도 되는 문자열의 최대 길이만큼은 또 다시 일치하므로그 길이 이후부터 비교해 나가는 방식입니다.이 때, 접미사도 되고 접두사도 되는 문자열의 최대 길이를 저장해놓은 테이블을부분 일치 테이블이라고 부르는데 이를 구하는 방법 또한N에서 자신을 제외하고 N을 찾는 방법으로 구할 수 있기에비슷한 두..

트립(Treap)은 tree와 heap의 합성어로STL에서 제공하지 않는 기능이 필요할 때 이진 검색 트리(Binary Search Tree)를직접 간단하게 구현 할 수 있는 자료구조입니다.예를 들어 어떤 수보다 작은 원소의 수 또는 k번째 원소를 찾는 연산은 STL에서 지원이 되지 않기에관련한 기능이 필요할 경우 사용할 수 있습니다. 기본 문제 2465번: 줄 세우기

상호배타적 집합(Disjoint Set)은 유니온 파인드(Union Find) 자료구조로도 불리며어떤 두 부분집합 사이에도 교집합은 없고 모든 부분집합의 합집합은 전체 집합인 자료를 표현합니다.이 자료구조는 아래의 2가지 함수를 지원합니다. 1. find(u) : 노드 u가 속해있는 집합의 루트를 반환한다.2. merge(u, v) : 노드 u가 속해있는 집합과 노드 v가 속해있는 집합을 합친다. find함수로 find(u)와 find(v)의 값이 같다면 u와 v는 같은 집합, 다르다면 다른 집합에 있는 정보를 얻을 수 있으며다른 집합에 있을 경우 merge함수를 이용하여 두 집합을 합칠 수 있습니다.추후 그래프파트의 최소 스패닝 트리에서 이 자료구조를 사용하기에 알아두면 좋은 자료구조입니다. 기본 문제..

LCA(Lowest Common Ancestor)는 최소 공통 조상이라고도 불리며트리에서 두 노드 u와 v를 모두 자손으로 갖는 노드 중 가장 아래에 있는 노드를 구하는 기법입니다.기본적으로 아래의 과정을 진행하여야 합니다. 1. u보다 v가 더 깊이(depth)가 더 깊을 경우 v를 부모노드로 올린다.2. 이제 u와 v의 깊이가 같아졌을 경우 u와 v를 같이 부모노드로 올린다.3. 2번 과정을 u와 v가 같은 노드를 가리킬 때까지 진행한다. 하나하나 부모노드로 올려 진행하였을 때 최악의 경우에는 O(N)의 시간복잡도로 LCA를 구하게 되는데앞서 배운 DP와 비트마스크 기법을 이용하여정점의 2^k번째 부모를 부분문제로 저장하여 O(lgN)만에 구할 수 있습니다.이는 트리 상에서 두 정점의 거리를 빠르게 ..

구간트리(Segment Tree)는 저장된 자료들을 적당히 전처리하여특정 구간에 대한 질의를 빠르게 대답할 수 있도록 하게 하는 기법입니다.보통 원소의 값 변경이 자주 일어나며 구간 원소의 합, 곱, 최댓값, 최솟값을 반복적으로 구해야 할 때 사용합니다.구간에 대한 질의를 답할 때의 시간복잡도는 O(lgN), 원소 하나의 값이 변경 되었을 때의 시간복잡도는 O(lgN)이며길이가 K인 구간의 원소의 값이 변경 되었을 경우의 시간복잡도는 O(KlgN)입니다.이를 O(lgN)만에 하게 하기 위하여 레이지 프로퍼게이션(Lazy Propagation)기법을 사용합니다.또한 앞서 배운 비트마스크 기법을 응용하여 짧고 간단하게 구간 합을 구할 수 있는 팬윅트리(Fenwick Tree)를 이용하여 구간 합을 응용하여 ..

비트마스크(Bitmask)는 정수의 이진수 표현을 자료구조로 쓰는 기법입니다.집합의 크기가 작은 집합을 나타내기 위해 많이 사용되며정수형 변수 하나로 이들을 나타낼 수 있어 함수의 인자로 넘겨주거나배열의 인덱스로 사용하여 접근이 가능하기에 익숙해지면 유용한 기법입니다.완전탐색, DP를 사용하는 문제를 풀 때 원하는 자료를 간단하게 표현하기 위해,또는 추후 트리파트의 구간트리에서 배우게 될 팬윅트리에서도 이 기법을 응용하여 사용합니다.여러가지 테크닉이 존재하기에 많이 사용해보시는 것이 좋습니다. 기본 문제 11723번: 집합2098번: 외판원 순회1102번: 발전소