동적 계획법(DP) 최적화 기법의 이해와 적용
1. 최장 증가 부분 수열(LIS)의 로그 시간 최적화
기존 $O(N^2)$의 시간 복잡도를 갖는 최장 증가 부분 수열 문제는 세그먼트 트리나 이진 인덱스 트리(BIT), 또는 이분 탐색을 활용하여 $O(N \log N)$으로 단축할 수 있습니다. 각 단계에서 계산된 $DP[i]$ 값을 자료구조에 삽입하고, 현재 값보다 작은 원소들 중 최대 DP 값을 쿼리하는 방식으로 전이 속도를 높입니다.
...
11월 1일 20:58에 게시됨
C++ 세그먼트 트리 구현 및 지연 전파(Lazy Propagation) 완벽 가이드
세그먼트 트리(Segment Tree)는 펜윅 트리(Fenwick Tree)와 유사하게 구간 합을 구하는 데 주로 사용되지만, 이 외에도 구간 최소/최대값 탐색, 구간 색칠 등 다양한 구간 연산을 효율적으로 처리할 수 있는 강력한 자료구조입니다. 본 가이드에서는 C++를 사용하여 세그먼트 트리의 기본 구현부터 지연 전파(Lazy Propagation)를 활용한 고급 기법까지 단계별로 다룹니다. ...
7월 23일 20:44에 게시됨
정수론과 기하학적 최적화를 활용한 알고리즘 문제 해결
약수 관계를 가진 정수 삼원조의 개수 구하기
양의 정수 \(n\)이 주어졌을 때, 다음의 조건을 모두 만족하는 정수 삼원조 \((a, b, c)\)의 개수를 구하는 문제입니다.
\(a + b + c = n\)
\(1 \le a < b < c \le n\)
\(a\)는 \(b\)의 약수이고, \(b\)는 \(c\)의 약수이다.
이 문제의 핵심은 약수 관계를 매개변수로 치환하여 식을 단순화하는 것입니다. ...
6월 27일 04:21에 게시됨
세그먼트 트리 심화: 다중 지연 전파와 세그먼트 트리 비트 구현
세그먼트 트리(Segment Tree)는 배열의 구간 연산을 효율적으로 처리하기 위한 강력한 자료구조입니다. 기본적인 구간 합 구하기를 넘어, 여러 종류의 업데이트를 동시에 처리하거나 구간 내 최솟값/최댓값을 갱신하는 고급 기법들이 존재합니다. 본 글에서는 지연 전파(Lazy Propagation)를 활용한 다중 연산 처리와 세그먼트 트리 비트(Segment Tree Beats)를 포함한 고 ...
5월 26일 20:46에 게시됨