그냥 하는 노트와 메모장

* 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가..

* 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..

조금 짜증나는 백트랙킹 문제였다. 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..

i번째 엘리베이터를 수식으로 나타낸다면 첫 위치를 그리고 몇칸씩 이동할 수 있는지를 로 표현한다면 i번째 엘리베이터가 갈 수 있는 곳은 아래를 만족하는 모든 층에 갈 수 있다. 하지만 최고층이 N이기 때문에 y는 최대 N까지 밖에 갈 수 없다. 따라서 엘리베이터에 따라 k의 최대값이 달라진다. 모든 엘리베이터를 수식으로 두고, 서로 다른 두 엘리베이터에 대해 i에서 j로 갈 수 있는지를 판단한다. 만약 i 엘베에서 j 엘베로 갈 수 있다면 간선을 연결해준다. 이 때 간선을 연결해줄 알고리즘이 매우 까다롭다. 두 수식에 대해서 만족하는 해와 최대층 N에 대해서 처리를 해줘야하기 때문이다. 우선 두 수식을 아래처럼 나타낸다. 이제 꼴로 나타냈으니 수식의 해가 정수해이기 위해선(정수해인 이유는 엘베에 대해 한..

A에서 B로 갈 수 있는 모든 경로의 차의 수 최대값은 최대 유량으로 충분히 가능하다. 하지만 또 하나가 있는게 이 중에서도 한 경로만 사용했을 때, 최대값을 구해서 앞서 구한 모든 경로의 차의 최대값과 한 경로의 차의 수 최대값의 비율을 계산하라고 한다. 단순 최대유량 문제만 내기엔 부족했나보다. 편의상 A에서 B로 가는 모든 경로의 차의 수 최대값을 X라고 하고, 한 경로의 차의 수 최대값을 Y라고하면 구하고자 하는 값은 Y/X가 된다. X는 단순 최대 유량으로 구해서 계산하며 Y는 backtracking으로 정의하여 계산한다. Y를 구할 때, 기저 사례는 B를 만날 때까지고, 재귀를 돌며 방문했던 정점은 다시 방문하지 않도록 한다. 재귀의 반환값은 현재 정점에서 방문 가능한 정점 중에서 차를 최대한..

완전 그래프에 관한 문제다. 크기가 K인 그래프 내의 clique(클릭) 중에서 구성된 정점의 번호가 제일 작은 것을 찾으려고 한다. 입력 데이터의 규모가 작으니 하나하나 접근해나가며 완전 그래프를 만들 수 있는지 없는지 판단하는 백트래킹 재귀 함수를 만들었다. 재귀 호출하기 전에, for문으로 번호가 작은 친구부터 탐색하도록 한다. 마찬가지로 재귀 내에서도 번호가 작은 친구를 찾도록 유도하여 구성된 정점의 번호가 작은 클릭을 찾을 수 있다. 재귀 함수의 기저 사례는 현재 구성된 완전 그래프의 크기 p와 찾아야 하는 완전 그래프의 크기 k와 같으면 true를 반환..

다소 까다로운 문제다. 문제 내용을 읽으면 우선 트리를 떠올리게 되는데, 문제에 맞는 트리의 속성을 적자면 아래와 같다. 1. 이진 트리다. 2. 자식이 하나만 있는 노드는 없으며, 자식이 있다면 무조건 2개의 자식을 갖는다. 하지만, 트리는 아니다. 이는 훼이크고, 그냥 단순 그래프이나, 노드에 순서성에 대해 트리형태처럼 보일 뿐이다. 정확히는 DAG(Directed acyclic graph)를 나타낸다. 따라서 나는 세 단계를 거쳐 AC를 받게 됐다. 1. MLE 2. TLE 3. AC (만약 단순 솔루션만 보고 싶다면 기본 아이디어 이후, 3.으로 바로 넘어가길 바란다.) * 기본 아이디어 그래프를 배열로 구현하고, 문자열에 대한 것은 string, map을 사용하여 배열에 대한 위치값(또는 포인터..