Doby's Lab

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

https://www.acmicpc.net/problem/12037 12037번: Polynesiaglot (Small1) In Case #1, suppose that the only vowel is a and the only consonant is h. Then the possible valid words of length 4 are: aaaa, aaha, ahaa, haaa, haha. In Case #2 (which would not appear in the Small dataset 1), suppose that the two vowels are a a www.acmicpc.net Solved By: DP cache[i][0]: 모음으로 끝나는 길이가 i인 문자열의 개수 cache[i][0]: 자음..

https://www.acmicpc.net/problem/11525 11525번: Farey Sequence Length Given a positive integer, N, the sequence of all fractions a / b with (0 < a  b), (1 < b  N) and a and b relatively prime, listed in increasing order, is called the Farey Sequence of order N. For example, the Farey Sequence of order 6 is: 0/1, 1/6, 1 www.acmicpc.net Solved By: Euler Phi Function 이번 문제를 풀면서 페리 수열에 대해 공부해봤습니다. (..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net Solved By: DP in Tree (공부한 풀이 출처: https://hqjang.tistory.com/104) 우선 이분법적으로 생각할 수 있습니다. 어떤 노드는 2가지 상태밖에 지니지 못 합니다. 1. 일반인인 경우 2. 얼리어답터인 경우 두 가지 경우에 대해서 생각해봅시다. [일반인인 경우] 어떤 노드가 일반인이라면 자식 노드들은 전부 얼리어답터여야 합..