본문 바로가기

Problem Solving/Baekjoon Online Judge (Platinum)

 (58)
백준 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..
백준 24520 - Meet In The Middle (C++) 문제 문제 링크 BOJ 24520 - Meet In The Middle 문제 요약 $N$개의 마을이 트리 형태로 주어지고 $Q$개의 약속이 마을 쌍의 형태로 주어진다. 각 약속마다, 두 마을에서 정확히 같은 거리만큼 떨어진 마을의 위치를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 10^5$ $1 ≤ w ≤ 10^9$ 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) 최소 공통 조상 (lowest common ancestor) 희소 배열 (sparse_table) 풀이 $dist[x]$ : 루트로부터 $x$까지의 거리. $dp[x][y]$ : $x$의 $2^y$번째 부모 정점. 라고 할 때 $O(NlogN)$의 전처리를 통해 어떤 두..
백준 29261 - 소수 세기 (C++) 문제 문제 링크 BOJ 29261 - 소수 세기 문제 요약 소수 $P$가 주어진다. 아래의 과정을 반복할 때, 지워진 수를 포함하여 한별이가 소수를 적는 최대 횟수를 구해보자. 칠판에 적힌 수 중, $p_1 + p_2 + 1$$($단, $p_1, p_2$는 소수$)$ 꼴로 표현되는 수가 있으면 그러한 수 중 하나를 골라 지우고, 대신에 $p_1$과 $p_2$를 적는다. 만약 고른 수에 대해서 가능한 $(p_1, p_2)$ 쌍이 여러 개 있으면 그런 쌍 중 하나를 고른다. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ P < 3,000,000$ 알고리즘 분류 수학 (math) 정수론 (number_therory) 소수 판정 (primality_test) 풀이 식에서 $1$을 제하면 골드..
백준 25549 - 트리의 MEX (C++) 문제 문제 링크 BOJ 25549 - 트리의 MEX 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $mex(i)$의 정의가 아래와 같을 때, $mex(1), mex(2), ... mex(N)$을 출력하자. $mex(i)$ : $i$번 정점을 루트로 하는 서브 트리의 정점에 적혀 있지 않은 수 중에서 가장 작은 음이 아닌 정수. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N ≤ 200,000$ 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) 트리를 사용한 집합과 맵 (tree _ set / map) 작은 집합에서 큰 집합으로 합치는 테크닉 (smaller_to_larger) 풀이 어떤 정점의 서브트리에 포함되는 $v_i$들은 집합을 통해 쉽게 ..
백준 29447 - Выборы (C++) 문제 문제 링크 BOJ 29447 - Выборы 문제 요약 길이 $N$의 수열과 $Q$개의 구간 쿼리가 주어진다. 각 쿼리마다, 해당 구간에서 가장 많이 등장하는 수가 몇 번 등장했는지 출력하자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 100,000$ $1 ≤ a_i ≤ 10^9$ 알고리즘 분류 오프라인 쿼리 (Offline Query) 좌표 압축 (Coordinate_Compression) mo's (mo's Algorithm) 풀이 BOJ 13548 - 수열과 쿼리 6 을 풀어 봤다면 이 문제역시 푼 거나 다름 없다. 단지 차이점은, $1 ≤ a_i ≤ 10^9$ 라는 것. 하지만 이 역시 $N ≤ 100,000$ 임에 따라 좌표 압축을 해주면 되기 때문에, ..
백준 28433 - 게리맨더링 (C++) 문제 문제 링크 BOJ 28433 - 게리맨더링 문제 요약 길이 $N$의 수열이 주어질 때, 이 수열을 원하는 개수의 연속된 구간으로 나누어 각 구간의 합을 계산한다. 이때, 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과하도록 할 수 있을까$?$ 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 2*10^5$ $-10^9 ≤ N_i ≤ 10^9$ $1 ≤ T ≤ 10^4$ 입력에서 주어지는 $N$의 합은 $2*10^5$를 넘지 않는다. 알고리즘 분류 그리디 알고리즘(greedy) 풀이 다음의 일반적인 두 사항은 관찰을 통해 쉽게 알아낼 수 있다. 연속된 음수는 반드시 하나로 합치는 것이 최선이다. 연속된 양수는 반드시 별개로 보는 것이 최선이다. 이를 바탕으로 풀이를 ..
백준 13038 - Tree (C++) 문제 문제 링크 BOJ 13038 - Tree 문제 요약 $1$ $x$ $y$ : 정점 $x$부터 정점 $y$까지 이르는 경로의 길이를 출력한다. $2$ $x$ : 정점 $x$를 제거한다. 이때, 정점 $x$의 자식들은 $x$의 부모 정점으로 전이된다. $N$개의 정점으로 이루어진 트리와 위와 같은 $Q$개의 쿼리가 주어진다. $1$번 쿼리가 주어질 때마다 그에 맞는 답을 출력하자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^6$ 반드시 올바른 트리가 입력으로 주어지며, 트리의 루트$(1)$는 제거되지 않음이 보장된다. 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할 (heavy-light decomposition..

티스토리툴바