그냥 하는 노트와 메모장

* BOJ 1765 - The Gangs (닭싸움 팀 정하기, https://www.acmicpc.net/problem/1765) [ 분류 - BFS, DFS/ DSU/ Hashing ] 이분 그래프가 여러개 생길 수 있는 구조를 생각하자. 조건에 따르면 특정 Component A에 대해 A의 적은 단 하나 밖에 존재하지 않는다. 따라서 자신의 적을 저장할 자료구조(Hashing)와 친구를 저장할 자료구조(인접 행렬 및 리스트/ DSU)를 정해야 한다. * 풀이 친구를 저장할 때는 인접 행렬 및 리스트로 저장하는 것은 꽤 간단하다. 하지만 적을 저장할 때는 어떻게 해야 할까? 이분 그래프이기 때문에 적을 단 하나만 저장한다. 이를 루트로 두고, 들어오는 데이터에 따라 자신의 적을 읽어들여, 적과 적을 이..

* BOJ 3964 - 팩토리얼과 거듭제곱 (https://www.acmicpc.net/problem/3964) [분류 - Mathematics/ GCD/ Sieve of eratosthenes ] 으음.. 생각해야할 부분이 굉장히 많은 문제다. 사실 어떻게 풀어야하겠다는 접근 자체는 다소 간단하다. 하지만 이 과정에서 발생할 수 있는 Overflow를 까다롭게 다뤄야 풀 수 있다. * 접근 방식 1. n!이 k^i에 나누어 떨어지기 위해서는 k^i = GCD(n!, k^i)이어야 한다. 2. 최대 공약수의 후보를 산출하기 위해서 k^i는 lg(k)의 시간이 걸리는 반면 n!은 lg(n!)이 걸린다. k^i가 lg(k)인 이유는 i제곱꼴은 k의 약수의 승수에 i를 곱하면 되기 때문. 따라서 후보를 추출하..

* BOJ 1103 - 게임 (https://www.acmicpc.net/problem/1103) [ 분류 - DFS/ Dynamic programming ] 여러분이 이 문제가 그래프임을 알았다고 가정하고 정리해보자. 1. 동전은 (0,0) 에서 시작한다. 2. 동전이 있는 지점에 있는 숫자만큼 상하좌우로 이동할 수 있다. 3. 구멍 H에 들어가거나 보드 밖으로 나가는 것도 동전을 움직이는 것으로 간주한다. 따라서 (0,0)부터 시작해서 상하좌우로 움직일 수 있는 곳의 최대치로 이동한다. 이는 memoization으로 구현할 수 있다. 하지만 무한번 움직일 수도 있는데, 바로 사이클이 생기는 경우다. 사이클이 하나라도 생긴다면 그 안에서 계속 움직일 수 있기 때문에 -1을 출력해줘야 한다. 따라서 me..

* BOJ 2981 - 검문 (https://www.acmicpc.net/problem/2981) [ 분류 - GCD ] 수학 개념이 필요한 문제다. 주어지는 N개의 수를 정렬한 수열의 결과를 a1, a2, ..., an 이라 하자. 임의의 정수 M으로 나눴을 때 수열의 나머지를 m라고 할 때, 수식을 아래처럼 나타낼 수 있다. 이에 대해 근접한 원소끼리 차이를 정리해보면, ... 서로 다른 두 원소 차이에 대해 "약수"로 M이 들어가 있는 것을 확인할 수 있다. 따라서 이 차이에 대해 최대공약수를 구하여 그것의 약수를 모두 출력하면 된다. - 코드 #include #include #include using namespace std; int gcd(int p, int q) { if (q == 0) ret..

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

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

분류 - [ 오일러 경로 ] 전형적인 문제다. 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가..

조금 짜증나는 백트랙킹 문제였다. unsigned long long 범위를 벗어나지 않기 위해서는 곱셈과정을 직접 구현해야 한다. 그렇지 않으면 10자리 수에 대한 세제곱 수를 구할 때, 무조건 overflow가 발생한다. 기본 아이디어는 다음과 같다. 일의 자리에 대해서 생각을 해보자. 어떤 한자리 수 세제곱을 하면 숫자 k(0

그래프 이론 + dp 문제의 다소 신기한 문제라 포스팅한다. i가 3이상인 구간에 대해서 아래의 공식이 성립한다. 아래 그림을 보자. 먼저 dp[i-1]을 설명한다. i이지만 i->k가 아닌 경우 > 0 k로 가는 경우는 없이 세는 것이다. i이고 i->k인 경우 > 마찬가지로 k의 후보는 0~i-1이므로 총 i개, k에 대해 i를 연결하고 i에 대해 k를 연결하면 나머지 i-2개에 대해 재배정이 되지 않도록 하는 방법의 수는 dp[i-2]가 된다. 따라서 i*dp[i-2]가 된다. 이 이후로 사이클 3개, 4개에 대해서 다루지 않는 이유는 이미 dp[i-1]에 포함되어 있기 때문이다. k가 i를 가리키고 있는 와중에 나머지 i-1개의 정점들 간의 재배정되지 않는 경우 안에 이 것이 포..

재밌는 문제라 포스팅하고자 한다. 연속된 숫자 1,5,10 이라고 한다면 심어야할 나무는 1보다 작은 위치 또는 10을 넘어가는 위치에 심을 순 없다. 따라서 1-5 간격과 5-10 간격이 다르기 때문에 각 구간에 나무를 심어야되는데, 그 간격을 정해보는 것에 포커싱을 맞춰보자. 1-5 간격은 4, 5-10 간격은 5다. 따라서 2도 3도 4,5 모두 간격으로 둘 수 없다. 따라서 1간격으로 나무를 심을 수 밖에 없다. 반면 1,5,11 이라고 가정해보자. 1-5 간격은 4, 5-11 간격은 6이 된다. 따라서 2간격만큼 나무를 심어줄 수 있다. 모든 구간에 대해 같은 간격으로 나눠져야하기 때문에 최대공약수를 이용해 구한다. 모든 간격에 대해 최대공약수를 구하면 그것을 나눈 값 - 1로 답을 구할 수 있..

BOJ 2479 - 경로찾기 문제를 먼처 푸는 것을 추천합니다. ====================================================== 해밍 경로에서 차이가 1인 것끼리 경로가 될 수 있다는 것은 문제에 나와있다. 즉, 그래프 상의 A,B 해밍코드가 연결되기 위해서는 A^B 결과의 1인 비트가 반드시 한 개여야 한다는 것이다. 그래프를 구성한 뒤, 해밍 코드 1번부터 시작하는 BFS를 구성하여 trace할 배열을 따로 설정하여 저장해주기만 하면 된다. 문제는 간선을 잇기 위한 작업인데, 가능한 서로다른 A,B 쌍에 대해 간선을 알아보기 위한 시간복잡도는 O(N^2 K)다. K를 없애고 일반 정수로 한다고 하더라도 (A^B 결과의 log2하는 등), O(N^2)라서 시간이 초과된..

우선 ax+b꼴을 예측하기 위해선 적어도 세 개의 숫자가 필요하다. 따라서 N이 1일 때와 N이 2일 때를 따로 처리해주자. 1. N = 1 무조건 답은 'A'다. 다음 숫자를 예측할 (a,b) 짝이 너무 많다. 2. N = 2 만약 두 숫자가 같다면 다음 숫자도 같은 숫자가 된다. 만약 다르다면 (a,b) 짝이 너무 많아서 'A'가 답이 된다. 3. N > 2 ax+b 꼴을 예측하기 위해 첫 세 숫자에 대해 a와 b를 fix 시킨다. 그 다음 그 fixed a,b를 가지고 모든 연속된 두 숫자에 대해 만족하는지 알아보기만 하면 된다. 수열에서 첫 숫자가 x라면 두 번째 수가 y, 다시금 두 번째 수가 x로서 feedback되므로 이 구조를 눈여겨 보자. ax+b가 모든 연속된 두 숫자에 대해 만족하기 ..

BOJ 2624 문제를 먼저 푸는 것을 추천합니다. ============================================================ 이 문제 역시 동전 바꿔주기 문제와 완전 동일하다. 단, 소수가 추가됐긴 했지만, 이는 에라스토테네스의 체로 구할 수 있다. 각 사탕에 대해서 hashing을 해줘야하며(몇 번째 사탕인지 등), 이는 map또는 vector, array 해싱으로 처리할 수 있다. 기본적인 아이디어는 캔디 종류 하나씩 처리를 해나가며 처리한다. 현재 처리해야 하는 캔디가 k번째 캔디라면 이전에 처리된 0부터 500000까지(50*10000) 가능한 가격에 대해 k번째 캔디의 가격을 더한다. 더할 때도, 같은 캔디가 여러개 있을 수 있으므로, k번째 캔디의 수가 cn..