Algorithm Graph

[Algorithm] C++/Python 백준 17399번: 트리의 외심

세 정점의 외심은 세 정점까지의 거리가 같으면서 그 거리가 최소가 되는 정점입니다. LCA·깊이로 세 경로의 교점 S를 찾고, 두 작은 팔 길이의 동일성과 큰 팔과의 짝수 차이를 이용해 존재·위치를 판정합니다. BFS+Binary Lifting로 O((N+Q)logN)에 해결합니다.

Algorithm Tree

[Algorithm] C++/Python 백준 18123번: 평행우주

각 별자리는 s≤30의 트리로 주어집니다. 위상(동형)만을 비교하므로 번호를 무시하고 트리 중심에서 AHU 문자열 정규형을 만들어 대표값을 구한 뒤, 두 중심일 땐 사전순 최소를 택해 중복을 제거합니다. 서로 다른 정규형의 개수가 한 우주에 공존 가능한 별자리 최대 수가 됩니다. 전체 별 수 합 ≤1e6 조건에서 선형에 가깝게 처리되어 안전합니다.

Algorithm Graph

[Algorithm] C++/Python 백준 18485번 : Nine Judges

심사위원 선호 순위로 유도된 다수결 비교(토너먼트)에서 해밀토니안 경로를 구성해 상위 p개를 취해 ‘plausible set’을 찾는다. 분할-정복 머지와 다수결 비교로 O(n·k log k), 구현은 pos 테이블로 O(n·k) 메모리. 엣지/동률 없음(다수결 임계), 입력 정합성·인덱스·출력 형식 점검.

Algorithm Graph

[Algorithm] C++/Python 백준 2316번: 도시 왕복하기 2 - Dinic, Node Splitting

정점 방문 제한을 정점 분할로 모델링하고, 1·2번은 무제한·나머지는 1의 용량을 부여합니다. 양방향 도로는 양방향 간선(∞)로 만들고 Dinic으로 최대 유량을 구해 왕복 가능한 최대 횟수를 계산합니다. 구현 포인트와 엣지 케이스까지 정리했습니다.

Algorithm String

[Algorithm] C++/Python 백준 33651번: Vandalism

UAPC에서 일부 문자를 삭제해 얻은 s가 주어지면, 빠진 문자들을 원래 순서대로 복원합니다. 두 포인터로 UAPC와 s를 한 번만 훑어 불일치만 수집해 O(|UAPC|) 시간, O(1) 공간에 안정적으로 해결합니다.

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 DP

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

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