데구리 블로그

문제 링크 2018/07/26 추가내용.참고) post-order대신 pre-order로 순회 해도 같은 효과를 볼 수 있으며, 코드를 조금 더 편하게, 더 직관적으로 짤 수 있다. pre-order로 순회하는 코드는 여기를 참고하자. 1번 정점을 루트로 하는 트리가 주어지고, M개의 질의가 주어졌을 때 다음과 같은 명령을 실행한다. 1 x꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치를 전부 XOR한 값을 출력.2 x y꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치에 각각 y를 XOR함 . 얼핏 봐선 그냥 하면 되는거 아닌가 싶겠지만 범위가 굉장히 크다.정점의 수 N과 질의의 수 M에 대해$(1\leq N \leq 100,000)$, $(1\leq M \leq ..

문제 링크https://www.acmicpc.net/problem/5214 역들을 연결하는 하이퍼튜브가 있고, 각 하이퍼튜브가 서로 연결하는 역들이 주어질 때 1번 역에서 N번 역으로 가는데 방문하는 역의 개수의 최소값을 구해야 한다. 누가 봐도 BFS문제이지만 일반적인 방법처럼 연결된 역들을 모두 그래프로 이어버리면 메모리 초과를 받게 된다. 일반적인 방법대로 풀어보자.하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M의 범위는 $1 \leq K, M \leq 1,000$이다. 하이퍼튜브 하나당 정점끼리 $K^2$개의 간선이 연결되므로 그래프의 총 간선의 개수는 최악의 경우 $O(MK^2) = 1,000,000,000$개이다. 메모리가 터질 수밖에 없다. 중복된 간선을 여러번 연결했기 때문..

문제 링크 https://www.acmicpc.net/problem/1008 두 정수 A와 B를 받아 A/B를 출력하자. 절대/상대 오차를 $10^{-9}$까지 허용하기 때문에 정확한 답을 위해 소수 10자리까지 출력한다. 정답 코드

문제 링크 https://www.acmicpc.net/problem/1005 "모든 건물을 지을 수 없는 경우는 없다."라는 조건에서 주어진 그래프가 싸이클 없는 방향 그래프(DAG)라는 걸 알 수 있다. 건물을 짓는 순서가 정해져 있으므로 위상정렬로 해결할 수 있다. 단순 BFS로는 풀기 힘들다. 본문의 예제를 단계별로 살펴보자. $x$번 건물이 완성될 때까지의 총 시간을 $d[x]$으로 표현하겠다. 아직 완성 시간을 알 수 없는 건물은 0의 값을 가진다. $step\,0)$ 초기상태이다. $n$ 1 2 3 4 $d$ 0 0 0 0 $step\,1)$ 우선 1번 건물을 먼저 지을 수 있고, 10초가 걸린다. $n$ 1 2 3 4 $d$ 10 0 0 0 $step\,2)$ 2번과 3번을 동시에 지을 수 ..

문제 링크https://www.acmicpc.net/problem/1004 맞은 사람 목록을 보면 해당 풀이보다 더 간단한 풀이가 존재하는 것 같다. 어쨌든 내 경우엔 이렇게 풀었다. 좌표평면 위의 원(행성계)들이 주어지고 출발점과 도착점이 주어졌을 때, 출발점에서 도착점으로 가는 동안 원을 뚫고 가는 횟수를 최소화해야 한다.문제에서 "행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다고 가정한다."라는 조건을 주었기 때문에 쉽게 풀 수 있다. 풀이에 앞서 '점 $X$ 또는 원$X$가 원$C$에 포함된다'라는 말을 '$X$가 $C$의 경계에 걸치거나 교차하지 않으면서, $C$ 내부에 있는 상태' 라고 하겠다. 1) 출발점이나 도착점이 여러 개의 원에 포함된다면 그 원 중에서도 작은 원은 항상 큰 원에 포..

문제 링크 https://www.acmicpc.net/problem/1003 기본적인 피보나치 문제를 모르거나 시간초과가 문제라면 http://degurii.tistory.com/14?category=755814 를 참고하자. 기존의 피보나치 함수가 $$f(n) = f(n - 2) + f(n - 1)$$ 이므로 $n$일때 호출되는 0과 1의 개수를 $[$0의개수, 1의개수$]_n$ 로 표현해서 단순히 $[i, j]_n = [i, j]_{n - 2} + [i, j]_{n - 1}$ 처럼 쓸 수 있다. 이때, $[i, j] + [x, y] = [i + x, j + y]$로 정의한다. 정답 코드

문제 링크https://www.acmicpc.net/problem/2747 피보나치 수열은 보통 점화식으로 다음과 같이 표현된다.$$f(n) = f(n-2) + f(n-1), (f(0) = 0, f(1) = 1)$$ 이를 재귀함수로 구현하면 이렇게 되고, 위의 코드에서 $n = 6$인 경우 다음 그림처럼 함수가 전개된다. 재귀함수가 $n$을 인자로 호출되면 그 함수는 $n - 1$과 $n - 2$를 인자로 함수를 호출하고, 호출된 각 함수가 계속해서 함수를 두 개씩 호출하게 된다. 결국 시간복잡도가 $O(2^N)$이므로 n 제한이 $n

문제 링크https://www.acmicpc.net/problem/1002 두 터렛의 위치 정보와 각 터렛에서 계산한 상대편 마린과의 거리가 주어질 때 마린이 있을 수 있는 위치를 출력하는 문제다.마린이 있을 수 있는 위치는 '터렛 중심으로부터 거리가 일정한 점들의 집합'이다. 즉, 원으로 볼 수 있다. 터렛이 두 대이므로 두 원끼리 겹치는 점의 개수가 답일 것이다.두 원이 어떤 상황에서 어떻게 겹치는지 알기 위해 다음 6가지 케이스를 보면 된다. 1) 어떤 원이 다른 원에 포함되지 않으면서, 두 원이 접하지 않을 때 2) 외접할 때 3) 두 점에서 만날 때 4) 내접할 때 5) 작은 원이 큰 원 내부에 있으면서, 두 원이 접하지 않을 때 6) 두 원이 같은 원일 때 이제 주어진 원들이 어떤 상태인지 판..