그냥 하는 노트와 메모장

[ 분류 - GCD ] 재밌는 문제다. 이 문제는 팩토리얼과의 GCD를 구하는 문제다. GCD에 요소가 될 수 있는 후보를 먼저 생각해보자. n!은 우선 냅두고.. k를 생각하자. n!은 너무 값이 클 수 있기 때문이다. 그렇다면 GCD 후보는 k의 약수로 요약할 수 있다. 또한 k를 소인수 분해하여 정리하면 아래와 같이 표현할 수 있다. 따라서 후보는 1부터 n을 곱했을 때, 그 값에서 소수 p1부터 px까지로 포함된 최대의 수로 나타낼 수 있다. 즉, 로 표현할 수 있다. 따라서 를 아래 수식처럼 표현할 수 있다. 접근법을 알았으니, 이제 n!에 대해 gx 값을 구하는 방법을 알아보자. 간단하게 나누기로 특정 소수의 px의 승수를 쉽게 알아낼 수 있다. 만약 px=2이라면 아래처럼 표현할 수 있다. ..

* BOJ 11097 도시계획 (https://www.acmicpc.net/problem/11097) [ 분류 - SCC(Strongly connected components) ] 다소 까다로운 문제? 였다. 반면 접근 방식이 매우 여러가지라 아래 해설도 그 중 하나라고 봐주시면 되시겠당 :) 문제가 물어보는 것은 플로이드의 결과라고 생각할 수 있는 인접 행렬이 주어졌을 때, 이를 구성할 수 있는 가장 적은 도로를 쓰는 도로망을 구성하는 것이다. 그리고 일방통행 도로이기 때문에 방향 그래프인 것을 알 수 있다. 이 문제를 "최대한 도로를 지우는" 과정으로 볼 수 있다. 인접 행렬에서 지울 수 있는 도로를 모두 지워야 최소 크기의 도로망을 구성할 수 있기 때문이다. 임의의 정점에 대해서 생각해보자. 정점 ..

* 강한 연결 요소(SCC, Strongly connected components) 문제들 Topological sort, dynamic programming, DSU 등 다양한 알고리즘과 연결하여 풀 수 있는 문제들을 Random하게 소개해 보겠당. 1. 백준 온라인 저지 1-1. Strongly connected component(https://www.acmicpc.net/problem/2150) 기본적인 SCC 문제다. 모든 SCC를 저장하고 이를 정렬하여 출력하면 된다. - 코드 #include #include #include #include using namespace std; int min_v(int a, int b) { return a < b ? a : b; } vector adj; int ..

* 강한 연결 요소 (SCC, Strongly connected components) 방향 그래프 상에서 두 정점 u와 v에 대해 양 방향으로 가는 경로가 모두 있을 때 두 정점은 같은 SCC에 있다고 말한다. if vertex u has paths to vertex v and also v has paths to u, either u and v are involved in same SCC. 이 SCC 집합은 하나의 component 내에 여러개가 생길 수 있다. 아래 그림을 보면 하나의 component에 대해 3개의 SCC가 있음을 직관적으로 알 수 있다. SCC의 특성 중 하나는 SSC 간의 방향 그래프를 그려보면 DAG가 나온다는 것이다. 이는 연역적으로 정리가 가능하다. 1. 현재 구성할 수 있는..

* BOJ 9376 - Jailbreak(탈옥) (https://www.acmicpc.net/problem/9376) nextq에 대한 다른 방식이 있어서 기억하고자 포스팅하고자 한당 문제는 그다지 어렵진 않다. 문제를 다소 변경해보자. 밖에서 문을 열어 주는 과정, 죄수1이 여는 과정, 죄수2가 여는 과정으로 문제를 분할하고, 세 사람이 한 점에서 모인다고 생각해보자. 세 사람이 그 한 점에 최소한의 문을 열고 오게끔 구성을 한다면 답을 충분히 도출할 수 있다. 주어진 지도 안에서 만나는 경우가 없을 수도 있으므로, 바깥 테두리를 설정해주면 된다. 보통 나는 이런 step by step bfs(내가 임의로 지은 이름임) 문제는 q와 nextq를 두어 문제를 해결하지만, solution에 다른 방식으로 ..

* 이분법(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한 방법이다. ..

분류 - [ 오일러 경로 ] 전형적인 문제다. N-M+1 개의 수열에 대해 앞 정점(M개에서 맨 뒤만 빠진 배열)과 뒷 정점(M개에서 맨 앞만 빠진 배열)을 이어주고, 이 그래프에서 오일러 회로 및 경로를 찾는다(입력에 따라 회로인지 경로인지 판단해야 한다).다만 좀 까다롭다는 점은 정점이 담아야하는 것이 배열이기 때문에 이를 유의하여 소스를 짜주시면 되겠다. 좀 더 쉬운 버전의 문제로는 Tanya and Password (http://codeforces.com/contest/508/problem/D)이 문제는 http://coloredrabbit.tistory.com/37?category=729843에 해설도 적어놓았으니, BOJ 1591 수열 복원 문제가 어렵다면 코드포스 문제를 먼저 풀어보는 것을 ..

분류 - [ 오일러 회로 ] 도로를 두 개 이상을 가지는 도시는 반드시 두 레스토랑을 갈 수 있어야 한다. 도로가 없거나 하나 이하의 경우는 생각하지 않기 때문에, 이 명제를 좀 변형 시켜보자. "도로를 두 개 이상을 가지는 도시에 대해 두 레스토랑을 보장하기 위해서 A 레스토랑이 있는 도로의 수를 Acnt, B 레스토랑이 있는 도로의 수를 Bcnt라고 할 때, Acnt는 Bcnt와 같아야 한다." 이것이 의미하는 바는 A와 B 레스토랑의 수를 같게 하면 명확하게 문제에서 원하는 도로를 배치할 수 있다. 따라서 A와 B를 진입/ 진출 간선처럼 생각하고, 항상 진입 간선 수=진출 간선 수가 같은 오일러 회로를 이용하여 문제를 해결한다. 단, 여기서 예외처리를 해줘야하는 점이 있다. 우선 Component가..

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

* Mike and Fish (http://codeforces.com/contest/547/problem/D) 뭐.. 문제 내용을 보면 생선을 싫어하는 곰, 마이크가 파란 생선과 빨간 생선을 2차원 좌표에 있는 바구니(?)에 하나씩 넣고자 한다. 또한 하나의 x축이나 y축에 대해 파란 생선 개수와 빨간 생선 개수의 차이가 1 이하로 만들기 위해 생선들을 각 좌표에 어떻게 배치시킬 것인지를 묻는 문제다. [분류 - Eulerian circuit/ Euler circult/ 오일러 회로/ 오일러 서킷] b clr[a] += (acc % 2 ? 1 : -1), clr[b] += (acc % 2 ? 1 : -1); x = a % 2 ? b : a; y = a % 2 ? a : b; ans[pool[make_pa..

* 오일러 회로 * 백준 온라인 저지 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..

* Branch 참고 URL - https://git-scm.com/book/ko/v2/Git-%EB%B8%8C%EB%9E%9C%EC%B9%98-%EB%B8%8C%EB%9E%9C%EC%B9%98%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80 Git은 데이터를 일련의 스냅샷으로 기록한다.커밋하면 Git은 현 Staging Area에 있는 데이터의 스냅샷에 대한 포인터, 저자나 커밋 메시지 같은 메타 데이터, 이전 커밋에 대한 포인터 들을 포함하는 커밋 개체(커밋 Object)를 저장한다. 이전 커밋 포인터가 있어서 현재 커밋이 무엇을 기준으로 바뀌었는지를 알 수 있다. 최초 커밋을 제외한 나머지 커밋은 이전 커밋 포인터가 적어도 하나씩 있고 브랜치를 합친 Merge 커밋..