Tags

38 pages

DFS

[Algorithm] cpp-python 백준 16993번: 연속합과 쿼리 (세그먼트 트리)

길이 N(≤100,000) 수열에 대해 구간 [i,j]의 최대 연속합을 O(log N)으로 질의하는 세그먼트 트리 풀이입니다. 각 노드에 합·최대 접두/접미합·구간 최대합을 저장하고 병합 규칙으로 정답을 계산합니다. 음수 전용 구간·단일 원소·전부 음수인 경우를 안전하게 처리하며, 시간·공간 복잡도와 실수 포인트를 정리했습니다.
[Algorithm] cpp-python 백준 16993번: 연속합과 쿼리 (세그먼트 트리)

[Algorithm] cpp 백준 18227번: 성대나라의 물탱크

루트 C에서 시작하는 트리에서 "A 도시에 물 채우기"는 루트→A 경로의 각 정점 v에 깊이(v)+1 리터를 더합니다. 따라서 임의의 정점 v의 물의 양은 서브트리(v)에서 발생한 갱신 횟수 × (깊이(v)+1)로 환원됩니다. 오일러 투어로 트리를 평탄화하고 펜윅 트리(BIT)로 서브트리 구간의 갱신·질의를 처리해 O((N+Q)logN)에 해결합니다. 경계 입력과 64-bit 오버플로를 주의합니다.
[Algorithm] cpp 백준 18227번: 성대나라의 물탱크

[Algorithm] cpp 백준 24272번: 루트 노드가 많은 트리일수록 좋은 트리이다

유일 경로 트리의 간선 방향을 제어하며 ‘모든 정점에 도달 가능한 루트’의 수를 유지하는 문제입니다. Euler tour로 서브트리를 구간화하고, child→parent 제약의 교집합과 parent→child 제약의 합집합을 각각 multiset과 세그먼트 트리로 관리하여 매 쿼리 O(log N)에 정답을 계산합니다. 엣지 케이스(교집합 공집합, 전역 인터벌, 무방향 전환)까지 안정적으로 처리합니다.
[Algorithm] cpp 백준 24272번: 루트 노드가 많은 트리일수록 좋은 트리이다