Problem Solving/Baekjoon Online Judge (Diamond) (17) 썸네일형 리스트형 백준 24124 - 高速道路 (Highway) (C++) 문제 문제 링크 BOJ 24124 - 高速道路 (Highway) 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 이 트리에서는, 간선 $e$가 정점 $u, v$를 이을 때 $weight_{uv}$와 $weight_{vu}$가 다를 수 있다. 어떤 $e$에 대해 번호가 작은 정점에서 큰 정점으로 향하는 방향을 상행, 반대를 하행이라고 하자. 이때, 다음 두 쿼리를 수행하는 프로그램을 작성해보자. $I$ $r$ $s$ $t$ : $r$번 간선의 상행 소요 시간을 $s$, 하행 소요 시간을 $t$로 수정한다. $Q$ $x$ $y$ : $x$번 정점에서 $y$번 정점에 도달하는 총 소요 시간을 출력한다. 제한 TL : $4$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^5$ $1 ≤ Q ≤.. 백준 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).. 백준 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) 풀.. 백준 20132 - Parity Constraint Minimum Spanning Tree (C++) 문제 문제 링크 BOJ 20132 - Parity Constraint Minimum Spanning Tree 문제 요약 $N$개의 정점과 $M$개의 간선으로 이루어진 무향 그래프가 주어진다. 이 그래프의 스패닝 트리에서, 비용이 홀수인 최솟값과 짝수인 최솟값을 구헤보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 100,000$ $1 ≤ M ≤ 300,000$ $1 ≤ w_i ≤ 1,000,000,000$ 알고리즘 분류 자료 구조(data structures) 그래프 이론(graphs) 그래프 탐색(graph traversal) 최소 스패닝 트리(minimum spanning tree) 최소 공통 조상(lowest common ancestor) 희소 배열(sparse tabl.. 백준 1626 - 두 번째로 작은 스패닝 트리 (C++) 문제 문제 링크 BOJ 1626 - 두 번째로 작은 스패닝 트리 문제 요약 $V$개의 정점으로 이루어진 무향 그래프가 주어진다. 이 그래프의 '두 번째로 작은 스패닝 트리'를 구해보자. 제한 TL : $2$ sec, ML : $128$ MB $1 ≤ V ≤ 50,000$ $1 ≤ E ≤ 200,000$ $0 ≤ E_w ≤ 100,000$ 알고리즘 분류 자료 구조(data structures) 그래프 이론(graphs) 트리(trees) 최소 스패닝 트리(minimum spanning tree) 최소 공통 조상(lowest common ancestor) 희소 배열(sparse table) 풀이 이 문제 를 풀어 보았는가 ? 비슷하면서, 다르기도 하다. 위 문제는 $LCA$ $with$ $Sparse$ $T.. 백준 13518 - 트리와 쿼리 9 (C++) 문제 문제 링크 BOJ 13518 - 트리와 쿼리 9 문제 요약 N개의 정점으로 이루어진 트리가 주어진다. Q개의 쿼리에 대한 답을 출력해보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 100,000$ $1 ≤ Q ≤ 100,000$ $1 ≤ E_w ≤ 1,000,000$ 알고리즘 분류 트리(trees) 최소 공통 조상(lowest common ancestor) 오일러 경로 테크닉(euler_tour_technique) 오프라인 쿼리(offline_queries) mo's(mo's algorithm) 풀이 예제를 예시로 들고, 트리를 그려보자. 그럼 대략 위와 같은 모양으로 그려볼 수 있는데, 이때 $1$부터 $ETT$를 돌려보며 기록 순서를 작성해보면 다음과같이 써볼 수 .. 백준 25078 - Software Package Manager (C++) 문제 문제 링크 BOJ 25078 - Software Package Manager 문제 요약 $n$개의 정점으로 이루어진 트리와 $q$개의 쿼리가 주어진다. 각 쿼리를 알맞게 처리해보자. 제한 TL : $1$ sec, ML : $1024$ MB $7 ≤ n ≤ 100,000$ $5 ≤ q ≤ 100,000$ 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할(heavy-light decomposition) 오일러 경로 테크닉(euler_tour technique) 세그먼트 트리(segment tree) 느리게 갱신되는 세그먼트 트리(lazy propagation) 풀이 여기 에서 다룬 문제의 하위호환 격인 문제다. 이 문제 역시 경로에 대한 구간 쿼리를 빠.. 백준 17429 - 국제 메시 기구 (C++) 문제 문제 링크 BOJ 17429 - 국제 메시 기구 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $Q$개의 쿼리에 대해 그에 맞는 처리를 진행하자. 제한 TL : $3$ sec, ML : $1024$ MB $1 ≤ N ≤ 500,000$ $1 ≤ Q ≤ 100,000$ 모든 출력에 있어서 $2^{32}$로 나눈 나머지 값을 출력 한다. 알고리즘 분류 자료구조(data structures) 트리(trees) 세그먼트 트리(segment tree) 느리게 갱신되는 세그먼트 트리(lazy propagation) heavy-light 분할(heavy-light decomposition) 오일러 경로 테크닉(euler_tour_technique) 풀이 이 문제 를 풀어 보았는가 ? 이번 문제는 위 .. 이전 1 2 3 다음