본문 바로가기

전체 글

 (141)
백준 25606 - 장마 (C++) 문제 문제 링크 BOJ 25606 - 장마 문제 요약 $N$일동안 비가 내린다. 장마 시작 $t$일 후 내리는 비는 상자에 $a_i$만큼 물을 채운다. 보관된 상자에선 매일 $M$만큼의 물이 증발할 때, 아래 두 쿼리를 수행하는 프로그램을 작성하자. $1$ $t$ : 장마 시작 $t$일 후, 모든 상자에 들어있는 물의 양의 합은 무엇인가$?$ $2$ $t$ : 장마 시작 $t$일 후, 모든 상자에서 증발하는 물의 양의 합은 무엇인가$?$ 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^5$ $1 ≤ M, a_i ≤ 10^4$ 알고리즘 분류 누적 합 (prefix_sum) 풀이 쿼리가 들어올 때마다 답을 계산하기엔 조금 귀찮아 보인다. $N ≤ 10^5$이고 각 $N_i$..
백준 23314 - Minimum Spanning Cactus (C++) 문제 문제 링크 BOJ 23314 - Minimum Spanning Cactus 문제 요약 $N$개의 정점과 이들을 잇는 무향 가중치 간선 $M$개로 이루어진 $Cactus$ $Graph$가 주어진다. 아래 쿼리를 수행하는 프로그램을 작성하자. $u$ $v$ $d$ : 정점 $u$와 정점 $v$를 잇는 간선의 가중치를 $d$로 바꾸고, 최소 신장 선인장의 비용을 출력한다. 제한 TL : $1.2$ sec, ML : $512$ MB $2 ≤ N ≤ 100,000$ $N-1 ≤ M ≤ 150,000$ $1 ≤ Q ≤ 100,000$ $-10^9 ≤ c ≤ 10^9$ 알고리즘 분류 자료 구조 (data_structures) 그래프 이론 (graphs) 이중 연결 요소 (biconnected_component)..
백준 21025 - Healthy Lifestyle (C++) 문제 문제 링크 BOJ 21025 - Healthy Lifestyle 문제 요약 $N$개의 정점과, 이들을 잇는 $M$개의 간선으로 이루어진 그래프가 주어진다. 아래의 쿼리를 수행하는 프로그램을 작성하자. $u$ $v$ : $u$에서 $v$로 가는 서로 다른 경로가 존재하면 $YES$, 존재하지 않는다면 $NO$를 출력한다. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, M, Q ≤ 10^5$ 알고리즘 분류 그래프 이론 (graphs) 이중 연결 요소 (biconnected_component) 자료 구조 (data_structures) 분리 집합 (disjoint_set) 풀이 간단히 생각해보면, 답이 $YES$인 경우는 $u, v$가 같은 사이클에 속할 때 뿐이라는 것을 알 수 ..
백준 26358, 26359 - A Prickly Problem – Black Edition (C++) 문제 문제 링크 BOJ 26359 - A Prickly Problem – Black Edition 문제 요약 $V$개의 정점으로 이루어진 $Cactus$ $Graph$가 주어진다. 스패닝 트리가 되도록 $V-1$개의 간선만을 남겼을 때, 서로 다른 모양의 트리가 존재할 수 있다. 이 스패닝 트리의 가짓수에 대해 $1,007$로 나눈 나머지를 출력하자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ V ≤ 50,000$ $1 ≤ E ≤ (3*V)/2$ 주어지는 그래프는 $Cactus$ $Graph$임이 보장된다. 입력은 여러 개의 테스트 케이스로 이루어져 있다. 알고리즘 분류 그래프 이론 (graphs) 이중 연결 요소 (biconnected_component) 선인장 (cactus) ..
백준 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)..

티스토리툴바