Algorithm Dynamic-Programming

[Algorithm] C++ 백준 29200번: 문제 수 줄이기

DP로 XOR 합 최대화 분할 문제 해결. 인접 구간 길이 조건 + 상태 최적화(Best/SecondBest)로 O(NK)에 해결. 정당성: 길이 제한의 최적성, 귀납적 DP 전이 증명 포함.

Algorithm Geometry Math

[Algorithm] C++ 백준 16481번 원 전문가 진우 - 방접원과 내접원의 관계

삼각형의 세 방접원 반지름이 주어졌을 때 내접원의 반지름을 구하는 기하학 문제입니다. 방접원과 내접원의 수학적 관계식을 유도하여 O(1) 시간복잡도로 해결하는 풀이를 제시합니다.

[Algorithm] C++ 백준 27533번 따로 걸어가기

토끼 부부가 격자 위에서 만나지 않고 이동하는 경로의 수를 구하는 비교차 경로(non-intersecting paths) 문제로, Lindström-Gessel-Viennot 보조정리를 사용하여 해결합니다. 조합론과 모듈로 연산을 활용한 효율적인 풀이입니다.

Algorithm Combinatorics

[Algorithm] C++ 백준 6567번: 팔찌

팔찌의 고유한 개수를 구하는 조합론 문제. Burnside의 보조정리와 오일러 파이 함수를 활용하여 회전과 뒤집기 대칭을 처리하는 Polya 열거 정리 풀이입니다. 조합 게임 이론의 핵심 개념을 학습할 수 있습니다.

Algorithm Game Theory

[Algorithm] C++ 백준 11869번: 님블

님블 게임 이론 문제 풀이. Sprague-Grundy 정리를 활용하여 각 동전 위치의 XOR로 게임 승자를 O(M) 시간에 판별합니다. 조합 게임 이론과 님 게임의 핵심 원리를 학습할 수 있는 문제입니다.

Algorithm Computational-Geometry

[Algorithm] C++ 백준 13310번: 먼 별

N개 별의 시간에 따른 위치 변화 중 가장 먼 두 별 사이 거리 최소화 시점을 찾는 문제입니다. 삼분 탐색, 볼록 껍질, 회전하는 캘리퍼스를 활용하여 O(N log N log T) 시간에 해결합니다.

[Algorithm] C++ 백준 13925 수열과 쿼리 13

구간 덧셈, 곱셈, 값 설정과 구간 합 쿼리를 처리하는 Lazy Propagation 세그먼트 트리 문제. 선형 함수 f(x)=mul*x+add로 모든 연산을 통합하여 해결합니다.

Algorithm Data Structure

[Algorithm] C++ 백준 14504번: 수열과 쿼리 18

Merge Sort Tree를 이용하여 범위 내 k보다 큰 원소 개수를 O(log²n)에 조회하고 O(log n)에 갱신합니다. 세그먼트 트리의 각 노드에 정렬된 벡터를 저장하여 범위 쿼리를 효율적으로 처리하는 풀이입니다.

Algorithm Tree Data Structures

[Algorithm] C++ 백준 15782번: Calculate! 2

트리 구조에서 부분트리 XOR 쿼리 및 범위 업데이트를 효율적으로 처리하는 문제입니다. Euler Tour Technique으로 트리를 일렬화하고 Lazy Propagation 세그먼트 트리로 O((N+M)logN)에 해결합니다.

Algorithm Greedy

[Algorithm] C++ 백준 16496번: 큰 수 만들기

주어진 음이 아닌 정수들을 재배열하여 만들 수 있는 가장 큰 수를 그리디 정렬으로 O(n log n)에 구합니다. 커스텀 비교함수(a+b vs b+a)와 엣지 케이스 처리까지 한 문서에 정리했습니다.