Algorithm Dynamic Programming

[Algorithm] C++/Python 백준 14869번: 요리 강좌 - DP, 슬라이딩 윈도우 최적화

연속 수강 길이 S~E, 학원 변경 비용 T, 불허용 학원 제약을 동시에 만족하는 최소비용을 구합니다. prefix sum과 단조 큐로 블록 DP를 슬라이딩 윈도우 최적화해 O(NM)로 해결, 정당성과 엣지 케이스 점검까지 담았습니다.

Algorithm Greedy

[Algorithm] C++/Python 백준 15337번: 관광열차 좌석 배치 - s1/s2 계산

정책-1(승객 자유 좌석 선택)·정책-2(운영자 일괄 배정)에서 필요한 최소 좌석 s1·s2 계산. s2는 라인 스위핑으로 최대 동시 탑승, s1은 n−endPrefix[a]−startSuffix[b]의 최댓값. [a,b) 경계·누적/접미합·빠른 I/O, 엣지·실수 포인트 점검.

Algorithm String

[Algorithm] C++/Python 백준 15338번: String Puzzle - 루트 압축 점프

길이 n(≤1e9) 비공개 문자열에 위치 고정 힌트와 구간 복사 힌트가 주어진다. 각 구간을 왼쪽으로 d만큼 당기는 함수로 모델링하고 p에서 반복 적용해 유일한 루트를 찾는다. 루트→문자 맵으로 쿼리를 O(log b)로 결정한다.

Algorithm Greedy

[Algorithm] C++/Python 백준 15773번: Touch The Sky

고도 h≤L에서만 풍선을 불 수 있고 한 번 불 때마다 D만큼 상승한다. 최대 몇 개의 풍선을 순서대로 사용할 수 있는지 구한다. E=L+D 오름차순 정렬 + 최대 힙으로 누적 D를 관리하며, 누적이 현재 E를 초과하면 가장 큰 D를 제거한다. 교환 논법으로 그리디 정당화, O(N log N), 64비트 정수 주의.

[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 조건에서 선형에 가깝게 처리되어 안전합니다.