[Algorithm] C++ 백준 15768번 - Duathlon

APIO 2018 Duathlon(백준 15768) 문제를 Tarjan의 이중연결요소(BCC)와 Block-Cut Tree로 모델링하고, 보수계산으로 ‘불량’ 삼중쌍을 합산해 전체 경우에서 빼는 O(N+M) C++ 풀이를 정리합니다. 스택 기반 간선 추출, 서브트리 원소수 집계, 절단점-블록 기여 계산, 64비트 오버플로 주의, 샘플 검증과 빌드/실행 방법까지 포함.

Algorithm BOJ Computational-Geometry UCPC 2018

[Algorithm] C++ 백준 15939번 쉬운 최단경로

UCPC 2018 B(BOJ 15939) 쉬운 최단경로 문제 풀이. 두 점의 위치(외부/내부)에 따라 3가지로 분기. 내부-내부는 선분 교차 대각선 수와 각자 외부로 나가는 비용 합 중 최솟값을 O(N)로 계산하고, 내부 판정은 O(log N)로 최적화한다.

[Algorithm] C++ 백준 16041번 : Double Clique

백준 16041 Double Clique를 스플릿 그래프 특성으로 환원해 정렬된 차수 누적 합 등식(sum_S−s(s−1)=2m−sum_S)으로 분할 크기 s를 찾고, 제거·추가·교환 경우의 수를 합산해 1e9+7로 정답을 출력하는 C++ 풀이.

Algorithm BOJ Tree DP

[Algorithm] C++ 백준 16191번 : Utilitarianism

트리에서 서로 인접하지 않는 k개의 간선을 골라 가중치 합을 최대로 만드는 문제. 라그랑주 최적화(λ)로 k-제약을 벌점으로 흡수하고, 노드별 상태 DP(A/B)로 F(λ)=max∑(w-λ)와 선택 간선 수를 O(n)에 계산, λ에 대한 단조성을 이용해 이분 탐색 후 F(λ)+λk의 최소값으로 정답을 복원한다.

[Algorithm] C++ 백준 1659번 : 수 (Hard)

백준 1659 수 (Hard): S∪T 병합 정렬 뒤 약한 연결(최근접 반대 타입)과 균형 구간 강한 매칭 비용(|∑S−∑T|)을 결합한 선형 DP로 최소 총비용을 구한다. 시간 O(n+m), 메모리 O(n+m)인 C++ 구현과 핵심 아이디어를 함께 정리한다.

[Algorithm] C++ 백준 17439번 : 꽃집

가격 오름차순 N개의 꽃을 최대 K개 구간으로 연속 분할하여 ∑(구간합×구간길이)을 최소화. 추가 비용 C를 이분탐색(Alien’s trick)하고 교점 1개 성질을 이용한 단조 큐 최적화로 O(N log N log X) 해법과 C++ 구현을 정리한다.

[Algorithm] C++ 백준 17442번 : 삼분 그래프

평면 그래프에 두 수직선 x=A, x=B를 그어 그래프를 삼분할할 때 조각 수를 구한다. 오일러 공식 ΔC=ΔV−ΔE+ΔF와 듀얼 그래프로 각 면의 x-범위를 구해 2D 질의로 ΔF(잘리는 면 수)를 세고, ΔE는 간선 교차수 누적으로 계산한다. 외부 면을 제외해 정확히 세며, 전체는 O((N+M)logN + Qlog^2N)로 처리하는 C++ 풀이.

[Algorithm] C++ 백준 17474번 : 수열과 쿼리

백준 17474 수열과 쿼리 26: 구간에 X로 chmin을 적용하고 구간 최댓값/합을 질의하는 문제. Segment Tree Beats로 (max, second max, count, sum)을 유지하여 chmin을 빠르게 처리하고, 질의는 O(log N)로 응답하는 C++ 구현을 정리합니다.

[Algorithm] C++ 백준 17517번 : Parklife

BOJ 17517 Parklife는 교차하지 않는 다리들을 라미나(중첩) 구간 트리로 변환한 뒤, 자식 DP의 볼록한 차이 수열을 small-to-large로 합치고 노드 가중치를 삽입(슬로프 트릭)해 k=1..N의 최댓값을 O(N log^2 N)에 구하는 C++ 풀이를 정리합니다.

[Algorithm] C++ 백준 17625번 : 고압선

백준 17625 고압선 문제를 회전 스윕(Rotating Sweep Line)으로 해결합니다. 모든 (i,j)쌍의 평행/수직 이벤트를 각도 정렬하여 인접 스왑만으로 순서를 유지하고, 수직이등분선과 선분 양측의 인접 점을 이용해 거주지점까지의 직선거리의 최솟값을 최대화하는 최적의 고압선 값을 안정적으로 구하는 C++ 풀이를 정리합니다.