본문 바로가기

분류 전체보기

 (145)
백준 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$의 ..
백준 29619 - 나무나무나 심어야지 (C++) 문제 문제 링크 BOJ 29619 - 나무나무나 심어야지 문제 요약 최초 $N$개의 정점으로 이루어진 트리에서, 아래와 같은 유형으로 이루어진 $Q$개의 쿼리가 주어진다. 각 쿼리를 알맞게 처리해보자. 쿼리를 간단히 요약하자. $1$ $i$ $j$ $w$ : $i$번 정점에 $j$번 정점을 추가한다. 이때 $j$는 정점값 $w$를 가진다. $2$ $i$ : $i$번 정점을 루트로 하는 서브 트리의 모든 정점값의 합을 출력한다. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N, Q ≤ 100,000$ $0 ≤ w_i ≤ 500$ 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) 세그먼트 트리 (segment tree) 오일러 경로 테크닉 (euler_tour_..
백준 23979 - 트리의 재구성 (C++) 문제 문제 링크 BOJ 23979 - 트리의 재구성 문제 요약 $N$개의 정점으로 이루어진 트리와, 아래와같은 $Q$개의 쿼리가 주어진다. 각 쿼리의 답을 출력하자. $u$ $v$ $w$ $a$ $b$ : $u$에서 $v$로 가는 비용이 $w$인 간선을 잇고, 지웠을 때 트리가 되는 간선 중 새로 추가한 간선을 제외한 비용이 가장 큰 간선 하나를 지운다. 재구성된 트리의 $a$에서 $b$로 가는 경로의 비용을 출력한다. 제한 TL : $1$ sec, ML : $512$ MB $2 ≤ N, Q ≤ 200,000$ $1 ≤ C_i, W_i ≤ 200,000$ 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) 최소 공통 조상 (lowest common ancestor) 희소 배열 (..
백준 24889 - 통행량 조사 (C++) 문제 문제 링크 BOJ 24889 - 통행량 조사 문제 요약 $N$개의 도시가 $N$개의 간선으로 이루어져 있다. 차량 집단 $Q$개의 통행 정보가 주어질 때, 각 도로마다 지날 가능성이 있는 차량의 수를 계산해보자. 단, 통행에선 각 도시와 도로를 최대 한 번 이용하며 차량 집단이 이용할 가능성이 있는 모든 도로가 고려되어야 한다. 제한 TL : $2$ sec, ML : $1024$ MB $3 ≤ N ≤ 200,000$ $1 ≤ Q ≤ 200,000$ $1 ≤ w_i ≤ 5,000$ 연결하는 도시 쌍이 동일한 도로가 여러 개 주어지지 않고, 임의의 두 도시는 도로를 통해 서로 이동할 수 있다. 알고리즘 분류 그래프 이론 (graphs) 그래프 탐색 (graph_traversal) 트리 (trees) 최..
백준 25491 - Mexor tree (C++) 문제 문제 링크 BOJ 25491 - Mexor tree 문제 요약 $x$ $y$ $z$ : 정점 $x$와 $y$를 잇는 단순 경로 상의 정점들의 값들을 각각 $z$와 $XOR$ 연산을 시행한 값으로 바꾼다. $b_i$ : 정점 $S$와 정점 $i$를 잇는 단순 경로 상의 정점들의 값들 중에 존재하지 않는 음이 아닌 정수 중 최솟값. $N$개의 정점으로 이루어진 트리와, 각 정점의 정점값이 주어진다. 쿼리의 내용과 수열 $b_i$의 정의가 위와 같을 때, $Q$개의 쿼리를 모두 처리한 후 $b_1, b_2, ... b_N$ 을 출력하자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 300,000$ $0 ≤ a_i ≤ N$ 알고리즘 분류 자료 구조 (data_structu..

티스토리툴바