Tags

5 pages

시간-복잡도

[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++ 백준 18438 번 : LCS 5

백준 18438 LCS 5는 최대 7000 길이의 두 문자열에 대해 LCS의 길이와 실제 수열을 모두 출력해야 하는 문제입니다. 4MB 메모리 제한 때문에 전형적인 2차원 DP 테이블을 저장할 수 없으므로, O(nm) 시간에 O(min(n,m)) 메모리만 사용하는 Hirschberg 알고리즘으로 안전하게 복원합니다. 전방·후방 1차원 DP, 분할 지점 선택, 경계 처리와 빠른 입출력까지 반영한 C++ 구현과 복잡도 분석을 제공합니다.
[Algorithm] C++ 백준 18438 번 : LCS 5