트리 체인 분할을 이용한 알고리즘 구현 및 응용
개요
트리 체인 분할은 트리를 여러 체인으로 나누어 선형 자료구조를 활용할 수 있도록 하는 기법이다. 이 중 가장 널리 사용되는 방식은 Heavy-Light Decomposition(HLD)이다.
다음과 같은 개념들을 정의한다:
무거운 자식: 특정 노드의 모든 자식 중 서브트리 크기가 가장 큰 자식
가벼운 자식: 무거운 자식을 제외한 나머지 자식들
무거운 간선: 부모와 무거운 자식을 ...
7월 14일 21:25에 게시됨
트리 DP와 비트마스크 DP 문제 풀이
P1352 상사 없는 파티
트리에서 인접한 노드를 동시에 선택할 수 없는 상황에서 최대 가중치 합을 구하는 문제입니다.
상태 정의: val[node][0/1] - 현재 노드를 포함하지 않는 경우(0) 또는 포함하는 경우(1)의 하위 트리 최대값
점화식:
val[node][1] = weight[node] + Σ val[child][0] (현재 노드를 선택하면 자식들은 선택 불가)
val[node][0] = Σ max(val[child][0], ...
7월 3일 21:12에 게시됨
NCPC 2018 문제 풀이 노트
2018년 노르딕 대학생 프로그래밍 콘테스트(NCPC 2018)의 문제들을 정리한 풀이 노트입니다. 각 문제의 핵심 아이디어와 구현 방식을 다룹니다.
A. 개구리 탈출
n마리의 개구리가 우물에 빠졌습니다. 각 개구리는 점프력, 체중(하부 지지 한도), 신장을 가지며, 서로를 밟고 올라가 우물을 탈출해야 합니다. 최대 몇 마리가 탈출할 수 있는지 구하는 문제입니다.
지지 한 ...
6월 9일 17:09에 게시됨