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++ 풀이를 정리합니다.

[Algorithm] C++ 백준 17642번 : Dynamic Diameter

가중 무향 트리에서 간선 가중치가 바뀔 때마다 지름을 출력한다. 센트로이드 분할과 지연 전파 세그트리로 업데이트를 O((log n)^2)에 처리하고, 각 센트로이드에서 두 서브트리 최댓값 합으로 전역 지름을 유지하는 정해 구현을 정리한다.

[Algorithm] C++ 백준 17955번 Max or Min

원형 배열에서 한 칸을 골라 인접 세 수의 최소/최대로 바꾸는 연산으로 모든 값을 x로 만드는 최소 시간을 구한다. 배열에 x가 없으면 불가능(-1). 인접 쌍마다 (min+1..max-1)에 1을 더하는 차분 누적으로 ‘그룹 수’를 집계하고, 시작점을 한 칸 회전한 두 번의 집계를 취해 중복을 보정한다. 정답은 (n - cnt[x]) + max(groups1[x], groups2[x])로 계산한다. O(n + m).

[Algorithm] C++ 백준 17973번 : Quadrilaterals

백준 17973 Quadrilaterals를 회전 스윕과 대각선 카운팅으로 해결합니다. 모든 대각선에 대해 반평면 점수의 곱으로 기본 점수를 합산하고, 최소 넓이 사각형은 4개 후보만 검사하여 __int128 연산으로 오버플로 없이 안정적으로 판정하는 C++ 풀이를 정리합니다.

[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++ 백준 18473번 : Fast Spanning Tree

BOJ 18473 Fast Spanning Tree는 인덱스가 작은 간선부터 조건을 만족할 때만 연결하는 과정을 효율적으로 복원하는 문제입니다. DSU(Union-Find)와 small-to-large 병합, 부족분 절반 기준의 watcher, 전역 후보 우선순위 큐를 이용해 O(m log m) 내에 기록된 간선 인덱스 시퀀스를 재현하는 C++ 구현과 핵심 아이디어를 정리했습니다.

[Algorithm] C++ 백준 18586번 : Salty Fish

트리의 각 노드 사과를 모두 먹되, 카메라가 보는 구간(p(x,k))의 변화를 막기 위해 일부 카메라를 매수(비용 c)하거나 일부 정점을 포기하는 문제를 최소 컷으로 환원한다. 거대한 일반 네트워크 대신 트리 구조를 활용해 dp(map<depth,sum>)을 small-to-large로 병합하고, 카메라별 커버 가능한 가장 깊은 depth부터 잔여 유량을 소모해 Max-Flow=Min-Cut을 암시적으로 계산, 전체 사과 합 − 유량으로 최대 수익을 구한다. 시간복잡도는 O((n+m) log n)으로 테스트케이스 합 n,m ≤ 10^6에서도 빠르게 동작한다.

Algorithm BOJ JOI

[Algorithm] C++ 백준 18855번 : Treatment Project

JOI 2019/2020 Day4 C, 백준 18855 Treatment Project의 정해 구현. 프로젝트들을 정점(정점 비용)으로 보고 시간-구간 제약을 불등식으로 변환해 간선을 정의, 시작(L=1)에서 종료(R=N)까지 정점 비용 최단경로를 다익스트라로 구한다. 간선 전개는 T별로 정렬해 세그트리로 한 번씩만 활성화하여 전체 O(M log M)에 해결한다.

[Algorithm] C++ 백준 31403번 : A + B - C

백준 31403 A + B - C 문제를 Python과 C++로 풀이합니다. 숫자로 계산하는 A + B - C와 문자열을 이어붙인 뒤 int로 변환하여 C를 빼는 연산의 차이를 예제와 함께 설명하고, 빠른 입출력 코드, 복잡도, 테스트 팁까지 간결하게 정리했습니다.

[Algorithm] C++ 백준 3419번 : Racing Car Trail

백준 3419 Racing Car Trail을 격자 그래프의 이분 그래프로 모델링해 Hopcroft–Karp 최대 매칭과 Dulmage–Mendelsohn 도달성으로 각 시작 칸의 승패(A/B)를 판정합니다. O(E√V) 매칭과 O(V+E) 마킹으로 빠르게 처리하며, 구현 디테일과 복잡도까지 정리.

[Algorithm] C++ 백준 3444번 : Robotic Sort

백준 3444 Robotic Sort는 로봇 팔이 연속 구간을 뒤집는 연산만으로 샘플을 안정적으로 오름차순 정렬하도록 P1..PN을 출력하는 문제입니다. Implicit Treap로 현재 위치 계산과 구간 뒤집기를 O(N log N)으로 처리한 C++ 풀이.

[Algorithm] C++ 백준 3527번 : Jungle Outpost

BOJ 3527 Jungle Outpost 문제를 반평면 교집합(HPI)과 이분탐색으로 해결. k개의 연속 정점 제거에도 항상 보호되는 HQ가 존재하는지 공집합 여부로 판정하고, 가장 큰 k를 찾아 k+1을 정답으로 출력하는 실전 C++ 구현과 핵심 아이디어 정리.

[Algorithm] C++ 백준 7907번 : Bytean Road Race

Bytean Road Race(백준 7907)을 동/남 방향 격자 DAG로 모델링해 두 정점 p, q를 모두 지나는 경로 존재 여부를 O(1)로 판별하는 C++ 풀이. 동우선·남우선 위상정렬 두 랭크 비교와 O(N+M) 전처리로 빠르고 안정적인 질의 응답을 제공합니다.

[Algorithm] C++ 백준 8235번 : Prefixuffix

백준 8235 Prefixuffix는 접두사와 접미사의 회전 동치 최대 길이를 구하는 문자열 문제입니다. 두 포인터와 롤링 해시(모듈러)로 T=A+B+X+B+A 구조를 O(n)에 찾아 C++로 구현하고, 경계 처리와 충돌 안정성까지 설명합니다.