본문 바로가기

전체 글

 (141)
백준 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_..
백준 29811 - 지각하기 싫어 (C++) 문제 문제 링크 BOJ 29811 - 지각하기 싫어 문제 요약 애지문부터 대운동장까지 가는 경로 $N$개, 대운동장부터 ITBT관까지 가는 경로 $M$개가 주어진다. 아래의 쿼리를 수행하는 프로그램을 작성해보자. $U$ $x$ $y$ : $x$번 경로의 인구를 $y$로 바꾼다. $L$ : 애지문에서 ITBT관까지 가는 가장 빠른 경로가 $a, b$번 경로를 통해 이동할 때일 때, $a, b$를 출력한다. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N, M ≤ 100,000$ $1 ≤ Q ≤ 200,000$ 알고리즘 분류 자료 구조 (data_structures) 트리를 사용한 집합과 맵 (tree _ set / map) 풀이 먼저 주어지는 $N$개의 경로를 관리할 집합과, 나중에 ..
백준 2849 - 탭댄스 (C++) 문제 문제 링크 BOJ 2849 - 탭댄스 문제 요약 탭댄스의 안무는 $L$과 $R$로 이루어진 수열로 표현될 수 있다. 안무의 점수는 $L$과 $R$이 두 번 연속해서 나오지 않는 연속된 원소들로 이루어진 가장 긴 부분 수열의 길이로 정의된다. $Q$번의 안무가 수정될 때마다, 해당 순간의 안무의 점수를 출력하자. 제한 TL : $1$ sec, ML : $128$ MB $1 ≤ N, Q ≤ 200,000$ 가장 처음의 안무는 $L$로만 이루어져 있다. 알고리즘 분류 자료 구조 (data_structures) 세그먼트 트리 (segment tree) 풀이 BOJ 16993 - 연속합과 쿼리 와 같은 문제들을 푼 경험이 있다면 그리 어렵지 않게 문제를 풀 수 있다. 나는 세그먼트 트리의 구조체 노드에서, ..
백준 17722 - Road Development (C++) 문제 문제 링크 BOJ 17722 - Road Development 문제 요약 $N$개의 도시로 구성된 국가에 대해, $Q$개의 교통 개선 계획이 주어진다. $2$번 쿼리가 주어질 때마다 그에 맞는 답을 출력하자. 제한 TL : $2$ sec, ML : $256$ MB $2 ≤ N ≤ 100,000$ $1 ≤ Q ≤ 300,000$ 이 문제는 서브태스크 문제이다. 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) heavy-light 분할 (heavy-light decomposition) 세그먼트 트리 (segment tree) 느리게 갱신되는 세그먼트 트리 (lazy propagation) 오프라인 쿼리 (offline_queries) 분리 집합 (disjoint_set) 풀..
백준 29618 - 미술 시간 (C++) 문제 문제 링크 BOJ 29618 - 미술 시간 문제 요약 칸의 길이 $N$과 아래와 같은 $Q$개의 쿼리가 주어진다. 모든 쿼리의 처리가 끝난 후 각 칸의 상태를 출력하자. $a$ $b$ $x$ : $a$번째 칸부터 $b$번째 칸까지, 색칠되지 않은 칸을 $x$번 색으로 칠한다. 제한 TL : $0.5$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 100,000$ $1 ≤ x ≤ 10^9$ 알고리즘 분류 자료 구조 (data_structures) 트리를 사용한 집합과 맵 (tree _ set / map) 풀이 제한을 보면 당연히 나이브하게 돌 수 없다. 간단하게, $std::set$에서 색칠되지 않은 칸들을 들고 있다고 해보자. 그럼 임의의 쿼리 $a_i, b_i, x_i$에서 $a_i$의 ..

티스토리툴바