Featured image of post [Algorithm] C++/Python 백준 18485번 : Nine Judges
Algorithm Graph

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

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

Featured image of post [Algorithm] C++/Python 백준 33651번: Vandalism
Algorithm String

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

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

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

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

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

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

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

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

Featured image of post [Algorithm] C++/Python 백준 8227번: Cloakroom
Algorithm DP

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

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

Featured image of post [Algorithm] C++/Python 백준 8872번: 빌라봉
Algorithm Graph

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

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