정리하기 위한 블로그 정리하기 위한 블로그

정의1. 컷 : 그래프를 2개의 서로 다른 집합으로 나누는 것.가중치가 없는 그래프 - 자른 간선의 개수가 cut의 비용.가중치가 있는 그래프 - 가중치의 합이 cut의 비용. 2. 유량 각 간선은 용량을 가지고 있고, 해당 간선으로 얼마나 많은 유량이 흐를 수 있는지이다.용량 - 각 간선에 할당된 유량은 그 간선의 용량을 초과할 수 없다.유량 보존 - 출발점과 도착점을 제외한 모든 정점에서는 들어오는 유량과 나가는 유량이 같다. 3. 최대 유량 최소 컷 정리 (MFMC) 최대 유량 - 네트워크 출발점에서 도착점으로 보낼 수 있는 가장 큰 유량최소 컷 - 간선을 가장 적게 자를 때 혹은 간선의 가중치 합이 가장 적을 때 용량의 최소합 핵심 - 정점 A와 B를 분리시키는 최소 컷의 비용은 A에서 B로 흐를..

1. DFS 스패닝 트리 DFS 탐색하면서 탐색 순서에 따른 간선 분류와 만들어지는 트리 트리 간선 : 스패닝 트리에 포함되는 간선순방향 간선 : 선조에서 자손으로 연결되는 간선이지만 트리간선이 아닌 간선역방향 간선 : 자손에서 선조로 연결되는 간선 2. 절단점 찾기정의절단점 : 무향그래프에서 어떤 점의 인접한 간선을 모두 지웠을 때 컴포넌트가 두 개 이상으로 나눠지는 점  기차역, 라우터 등 절단점이 있으면 해당 점이 고장나면 전체 망이 고장난다. 절단점 찾는 방법 : DFS 스패닝 트리에서 어떤 정점 u의 서브트리 중에 u의 선조로 가는 역방향 간선이 하나라도 존재하지 않으면 절단점이 된다.-> 그럼 u의 1,2,3 서브트리 중 1이 선조로 가고 2가 1로 3이 2로 가면 u는 절단점인가? -> 아니..

트라이문자열 집합을 트리 형태로 저장하는 자료구조다.각 노드에 26개의 알파벳 노드를 배열로 저장한다. int toNumber(char ch) { return ch - ‘A’; }struct TrieNode { TrieNode* children[26]; bool terminal; TrieNode() : terminal(false) { memset(children, 0, sizeof(children)); } ~TrieNode() { // destructor 소멸자 for(int i=0; i insert(key + 1); // key+1은 내 다음 문자의 포인터 가르킴 } } TrieNode* find(const char* key) { // ke..

여러 최적화 방법이 있겠지만 내가 배운 최적화 3가지 작성 1. find에서 수장 지정하면서 재귀당연하게 사용하고 있는 방법 int find(int x) { return u[x] u[x] 에 내가 찾은 수장을 지정하면서 복귀한다.  2. 합치는 연산 uni 최적화트리의 높이를 저장하는 rank 배열을 하나 더 만들고 트리가 낮은 집합을 큰 집합 아래로 가게 한다만약 크기가 같다면 rank를 +1 한다 이러면 find 시에 최악에 O(n)을 피할 수 있음 if(rank[u] > rank[v]) swap(u, v);parent[u] = v;if (rank[u] == rank[v]) ++rank[v];  3. 집합의 크기를 음수로 저장하기 유니온파인드 -1로 두고 수장은 음수 이면서 집합의 크기를 담기 ..

세그먼트 트리세그먼트 트리 = 구간의 어떤 결과를 트리 노드에 저장해놓는 자료구조 형태 세그먼트 트리 = 구간 트리 =  꽉 찬 이진 트리-> 배열로 표현하는 것이 효율적이다.-> i번째 노드의 왼쪽, 오른쪽 자손은 각각 2*i, 2*i +1이 된다  다양한 형태의 문제를 세그 트리로 풀어나갈 수 있다.구간의 최소값, 구간의 최대값, 구간 합, 구간의 최소치 두개, 정렬된 배열에서 구간의 최대 출현 빈도 구간의 최대 출현 빈도는 노드를 다음과 같이 응용 가능하다.단순히 왼쪽, 오른쪽 자식의 결과 중 최대값을 취해서 만들 수 있으면 좋겠지만왼 : {1,1,1,2,2} , 오 : {2,2,3,3,3} 이면 합치는 데에 정보가 더 필요하다.각 구간의 양쪽 끝 구간의 숫자와 빈도를 같이 저장하여 합치는 데에 사..

Z[i] : s의 i 부터의 substring == s의 prefix 가 되는 최대 길이 Z 배열 :문자열 s의 Z배열 z[i]는 s[i]에서 시작하는 부분 문자열이면서 s의 prefix이기도 한 가장 긴 문자열의 길이를 담는 배열이다.이전에 구한 정보들을 최대한 활용해서 O(n)에 Z배열을 구할 수 있다.  문자열 ABCABCABAB인 경우 Z 배열ABCABCABABx005002020  vector z_function(const string &s) { int n = s.size(); vector z(n); z[0] = n; int L = 0, R = 0; for (int i = 1; i   prefix과 일치하는 substring 중 가장 긴 substring의 인덱스 l,r..

LCA 구현하는 과정을 최대한 간단하게 정리해본다. LCA 는 가장 가까운 공통 조상을 찾는 알고리즘인데, 두 노드에서 한 칸씩 이동하며 찾을 수도 있지만 2의 n제곱 칸씩 이동하며 찾는 방법도 가능하여 시간을 많이 단축할 수 있다. 먼저 필요한 자료구조는 다음과 같다. - depth[node] : node의 루트 노드로부터의 깊이, lca에서 두 노드의 깊이 차이를 구할 때 필요 - parent[node][k] : node의 2^k 번째 부모의 노드 번호, lca에서 두 노드의 공통 조상을 찾을 때 필요 과정은 다음과 같다. 1. dfs() 로 depth[node] 와 parent[node][0] (직계 부모)를 구한다. 2. build() 로 parent[node][1..maxlog] 를 구한다. k..

DP와 메모이제이션 개념 동적 계획법 (dp) - 복잡한 문제를 작은 부분 문제(subproblem)으로 쪼개어, 각 부분 문제의 최적해를 계산하여 중복 계산을 피하면서 전체 문제의 최적해를 찾는 알고리즘 설계 기법. 전체 문제의 하위 부분 문제의 답으로부터 전체의 답을 구하는 방법. 메모이제이션 - 중복 계산을 피하기 위해 계산 결과를 따로 저장해놓는 기법. dp 에서 사용되는 기법 중 하나이다. dp에 포함되는 개념. DP의 2가지 주요 요소 1. Optimal Substructure (최적 부분 구조) : 하위 문제의 최적해로부터 전체 문제의 최적해를 구할 수 있음. 2. Overlapping sub-problems (겹치는 부분 문제) : 동일한 부분문제가 여러번 반복적으로 해결되는 현상. 메모이..