가장자리 트리(지속 가능한 세그먼트 트리) 기초 설명
개요
가장자리 트리는 지속 가능한 세그먼트 트리로, 하지타 님이 개발한 데이터 구조이다. 함수형 세그먼트 트리라고도 불린다. 이 구조는 배열의 역사적 상태를 효율적으로 저장하고 조회할 수 있게 해준다.
핵심 아이디어
모든 버전을 복제하는 방식은 메모리 낭비가 심하다. 하지만 각 업데이트에서 영향을 받는 노드는 루트까지의 경로에 국한된다. 따라서 기존 트 ...
9월 9일 16:17에 게시됨
이진 인덱스 트리와 세그먼트 트리를 활용한 효율적인 알고리즘 해결 방안
이 문제는 주로 자료구조를 다루며, O(n log²n) 시간 복잡도를 가지는 이진 인덱스 트리와 이분 탐색 조합이 O(n log n)의 세그먼트 트리 이분 탐색보다 빠르다는 점을 보여줍니다. 세그먼트 트리는 상수 최적화가 필요할 정도로 20ms 차이로 시간 초과가 발생합니다.
공식을 통해 k 라운드(모두 사용) 후 체력이 0이 되는 지점을 이분 탐색으로 찾을 수 있습니다. 그 다음 ...
7월 25일 13:03에 게시됨
HEOI2016/TJOI2016 알고리즘 문제 해설
[HEOI2016/TJOI2016] 트리
이 문제는 트리에서 노드를 표시하거나, 특정 노드로부터 가장 가까운 조상 중 표시된 노드를 찾는 쿼리를 처리해야 한다. 이를 효율적으로 해결하기 위해 경로 분할(Heavy-Light Decomposition) 기법을 사용한다. 각 경로 체인의 맨 위에 있는 표시된 노드를 관리하고, 세트(set)를 이용해 체인 내 위치를 추적한다. 쿼리는 부모 방향으로 이동 ...
7월 14일 19:41에 게시됨
삽입 정렬의 원리와 실전 활용 전략
삽입 정렬의 작동 원리
삽입 정렬은 데이터를 하나씩 차례로 처리하며, 이미 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작합니다. 이는 마치 카드를 손으로 정리하는 과정과 유사합니다.
정렬된 영역: 처음에는 첫 번째 요소만 포함되어 있으며, 단일 요소는 자연스럽게 정렬된 상태입니다.
미정렬 영역: 두 번째 요소부터 끝까지 탐색 대상입니다.
삽입 절차:
...
7월 13일 23:14에 게시됨
AtCoder ABC321 풀이 노트
A - 321-like Checker (난이도 22)
주어진 숫자의 각 자리를 순차적으로 확인하여 이전 자리보다 현재 자리가 항상 작은지 검사합니다.
void solve() {
int n;
cin >> n;
int prev = -1;
while (n > 0) {
int cur = n % 10;
if (cur <= prev) {
cout << "No" << endl;
return;
} ...
6월 30일 17:51에 게시됨
루구 P3957: 점프 하우스 문제 해결 및 동적 프로그래밍 최적화
문제 설명
이 문제는 2017년 NOIP(전국정보올림피아드) 보급조 T4 문제로, 동적 프로그래밍(DP)의 데이터 구조 최적화 요구사항을 보여줍니다. 2018년 T3 및 NOI online 2020 T2 문제와 함께, NOIP 보급조가 DP 최적화에 대한 요구를 높이고 있음을 알 수 있습니다.
해결 접근법
이 문제는 시험장에서도 매우 어려운 완전 탐색 문제입니다. 주어진 데이터 범위는 다음과 같 ...
6월 1일 11:17에 게시됨
이분 탐색 기반 문제 해결 분석 및 코드 리뷰
개요
이 문서는 이분 탐색을 활용한 알고리즘 문제 해결 과정에 대한 검토를 다룹니다. 각 문제는 이분 탐색과 보조 함수인 check를 결합하여 최적해를 도출하는 전략을 사용합니다. 아래에서는 각 문제에 대한 접근 방식, 오류 원인, 그리고 최종 정답 코드를 재구성하여 설명합니다.
문제 1: 나무 자르기 (P1873)
주어진 높이 이상의 나무를 잘랐을 때 얻을 수 있는 나 ...
5월 27일 04:01에 게시됨