그냥 하는 노트와 메모장

[ 분류 - 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 수열 복원 문제가 어렵다면 코드포스 문제를 먼저 풀어보는 것을 ..