Tags

57 pages

Tree

[Algorithm] C++/Python 백준 18123번: 평행우주

각 별자리는 s≤30의 트리로 주어집니다. 위상(동형)만을 비교하므로 번호를 무시하고 트리 중심에서 AHU 문자열 정규형을 만들어 대표값을 구한 뒤, 두 중심일 땐 사전순 최소를 택해 중복을 제거합니다. 서로 다른 정규형의 개수가 한 우주에 공존 가능한 별자리 최대 수가 됩니다. 전체 별 수 합 ≤1e6 조건에서 선형에 가깝게 처리되어 안전합니다.
[Algorithm] C++/Python 백준 18123번: 평행우주

[Algorithm] C++ 백준 12736번 : Fireworks

백준 12736 Fireworks(APIO 2016)는 스위치-연결점-폭약으로 이루어진 트리에서 모든 폭약의 폭발 시각을 같게 만들기 위해 도화선 길이를 조정하는 최소 비용을 구하는 문제입니다. 볼록 함수(slope trick) 기반 트리 DP와 small-to-large 우선순위 큐 합병으로 O((N+M) log^2(N+M))에 해결합니다. 구현 핵심은 기울기 변화 지점을 우선순위 큐로 관리하고, 간선 통과 시 upperize 연산으로 기울기와 절편 변화를 반영하는 것입니다. 안전한 64-bit 정수 사용과 서브트리 크기 기준 정렬로 상수 시간을 줄여 AC를 얻습니다.
[Algorithm] C++ 백준 12736번 : Fireworks

[Algorithm] C++ 백준 18586번 : Salty Fish

트리의 각 노드 사과를 모두 먹되, 카메라가 보는 구간(p(x,k))의 변화를 막기 위해 일부 카메라를 매수(비용 c)하거나 일부 정점을 포기하는 문제를 최소 컷으로 환원한다. 거대한 일반 네트워크 대신 트리 구조를 활용해 dp(map<depth,sum>)을 small-to-large로 병합하고, 카메라별 커버 가능한 가장 깊은 depth부터 잔여 유량을 소모해 Max-Flow=Min-Cut을 암시적으로 계산, 전체 사과 합 − 유량으로 최대 수익을 구한다. 시간복잡도는 O((n+m) log n)으로 테스트케이스 합 n,m ≤ 10^6에서도 빠르게 동작한다.
[Algorithm] C++ 백준 18586번 : Salty Fish

[Algorithm] C++/Python 백준 16978번 : 수열과 쿼리 22

백준 16978번 문제는 여러 버전의 수열 상태에서 구간 합 쿼리와 값을 갱신하는 쿼리를 빠르게 처리해야 합니다. 이를 위해 영속적 세그먼트 트리(Persistent Segment Tree)를 활용하여, 각 업데이트마다 새로운 버전을 효율적으로 관리하며, 원하는 시점의 구간 합을 O(log N)에 계산할 수 있습니다. 본 글에서는 문제의 요구사항, 제한 사항, 데이터 구조의 원리와 구현 방법을 상세히 설명합니다.
[Algorithm] C++/Python 백준 16978번 : 수열과 쿼리 22

[Algorithm] C++/Python 백준 12928번 : 트리와 경로의 길이

백준 12928번 트리와 경로의 길이 문제는 N개의 노드와 정확히 S개의 길이가 2인 단순 경로를 갖는 트리의 존재 여부를 판별하는 수학+DP 문제입니다. 각 노드의 차수 분배와 경로 수식 변형을 통해 조건을 수식화하고, N과 S가 작으므로 다이나믹 프로그래밍을 활용해 차수 배치가 충족되는지를 탐색합니다. 수학적 귀납 및 조합 원리를 바탕으로 효율적인 검사를 수행하는 것이 핵심입니다.
[Algorithm] C++/Python 백준 12928번 : 트리와 경로의 길이