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)와 엣지 케이스 처리까지 한 문서에 정리했습니다.

Algorithm Stack

[Algorithm] C++ 백준 1725번: 히스토그램

히스토그램에서 최대 넓이 직사각형을 찾는 고전 문제입니다. 스택을 활용한 선형 시간 알고리즘으로 O(n) 복잡도를 달성하며, 좌우 경계 확장 개념과 엣지 케이스 처리를 완벽히 정리했습니다.

Algorithm Computational Geometry

[Algorithm] C++ 백준 2626번: 헬기착륙장

N개 섬의 최적 헬기착륙장 위치를 찾는 최소 외접원(MEC) 문제입니다. Welzl의 랜덤화 선형 시간 알고리즘으로 원의 중심과 반지름을 구하고, 세 점의 외접원 계산과 일직선 처리로 견고한 기하 구현을 합니다.

Algorithm String

[Algorithm] C++ 백준 4354번: 문자열 제곱

문자열 s = a^n을 만족하는 최대 n을 KMP failure function으로 O(n)에 구합니다. 주기성 판별과 약수 계산을 통해 정확하게 해결하고, 엣지 케이스 처리까지 정리한 풀이입니다.

Algorithm Graph

[Algorithm] C++ 백준 7577번: 탐사

직선 도로에서 구간별 물체 개수 조건을 만족하는 배치를 찾는 문제입니다. 차분 제약 조건을 그래프로 모델링하고 SPFA로 음수 사이클을 탐지하여 O(NK) 시간에 해결합니다.