그냥 하는 노트와 메모장

* 이분법(Bisection method) 1차원 데이터에 대해 [low, high] 구간을 지정하고, 원하는 데이터를 이분적으로 찾아가는 방식을 말한다. 여기서 low와 high는 사용자 정의 f()함수에 대해 f(low) > f(high)인 경우 low와 high를 swap 해주는 것이 더욱 깔끔하게 소스를 짤 수 있다. 즉, low = 10, high = 15, f(low) = 2, f(high) = 1 인 경우, 결과적으로 f(low)가 f(high)보다 크기 때문에 구간 [low, high]를 [15, 10]로 잡는 것이다. 방식은 iteration(순차 접근, for문)을 이용하는 방법과 while로 근사치를 추정해나가는 방식이 있다. 두 방식 중 안전한 방법은 iteration한 방법이다. ..

해당 게시글은 아래 속성에 맞춰 작성되어있습니다 :) * 무향 그래프(양방향 그래프, Undirected graph) * Cut vertex(절단점, 단절점) 절단점이란 이 점과 이어진 모든 간선을 지웠을 때 두 개 이상의 Component로 나뉘어 지는 정점을 말한다. 역방향 간선을 이용하여 DFS 한 번만에 절단점을 찾을 수 있다. DFS를 통해 DFS spanning tree를 구성하면 정점 u는 아래처럼 분류할 수 있다. 1. u가 root다 2. u가 root가 아니다. 1. u가 root다 정점 u가 root인 경우, 자식의 개수에 따라 절단점이 될 수도 있고 아닐 수도 있다. 자식이 없는 경우는 당연하고, 하나인 경우에도 root가 사라진다고 두 개의 Component로 나눠지는 것은 아니기..

* 오일러 회로 * 백준 온라인 저지 1. 오일러 회로 (https://www.acmicpc.net/problem/1199) 문제 이름부터가 오일러 회로다.. ㅎㅎ 가장 기본적인 오일러 회로를 따라가면 된다. 또한 무방향 그래프이기 때문에 방향성에 대해 확인할 필요가 없다. 기초적인 오일러 회로가 있는지 확인한 뒤, DFS를 돌리면 된다. 인접 행렬 코드 : #include #include using namespace std; int adj[1000][1000], n; vector c; void eulerianCircuit(int u) { for(int v=0;v= j) continue; addEdge(i, j, cap); } for (i = 0; i < n; i++) f &= (deg[i] && !(d..

* 오일러 서킷 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 시작점으로 돌아오기 때문에 오일러 서킷은 사이클임을 알 수 있다. * 오일러 경로 그래프의 모든 간선을 정확히 한 번씩 지나는 경로를 말한다. 시작점과 도착점이 다를뿐(오일러 경로는 사이클이 아니다), 나머지 속성은 오일러 서킷과 같다. * 오일러 서킷/경로 존재 조건 배제의 방식으로 접근한다. 반대로 오일러 서킷이 존재할 수 없는 그래프를 파악하면 된다. u = v의 경우는 오일러 서킷이고, u != v의 경우는 오일러 경로를 말한다. 1. Graph components가 두 개 이상 Components가 두 개 이상이면 한 번의 연산(사이클)이 절대로 모든 간선을 지날 수 없다. 2-1. (양/무방향 그래..

* 위상 정렬(Topological sort) 의존성이 있는 작업들이 주어질 때, 이들을 어떤 순서로 수행해야 하는지 계산할 때 필요하다. 이런 DAG의 정점을 배열하는 것을 위상 정렬이라 한다. 구현 방식은 두 가지 방식이 있다. DFS와 BFS. 1. DFS BFS와 다르게 indegree 배열이 필요가 없다. 또한 나중엔 반드시 reversing process가 필요하다. 코드 : #include vector visit, order; void dfs(int here){ visit[here] = 1; for(int there = 0; there < adj.size(); ++there) if(adj[here][there] && !visit[there]) dfs(there); order.push_back..

* DSU (Disjoint-Set Union, Union-Find 또는 상호배제 집합) DSU에 관련된 문제 중 푼 문제를 소개합니당 1. Codeforce 1-1. Serial Time! (http://codeforces.com/contest/60/problem/B) 단순히 BFS 돌려도 되지만, DSU로 풀어보고 싶어서 적용해봤다. 인접한 6 이웃에 대해 #이 아니라면 접근이 가능하다. 코드 : #include int tp[10][10][10], p[1001], s[1001]; int find(int u) { if (u == p[u]) return u; return p[u] = find(p[u]); } void merge(int u, int v) { u = find(u), v = find(v); i..