Featured image of post [Algorithm] cpp-python 백준 18485번 : Nine Judges
Algorithm Graph

[Algorithm] cpp-python 백준 18485번 : Nine Judges

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

Featured image of post [Algorithm] cpp-python 백준 33651번: Vandalism
Algorithm String

[Algorithm] cpp-python 백준 33651번: Vandalism

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

Featured image of post [Algorithm] cpp-python 백준 3640번: 제독 - 최소 비용 최대 유량
Algorithm Graph

[Algorithm] cpp-python 백준 3640번: 제독 - 최소 비용 최대 유량

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

Featured image of post [Algorithm] cpp-python 백준 8202번: Conspiracy (스플릿 그래프)
Algorithm Graph

[Algorithm] cpp-python 백준 8202번: Conspiracy (스플릿 그래프)

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

Featured image of post [Algorithm] cpp-python 백준 8227번: Cloakroom
Algorithm DP

[Algorithm] cpp-python 백준 8227번: Cloakroom

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

Featured image of post [Algorithm] cpp-python 백준 8872번: 빌라봉
Algorithm Graph

[Algorithm] cpp-python 백준 8872번: 빌라봉

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

Featured image of post [Algorithm] cpp-python 백준 9244번: 핀볼 - 스위프 라인
Algorithm Geometry

[Algorithm] cpp-python 백준 9244번: 핀볼 - 스위프 라인

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

Featured image of post [Algorithm] cpp 백준 13263번 : 나무 자르기
Algorithm Dynamic Programming

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

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

Featured image of post [Algorithm] cpp 백준 1648번: 격자판 채우기
Algorithm Dynamic Programming

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

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

Featured image of post [Algorithm] cpp 백준 3878번: 점 분리
Algorithm Geometry

[Algorithm] cpp 백준 3878번: 점 분리

볼록껍질과 선분 교차·포함 판정을 이용해 흰 점과 검은 점의 ‘직선에 의한 엄격 분리’ 가능 여부를 판단합니다. 접촉(점·변 포함)도 분리 불가로 처리하며, O((n+m) log(n+m))에 해결합니다.

Featured image of post [Algorithm] C++ 백준 12670번 : The Year of Code Jam (Large)
Algorithm BOJ

[Algorithm] C++ 백준 12670번 : The Year of Code Jam (Large)

격자 달력에서 파란날 행복도 4−이웃수의 합을 최대화하는 문제를 이분 격자 그래프 컷으로 환원한다. B측 보조 변수 y=1−x 변환과 Potts [x!=y] 간선, 단항 재매개화, 고정일(#, .)을 s-t 컷으로 구성해 Dinic으로 최적값을 빠르게 구한다.

Featured image of post [Algorithm] C++ 백준 12736번 : Fireworks
Algorithm BOJ

[Algorithm] C++ 백준 12736번 : Fireworks

백준 12736 Fireworks(APIO 2016)는 스위치-연결점-폭약으로 이루어진 트리에서 모든 폭약의 폭발 시각을 같게 만들기 위해 도화선 길이를 조정하는 최소 비용을 구하는 문제입니다. 볼록 함수(slope trick) 기반 트리 DP와 small-to-large 우선순위 큐 합병으로 O((N+M) log^2(N+M))에 해결합니다. 구현 핵심은 기울기 변화 지점을 우선순위 큐로 관리하고, 간선 통과 시 upperize 연산으로 기울기와 절편 변화를 반영하는 것입니다. 안전한 64-bit 정수 사용과 서브트리 크기 기준 정렬로 상수 시간을 줄여 AC를 얻습니다.