Featured image of post [Algorithm] cpp-python 백준 16998번: Mod World
Algorithm Number Theory

[Algorithm] cpp-python 백준 16998번: Mod World

p, q, n이 주어질 때 (p·i mod q)의 합을 i=1..n까지 구하는 문제입니다. 유클리드 호제법 기반 floor_sum과 주기성(서로소 시 잔여 클래스 순열)을 이용해 O(log q)로 풀며, 정당성과 경계 사례를 함께 점검합니다.

Featured image of post [Algorithm] cpp-python 백준 17399번: 트리의 외심
Algorithm Graph

[Algorithm] cpp-python 백준 17399번: 트리의 외심

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

Featured image of post [Algorithm] cpp-python 백준 18123번: 평행우주
Algorithm Tree

[Algorithm] cpp-python 백준 18123번: 평행우주

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

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))에 해결합니다.