Algorithm Graph

[Algorithm] C++/Python 백준 3640번: 제독 - 최소 비용 최대 유량

1에서 v까지 두 전함이 서로 다른 경로로 출발해 목적지 v에서 다시 만나야 합니다. 출발·도착을 제외한 정점/간선 겹침을 금지하기 위해 정점 분할로 정점 용량을 1로 제한하고, 1과 v만 2로 둔 뒤 최소 비용 최대 유량으로 두 경로의 포탄 수 합을 최솟값으로 구합니다.

Algorithm Graph

[Algorithm] C++/Python 백준 3683번: 고양이와 개 - 투표 최대 만족

고양이 선호(C×D)·개 선호(D×C) 투표를 분리해 충돌 간선으로 이분 그래프를 만들고, 최대 매칭으로 최소 제거 수를 구합니다. 코니그 정리로 정당성을 보이고 Hopcroft–Karp로 O(E√V) 내에 해결합니다. 구현·엣지 케이스까지 정리했습니다.

Algorithm Graph

[Algorithm] C++/Python 백준 5250번: 최단 경로들

BOI 2012 ‘최단 경로들’. 다익스트라 2회와 최단경로 DAG에서 구간 후보를 만들고, 우선순위큐 스윕으로 각 경로 간선 폐쇄 시 a→b 대체 최단거리를 O(m log n)으로 계산합니다.

Algorithm Graph

[Algorithm] C++/Python 백준 8202번: Conspiracy (스플릿 그래프)

POI 2010/2011 ‘Conspiracy’를 스플릿 그래프 인식 정리로 해결합니다. Hammer–Simeone 차수 조건으로 분할 가능 여부를 판정하고, 기준 분할에서 단일 이동과 교환 스왑 규칙으로 모든 유효 분할 수를 O(n^2)로 계산합니다. 엣지·완전 그래프 등 코너 케이스와 정당성 근거, 구현 포인트까지 제공합니다.

[Algorithm] C++/Python 백준 8227번: Cloakroom

시점 m에 a≤m, b>m+s인 물건만 선택 가능. 이 집합에서 합이 정확히 k가 되는지 비트셋 부분합 DP로 판정한다. 질의를 B=m+s로 그룹화해 m 오름차순으로 아이템을 추가하며 정답을 빠르게 계산한다.

Algorithm Graph

[Algorithm] C++/Python 백준 8872번: 빌라봉

가중 무방향 그래프의 각 연결요소에서 지름과 반지름을 구한 뒤, 길이 L의 간선을 N−M−1개 추가해 전체 지름을 최소화한다. 해답은 기존 지름과 r1+L+r2, r2+2L+r3 후보의 최댓값으로 결정된다. 구현, 정당성, 복잡도, 코너 케이스까지 정리.

Algorithm Geometry

[Algorithm] C++/Python 백준 8885번: Pirate Chest - 수면 상승 고려 최대 체적

상자가 밀어낸 물로 수면이 R=(A·H)/(m·n)만큼 상승할 때, 윗면이 수면 아래에 엄격히 위치하도록 최대 부피 V=A·H를 구한다. 세로 슬라이딩 최소+단조 스택으로 A, H를 빠르게 계산.

Algorithm Geometry

[Algorithm] C++/Python 백준 9244번: 핀볼 - 스위프 라인

선분이 서로 교차하지 않는 핀볼 보드에서 x=x0로 공을 떨어뜨릴 때, 선분을 만난 뒤에는 더 낮은 끝점으로 흘러 다시 수직 낙하합니다. 스위프 라인과 활성 집합으로 각 선분 하단에서 바로 아래 선분을 연결해 흐름 그래프를 만든 뒤, 시작 x에서 최상단 선분부터 따라 내려가 O(N log N)으로 최종 x좌표를 구합니다. 정수 기하 비교로 오차 없이 안전하게 구현합니다.

Algorithm Dynamic Programming

[Algorithm] C++ 백준 13263번 : 나무 자르기

증가하는 높이 a와 감소하는 비용 b의 단조성을 활용해 점화식 dp[i]=min_{j<i}(dp[j]+b[j]*a[i])의 하한선을 직선 하포로 관리하고, CHT(단조 큐)로 O(n) 시간에 계산합니다. 교차 지점 비교와 128비트 연산으로 오버플로를 방지하며 구현 포인트와 정당성을 간명히 정리했습니다.

Algorithm Dynamic Programming

[Algorithm] C++ 백준 1648번: 격자판 채우기

2x1 도미노로 N×M 격자를 빈칸 없이 채우는 경우의 수를 9901로 계산. 열 너비 W를 최소로 두고 상태압축 비트마스크 DP로 스캔하며 수평/수직 배치 전이를 수행한다. 마스크 불변식으로 정당성을 보이고, 시간/공간 복잡도와 구현 포인트, 엣지 케이스(N·M 홀수=0)까지 정리했다.