Tags

47 pages

DFS

[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++/Python 백준 11375번 : 열혈강호

백준 11375번 '열혈강호'는 직원-작업 매칭 문제로, 이분 그래프에서 최대 매칭을 구하는 DFS 기반 알고리즘을 효율적으로 설계하는 데 중점을 둔다. 각 직원에게 한 개 작업만 배정할 수 있고, 모든 작업은 반드시 담당자를 가져야 하므로, 실제 네트워크 플로우 및 이분 매칭의 원리와 DFS 수행 로직을 이해하는 데 좋은 예제다. 본문에서는 문제 풀이 전략, 최적화 방법, 구현 시 주의점과 함께 C++ 및 Python 코드를 단계별로 설명한다.
[Algorithm] C++/Python 백준 11375번 : 열혈강호