본문 바로가기

분류 전체보기

 (145)
백준 25545 - MMST (C++) 문제 문제 링크 BOJ 25545 - MMST 문제 요약 모든 간선의 가중치가 다른 무향 연결 그래프가 주어진다. 이 그래프의 $MMST$를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 200,000$ $N - 1 ≤ M ≤ 500,000$ $-10^9 ≤ C_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 최소 스패닝 트리(minimum spanning tree) 풀이 얼핏 잘못 보면 삽질하기 쉬운 문제인데, $mst$의 본질을 안다면 굉장히 쉬워진다. "모든 간선의 가중치가 다른 무향 연결 그래프가 주어질 때," 위 조건을 유의한 채 얻을 수 있는 정보를 나열하면 다음과 같다. $M == N - 1$일 때는 $MMST$가 존재할 수 없다. 반대로 $N..
백준 27945 - 슬슬 가지를 먹지 않으면 죽는다 (C++) 문제 문제 링크 BOJ 27945 - 슬슬 가지를 먹지 않으면 죽는다 문제 요약 $N$개의 정점을 잇는 $M$개의 간선 정보가 주어진다. $1$일차부터 매일 노점에 들려야 할 때, 버틸 수 있는 가장 긴 날의 수를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^5$ $N - 1 ≤ M ≤ min(5 * 10^5, {N\choose 2})$ $1 ≤ t_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 그래프 이론(graphs) 분리 집합(disjoint_set) 풀이 모든 요리 학원에 다닐 수 있도록 $N - 1$ 개의 길을 고른다고 한다. 이 대목에서 유사 $mst$ 문제임을 눈치 챘다면 문제는 쉬워진다. 날짜가 $1$일차부터 시작하므로..
백준 16453 - Linhas de Metrô (C++) 문제 문제 링크 BOJ 16453 - Linhas de Metrô 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $Q$개의 쿼리에 대해 그에 맞는 답을 출력하자. 제한 TL : $2$ sec, ML : $512$ MB $5 ≤ N ≤ 100,000$ $1 ≤ Q ≤ 20,000$ 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할(heavy-light decomposition) 세그먼트 트리(segment tree) 느리게 갱신되는 세그먼트 트리(lazy propagation) 풀이 쿼리 내용은 간단하다. $Q : $ 트리 위 두 가지 경로가 주어질 때, 겹치는 정점의 수 ? 이는 $LCA$ $+$ $case$ $work$ 로 해결 하거나, 트리..
백준 27953 - 공룡 게임 (C++) 문제 문제 링크 BOJ 27953 - 공룡 게임 문제 요약 $N$개의 장애물을 $2$가지 행동을 이용해 넘어야 한다. 각 행동마다 그에 따른 패널티를 받을 때, 모든 장애물을 넘기 위한 최소 패널티를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 5,000$ $1 ≤ A, B, X, Y, T_i ≤ 10^9$ $S_i ∈ {1, 2, 3}$ $T_i < T_j$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 만약 이 문제 의 향기를 맡았다면 정답이다. $dp[p][q]$ : 마지막으로 점프, 슬라이딩을 한 장애물이 각각 $p, q$ 일 때 남은 장애물들을 넘기 위한 최소 패널티. 구체적으로, 임의의 장애물 $k$를 점프로 극복 하려면 $S[k]$ 가 홀수이고 $T[k..
백준 2618 - 경찰차 (C++) 문제 문제 링크 BOJ 2618 - 경찰차 문제 요약 $2$차원 맵에서 $w$개의 사건이 발생한다. 두 대의 경찰차가 사건을 순차적으로 해결할 때, 두 대의 경찰차가 이동하는 거리의 합을 최소로 하는 경로를 찾아보자. 제한 TL : $1$ sec, ML : $128$ MB $5 ≤ N ≤ 1,000$ $1 ≤ W ≤ 1,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 플래티넘 $dp$계의 수문장같은 바이블 문제이다. 결국 매 시점마다 변하는 상태는 경찰차들의 위치 뿐이다. 이에 따라 다음과 같이 정의를 내려보자. $dp[p][q]$ : 각 경찰차의 마지막으로 해결한 사건 번호가 각각 $p, q$일 때 이동하는 거리 합의 최솟값. 이런 문제는 사실 위처럼 점화식 정의를 내리기까지가 문제이지 막상 정..
백준 27453 - 귀엽기만 한 게 아닌 한별 양 (C++) 문제 문제 링크 BOJ 27453 - 귀엽기만 한 게 아닌 한별 양 문제 요약 가장 최근 지나온 $3$ 개 이하 칸에 있는 불상사의 개수 합이 $K$ 이하가 되게 이동하려 한다. 학교에서 집으로 가는 최단 거리를 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N, M ≤ 1,000$ $0 ≤ K ≤ 27$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 풀이 우선 불상사 합이 $K$ 를 넘는지에 대한 여부는 이전 위치의 정보를 들고 있으면 간단히 처리할 수 있다. 방문 처리에 있어서 다소 까다로워 보일 수 있는데, "방향에 대한 방문 처리를 하자" 라는 생각이 들었다면 이미 문제를 다 푼 것이나 다름 없다. 구체적으..
백준 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) 풀이 여기 에서 다룬 문제의 하위호환 격인 문제다. 이 문제 역시 경로에 대한 구간 쿼리를 빠..

티스토리툴바