oVeron

https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net dp[i][j] : i = 순열의 나머지, j = 이룬 순열(비트마스킹) 순열의 나머지를 이용해 dp를 설계하는 것이 핵심이었다. 큰 수 나눗셈, 최대공약수(gcd), 비트마스킹 dp를 조합해야 풀 수 있었던 문제였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typ..

알고리즘/baekjoon 2023. 3. 2. 23:05

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 예제 입력 1의 첫 번째 테스트케이스를 살펴보자. 해당 테스트케이스에서 순서쌍 (3, 4)만 순위가 바뀐 쌍이라 해 보자. 이때 답은 IMPOSSIBLE이 아니다. 3과 4 사이에 끼어있는 팀이 존재하지 않기에, 3번 팀과 4번 팀의 순위를 바꿔도 영향을 받는 팀이 없기 때문이다. 이번에는 해당 테스트케이스에서 순서쌍 (2, 4)만 순위가 바뀐 쌍이라 해 보자. 이때 답은 IMPOSSIBL..

알고리즘/baekjoon 2023. 3. 2. 17:10

https://www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int N, M; vector graph[100001]; //도착 도시..

알고리즘/baekjoon 2023. 3. 2. 10:19

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 도로의 길이 역시 sparse table로 처리할 수 있다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typed..

알고리즘/baekjoon 2023. 3. 2. 09:23

https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int N, M; vector graph[100001]; int par[..

알고리즘/baekjoon 2023. 3. 1. 17:38

https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; type..

알고리즘/baekjoon 2023. 3. 1. 16:45

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int N; int par[1..

알고리즘/baekjoon 2023. 3. 1. 15:58

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 1. 가장 먼저 떠오르는 방법은 DFS를 이용해 분리된 그래프의 개수를 구하는 것이다. 하지만 각 그래프의 root를 모르기 때문에 실행하기 어려운 방법이다. 2. 각 그래프의 root를 구해야 한다는 점에서 위상 정렬을 떠올려 볼 수 있다. 사이클이 존재할 수 있으므로 SCC와 결합시켜 생각한다면 풀 수 있을 것이다. 다만 실제로 위상 정렬의 방식을 SCC와 결합해 구현하기는 힘들어서, SCC 타잔 알고리즘의 ..

알고리즘/baekjoon 2023. 3. 1. 11:13