Doby's Lab

https://www.acmicpc.net/problem/24009 24009번: Huge Numbers The first line of the input gives the number of test cases, T. T lines follow. Each line contains three integers A, N and P, as described above. www.acmicpc.net Solved By: Exponentiation By Squaring, Number Theory 거듭제곱은 시간 단축을 위해 분할 정복을 이용했습니다. A, N, P가 주어지면 A의(N!) 제곱을 구하고, 이를 P로 나누라는 소리인데 우선, A의(N!)제곱은 N이 3이라 할 때, (((A^1)^2)^3)과 같이 정리할 ..

ll POW(ll a, ll b) { if (b == 0) {//지수가 0이면 모든 수가 1이 된다. return 1; } ll value = POW(a, b / 2); // 여기서 분할적으로 나뉘어짐 value = value * value; if (b % 2 == 0) {// b가 짝수일 때 return value; } else {// b가 홀수일 때 return value * a; } }

https://www.acmicpc.net/problem/15203 15203번: Police Station A network of hyperspace highways is built in the galaxy. Each of the highways is a one-directional corridor which connects two planets. Galactic government wants to find a planet on which a police station will be built. In order for the police to protect www.acmicpc.net Solved By: Tarjan Algorithm 각 SCC를 구성하여 SCC의 indegree를 조사합니다. inde..

https://www.acmicpc.net/problem/13059 13059번: Tourists Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will consist of an integer n (2 ≤ n ≤ 200,000) indicating the number of attractions. Each of the following n− www.acmicpc.net Solved By: LCA, Number Theory 트리가 주어지면 각 노드의 배수 노드들 사이에 노드 개수를 세는 문제입니다. 트리이..

https://www.acmicpc.net/problem/9742 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net Solved By: BackTracking 찾아야 하는 순서가 백트래킹으로 구해지는 순서 안에 있다면 결과 string에 해당 문자열을 할당해주고, 아니라면 빈 문자열을 반환하도록 아무것도 할당하지 않았습니다. #include #include using namespace std; string s; int n; int cnt; string res; bool visited[10]; void backTrac..

https://www.acmicpc.net/problem/7742 7742번: Railway The first line of the input contains the integers N and Q (in this order) separated by a single space. N is the number of cities, 1 ≤ N ≤ 100 000, and Q is the number of queries, 1 ≤ Q ≤ 2 000 000 000. For simplicity, the cities are numbered by the www.acmicpc.net Solved By: LCA 1761과 같은 문제입니다. (https://draw-code-boy.tistory.com/305) #include #..

https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net Solved By: LCA 바로 직전의 포스팅 문제 (1761)과 비슷합니다. 거리의 점화식을 사용하여 구할 수 있습니다. #include #include #include #include #define MAX 100001 #define LOG_MAX 18 #define pii pair using namespace std; int n, k; int pare..

https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net Solved By: LCA Sparse Table을 이용해 LCA만 구할 수 있었지만, 각 정점들 간의 거리 또한 Sparse Table로 parent node들을 구하듯이 거리를 구할 수 있습니다. parent를 구하는 점화식과 유사합니다. Sparse Table을 아는 상태에서 조금 더 생각해보면 충분히 나올 수 있는 점화식입니다. #include #include #include #i..