Doby's Lab

https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net Solved By: Offline Query, Union-Find 문제를 직관적으로 처리하려면 DFS를 하는데에 있어서 쿼리의 개수까지 고려하면 O(NQ)로 시간 초과가 나옵니다. 하지만, 쿼리를 우리에게 유리하게끔 쿼리 순서를 바꾸어 Offline Query로 처리하려 한다면 문제에서 '간선을 끊어라'는 '간선을 이어라'가 되면서 Union-Find 문제가 됩니다. -> ..

https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net Solved By: KMP 주어진 광고에서 앞(접두사)과 뒤(접미사)가 얼마나 중복되는지 길이를 안다면 전체 길이에서 그 길이를 빼서 얼마큼만 광고해도 되는지 구할 수 있다. 이때 문자열 알고리즘 KMP를 사용한다. #include #include #include using namespace std; int main(){ int l; string s; cin >> l >> s; vector pattern(l + 1..

https://www.acmicpc.net/problem/13706 13706번: 제곱근 첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다. www.acmicpc.net Solved By: Binary Search 주어지는 수가 엄청 크기 때문에 Python을 이용했습니다. Python의 math 패키지에 있는 sqrt를 사용하여 문제를 풀려 했지만 연산을 해야 하는 값이 너무 커서 OverflowError가 나왔습니다. 그래서 이분 탐색을 돌려서 만족하는 값이 있으면 출력하도록 코드를 썼습니다. from math import sqrt n = int(input()) low, high = 1, n while low n): high = mid - ..

https://www.acmicpc.net/problem/14935 14935번: FA 정수 x가 FA수 라면 FA를 출력하고, 아니라면 NFA를 출력한다. www.acmicpc.net Solved By: Math 모든 수는 결국 1의 자리가 되어 '1의 자리의 어떤 수' * 1이 반복되는 것을 인지한다면 모든 수가 FA라는 것을 알 수 있다. x = input() print('FA')

https://www.acmicpc.net/problem/7501 7501번: Key Hackers often have to crack passwords for different data encryption systems. A novice hacker Bill faced such a problem one day. After performing several experiments he noticed regularity in the formation of an encryption key. He knew that a key is an odd i www.acmicpc.net Solved By: Miller-Rabin 주어진 a, b 사이에 존재하는 홀수 K에 대해 다음을 묻습니다. K^2으로 (K - 1)!을 ..

https://www.acmicpc.net/problem/17633 17633번: 제곱수의 합 (More Huge) 입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 1,000,000,000,000,000,000이다. www.acmicpc.net Solved By: Pollard's Rho, Number Theory 이번 문제는 기존에 가지고 있던 수학 지식으로는 풀 수 없었습니다. 그래서 공부를 한 뒤 풀어야 했습니다. Fermat's Two-Square Theorem Legendre's Three-Square Theorem Lagrange's Four-Square Theorem 본격적으로 문제에 들어가기 전에 문제를 읽어보면 라그랑주는 이미 자연수가 ..

https://www.acmicpc.net/problem/23832 23832번: 서로소 그래프 우석이는 심심할 때마다 그래프를 그린다. 우석이는 매달 새로운 그래프를 그리는데, 이번 달에는 서로소 그래프를 그린다. 서로소 그래프는 $1$부터 $N$까지의 번호를 가진 $N$ 개의 정점으로 이 www.acmicpc.net Solved By: Euler Phi Function 노드 N에서 나와야 하는 간선의 개수는 N이하의 양의 정수 중 N과 서로소의 개수다. 즉, EulerPhi(N)과 같다. 이를 이용하여 2 ~ N까지의 EulerPhi값들의 합을 구해주면 된다. EulerPhi를 연산하는 과정에서 overflow가 날 수도 있으므로 long long으로 선언하고 풀어준다. #include #includ..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net Solved By: DFS DFS를 선언하면서 자신이 Leaf Node인지 아닌지를 판단할 수 있는 코드가 필요했습니다. 어떤 노드의 parent 노드는 방문이 다 된 상태이기 때문에 현재 노드에서 방문할 노드가 생기면 이는 Leaf Node로 판단하게 했습니다. 방문할 노드가 있다는 것은 Child Node가 있다는 것이고 이는 Leaf Node가 아님을 뜻하기 때문입니다. 그리고, Roo..