본문 바로가기

분류 전체보기

 (145)
백준 11817 - Robots and Oil Transportation System (C++) 문제 문제 링크 BOJ 11817 - Robots and Oil Transportation System 문제 요약 $N$개의 정점으로 이루어진 그래프가 주어진다. 두 로봇이 시작 정점 $s_1, s_2$에서 임의의 단절선이 잇는 서로 다른 두 정점에 도달하려 한다. 어떤 단절선에 대해, 더 나중에 도달한 로봇을 기준으로 시간을 측정한다. 이 시간을 최대한 짧게 하도록 하는 단절선을 선택할 때, 걸리는 최소 시간을 구해보자. 제한 TL : $2$ sec, ML : $256$ MB $2 ≤ N, M ≤ 10^5$ $1 ≤ w_i ≤ 10^3$ 주어지는 그래프에 적어도 하나의 단절선이 존재함이 보장된다. 알고리즘 분류 그래프 이론 (graphs) 단절점과 단절선 (articulation) 다익스트라 (dijk..
백준 9548 - 무제 (C++) 문제 문제 링크 BOJ 9548 - 무제 문제 요약 본문에 써있는 내용을 그대로 가져와 보겠다. "그냥 단순히 문자열 조작 연산을 구현하는 문제이다. 문제 이름은 딱히 필요가 없어서 짓지 않았다." 제한 TL : $10$ sec, ML : $256$ MB $1 ≤$ 테스트 케이스의 수 $≤ 100$ $1 ≤ |S| ≤ 10^6$ $S$와 $R$은 항상 알파벳 소문자로만 구성되어 있으며, 연산의 결과로 $S$의 길이가 $10^6$을 넘어가는 경우는 없다. 출력되는 문자의 개수의 합은 모든 테스트 케이스에서 $10^6$을 초과하지 않는다. 알고리즘 분류 자료 구조 (data_structures) 문자열 (string) 로프 (rope) 풀이 문자열 조작을 효율적으로 수행할 수 있게 해주는, $rope$라는 ..
백준 18425 - Putovanje (C++) 문제 문제 링크 BOJ 18425 - Putovanje 문제 요약 $N$개의 노드로 이루어진 트리와, $N-1$개의 도로에 대한 단일, 복수 패스 비용이 주어진다. $1, 2, ... , N$번 노드를 차례로 순회할 때, 모든 노드를 순회하는 데 드는 최소 패스 비용을 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $2 ≤ N ≤ 200,000$ $1 ≤ C_1, C_2 ≤ 100,000$ 알고리즘 분류 그래프 이론 (graphs) 그래프 탐색 (graph_traversal) 깊이 우선 탐색 (dfs) 트리 (trees) 최소 공통 조상 (lowest common ancestor) 누적 합 (prefix_sum) 풀이 모든 노드를 순회하고난 뒤, 간선마다 사용된 횟수를 알고 있다고 해..
백준 23836 - 어떤 우유의 배달목록 (Hard) (C++) 문제 문제 링크 BOJ 23836 - 어떤 우유의 배달목록 (Hard) 문제 요약 $N$개의 노드로 이루어진 트리가 주어진다. 아래 두 쿼리를 수행하는 프로그램을 작성하자. $1$ $u$ $v$ : $u$번 노드부터 $v$번 노드에 이르는 경로 상에서, $i$번째로 등장하는 노드에 $i$를 더한다. $2$ $x$ : 지금까지 $x$번 노드에 더해진 값을 출력한다. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^5$ $2$번 쿼리는 최소 한 개 이상 주어진다. 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) heavy-light 분할 (heavy-light decomposition) 세그먼트 트리 (segment tree) 스택 (stack)..
백준 23006 - Truck Delivery (C++) 문제 문제 링크 BOJ 23006 - Truck Delivery 문제 요약 $N$개의 노드로 이루어진 트리가 주어진다. 각 간선들에는 하중 제한 $Li$, $Li$보다 무거운 화물이 지나갈 경우 부과하는 요금 $A_i$가 있다. 이때, 아래의 쿼리를 수행하는 프로그램을 작성하자. $C$ $W$ : $C$번 노드에서 $W$의 무게를 가진 화물을 $1$번 노드에 전달한다. 해당 날에 지불하는 요금을 $a_1, a_2, ... a_k$라 할 때 $gcd(a_1, a_2, ... a_k)$의 값을 출력한다. 제한 TL : $80$ sec, ML : $1024$ MB $1 ≤$ 테스트 케이스의 수 $≤ 100$ $2 ≤ C_j ≤ N ≤ 5 * 10^4$ $1 ≤ L_i, W_j ≤ 2 * 10^5$ $1 ≤ Q..
백준 10623 - Breadth-First Search by Foxpowe (C++) 문제 문제 링크 BOJ 10623 - Breadth-First Search by Foxpowe 문제 요약 $N$개의 노드로 이루어진 트리가 주어진다. $1$부터 $BFS$를 진행할 시 방문되는 노드의 순서대로 이동할 때, 총 이동 거리를 계산하자. 제한 TL : $2$ sec, ML : $128$ MB $1 ≤ N ≤ 10^5$ 루트 노드는 $1$이다. 알고리즘 분류 그래프 이론 (graphs) 그래프 탐색 (graph_traversal) 너비 우선 탐색 (bfs) 트리 (trees) 최소 공통 조상 (lowest common ancestor) 풀이 어려울 것 없이, 문제의 요구 사항을 그대로 구현해주면 된다. 단, $N ≤ 10^5$ 이므로 이동 거리를 나이브하게 계산할 순 없으니, $LCA$를 이용해..
백준 30092 - 슥삭슥삭 나무자르기 (C++) 문제 문제 링크 BOJ 30092 - 슥삭슥삭 나무자르기 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 아래 쿼리를 수행하는 프로그램을 작성하자. $a$ $b$ $c$ $d$ : 정점 $a$에서 $b$로 가는 최단 경로에 속한 모든 간선을 제거했을 때, 정점 $c$에서 $d$로 가는 경로가 존재하면 $YES$, 존재하지 않으면 $NO$를 출력한다. 제한 TL : $4$ sec, ML : $1024$ MB $2 ≤ N ≤ 100,000$ $1 ≤ Q ≤ 300,000$ 각 쿼리는 독립적이다. 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) heavy-light 분할 (heavy-light decomposition) 세그먼트 트리 (segment tree) 느리게 갱신..
백준 8812 - Jaś Robaczek (C++) 문제 문제 링크 BOJ 8812 - Jaś Robaczek 문제 요약 최초 $1$개의 노드만이 존재하는 상태에서, 아래 두 쿼리를 수행하는 프로그램을 작성하자. $D x$ : $x$번 노드에 새로운 노드를 연결한다. 단, $x$는 이미 존재하는 노드임이 보장된다. $J x$ : Jaś가 $x$번 노드를 향해 한 번 이동한다. 단, 최초 Jaś가 서있는 노드는 $1$번 노드이다. 제한 TL : $1$ sec, ML : $128$ MB $1 ≤$ 테스트 케이스의 수 $≤ 10$ $1 ≤ Q ≤ 10^6$ 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) 최소 공통 조상 (lowest common ancestor) 희소 배열 (sparse_table) 오프라인 쿼리 (offline_..

티스토리툴바