Algorithm Graph

[Algorithm] C++ 백준 3295번: 단방향 링크 네트워크 - 최대 매칭

단방향 링크 네트워크를 링과 선형 배열로 분해할 때의 최대 가치는 선택된 간선 수와 동일합니다. 각 정점의 진입·진출 차수를 최대 1로 제한하는 간선 선택 문제를 좌·우 파티션으로 분리한 이분 매칭으로 모델링하고, Hopcroft–Karp 알고리즘으로 O(√V·E)에 해결합니다. 구현 포인트와 코너 케이스까지 정리했습니다.

Algorithm Graph

[Algorithm] C++ 백준 3311번: Traffic - SCC 압축과 DAG 구간 전파

섬 내부 도로망은 선분 도로가 교차하지 않는 평면 그래프이므로, SCC 압축 DAG에서 각 컴포넌트가 도달할 수 있는 동쪽 경계 정점 집합은 y좌표 기준 연속 구간이 됩니다. 이를 이용해 동쪽 경계 정점(서쪽에서 실제로 도달 가능한 것만)을 y 오름차순으로 인덱싱하고, 자식 구간을 부모로 병합하는 역위상 전파로 각 서쪽 정점의 답(서쪽 정점에서 도달 가능한 동쪽 정점 수)을 O(n+m)에 계산합니다. 구현은 반복형 Kosaraju + 압축 그래프 위상정렬 기반입니다.

Algorithm DP

[Algorithm] C++ 백준 3319번: 전령들

트리의 각 도시에서 수도까지 메시지를 가장 빨리 전달하는 최소 시간을 구하는 문제입니다. 도시 i는 출발 준비 시간 S_i와 1km당 이동 시간 V_i를 가지며, 유일한 최단 경로를 따라 이동 중 중간 도시에서 다른 전령에게 넘길 수 있습니다. dp[u]를 루트까지의 거리 dist[u]를 이용해 dp[u] = S_u + V_u·dist[u] + min_{조상 x}(dp[x] − V_u·dist[x])로 정리하고, 조상 집합에 대한 직선 최소값 질의를 처리하기 위해 Li Chao Tree(선형함수 컨벡스 헐 트릭)를 트리 경로에 영속적으로 유지(퍼시스턴스)하여 각 정점에서 O(log C)에 답합니다. 64비트 정수 및 곱셈 시 128비트 캐스팅으로 오버플로를 방지합니다.

Algorithm Graph Flow

[Algorithm] C++ 백준 3611번: 팀의 난이도

팀의 난이도(같은 팀에서 일을 못하는 쌍/인원)를 최대화하는 문제는 최대밀도부분그래프와 동치입니다. r에 대해 |E(S)|-r|S|를 최대화하는 파라메트릭 최소절단을 구성하고 이분 탐색으로 r*를 찾은 뒤, 절단의 S측에서 최적 팀을 복원합니다. n≤100, m≤1000에서 안전합니다.

Algorithm Graph

[Algorithm] C++ 백준 4001번: 미노타우르스 미궁

좌·우수법(Left/Right-hand rule)으로 정의되는 두 개의 표준 경로를 계산하고, 2차원 누적합으로 직사각형 내부 경로/장애물 포함 여부를 O(1)에 판정합니다. 각 좌표별로 ‘막히는 최소 정사각형 크기’와 ‘설치 가능한 최대 정사각형 크기’를 각각 이분 탐색해 교집합이 존재하면 정답 후보로 갱신하여, 가장 작은 변의 길이와 위치를 찾습니다.

Algorithm Greedy Interval Scheduling

[Algorithm] C++ 백준 4012번: 컨벤션 센터 - 사전순 최소 해 선택

회의 구간을 최대 개수로 선택하면서 사전순(lexicographical)으로 가장 이른 해를 출력하는 문제. 시작 시각 기준 정렬, 선행 회의의 이진 점프(sparse table)로 f(l,r)를 O(log n)에 계산하고, 구간 경계 map을 유지해 포함 여부를 O(log n)에 증명·선택한다. 전체 O(n log n).

Algorithm Dynamic Programming

[Algorithm] C++ 백준 5466번: 상인

IOI 2009 상인 문제. 집 S에서 출발·복귀하며 U/D 비용으로 강을 오르내리며 시장을 방문해 이익 합을 최대로 한다. 날짜별 비내림 방문 제약을 활용해 좌/우 이동 비용을 선형식으로 흡수한 최대 변환과 같은 날 내부 양방향 스위핑 DP를 결합, 좌표압축+펜윅 트리로 O(N log N) 최적 이익을 계산한다.

Algorithm Tree

[Algorithm] C++ 백준 5820번: 경주 - 길이 K 최소 간선 경로

트리에서 길이 K인 경로 중 사용 간선 수가 최소인 것을 찾는다. 센트로이드 분해로 각 서브트리 거리 목록을 수집해 보완 거리(K−d)와 즉시 매칭하고, 터치된 거리만 관리해 O(N log N) 내 해결한다. 가중치 합 가지치기와 64비트 누적으로 안전성을 확보한다.

Algorithm Dynamic Programming

[Algorithm] C++ 백준 6171번: 땅따먹기 - 묶음 할인 최소 비용 DP+CHT

여러 직사각형 땅을 묶어 살 때 비용은 (묶음 내 최대 W)*(묶음 내 최대 H)입니다. W 오름차순 정렬 후 같은 W는 최대 H로 병합하고, 뒤에서 앞으로 보며 지배된 직사각형을 제거해 H를 단조 감소로 만듭니다. 이후 dp[i]=min(dp[k]+W[i]*H[k+1])를 단조 Convex Hull Trick으로 O(n)에 계산하며, 정수 교차 비교와 __int128 중간 연산으로 오버플로를 방지합니다.

Algorithm Greedy

[Algorithm] C++ 백준 8131번: Ploughing - 슬라이딩 윈도우

2000×2000 격자에서 합 ≤ K인 바깥 행·열만 제거하며 제거 횟수를 최소화한다. 마지막 1×L 또는 L×1 스트립 길이 최대화로 환원하고, 2D 누적합+투포인터로 O((N+M)^2) 해결. 경계 우선 그리디 핵심.