[Algorithm] C++/Python 백준 16404번: 주식회사 승범이네 - 서브트리 갱신·점 질의

회사 트리에서 직원 i와 그 하위 전체의 이익/손해를 일괄 반영하고 단일 직원의 잔액을 즉시 조회하는 문제입니다. 오일러 투어로 서브트리를 구간화하고 펜윅 트리 차분으로 구간 덧셈·점 질의를 O(log N)에 처리해 1초 제한을 안정적으로 통과합니다.

Algorithm Graph

[Algorithm] C++/Python 백준 16901번: XOR MST

XOR 가중치 완전그래프의 MST를 비트 최상위부터 그룹을 나누는 분할정복과 이분 트라이로 계산합니다. 각 레벨에서 교차 간선 비용을 2^b + 하위 최소 XOR로 구해 전체 비용을 누적합니다. 구현 포인트와 코너 케이스, C++·Python 코드와 정당성 근거까지 정리했습니다.

Algorithm Number Theory

[Algorithm] C++/Python 백준 16998번: Mod World

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

Algorithm Greedy

[Algorithm] C++/Python 백준 17169번: Eat Economically - 그리디 O(N log N)

2N개의 메뉴에서 점심·저녁 가격이 다를 때 i쌍(점심 i, 저녁 i)을 중복 없이 골라 총 비용을 최소화하는 문제. 잔여 그래프 관찰을 바탕으로 매 단계 3가지 증분 케이스만 비교하는 O(N log N) 그리디로 모든 i의 정답을 한 번에 계산한다.

Algorithm Graph

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

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

[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로 둔 뒤 최소 비용 최대 유량으로 두 경로의 포탄 수 합을 최솟값으로 구합니다.