자료구조 문제 풀이 모음
이 문서에서는 다양한 자료구조 문제들을 다루며, 세그먼트 트리, 블록 분할, 그리고 코뜰리 트리(ODT)를 활용한 풀이를 소개한다.
P6812 「MCOI-02」조상 (Ancestor)
문제에서 정의한 "조상"은 비내림차순 수열이다. 이를 판별하기 위해 차분 배열을 활용하여 세그먼트 트리로 구간 최솟값을 관리할 수 있다. 차분 배열의 구간 최솟값이 0 이상이면 해당 구간은 비내림차 ...
6월 12일 16:42에 게시됨
세그먼트 트리의 기본 연산과 구현
단일 요소 수정 및 구간 질의
기본적인 세그먼트 트리는 이진 트리 구조로 단일 요소 수정과 구간 질의를 지원합니다:
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 200010;
struct TreeNode {
int left, right, max_val;
} tree[MAX_N * 4];
void update_node(int idx) {
tree[idx].max_val = max(tree[idx*2 ...
6월 1일 04:21에 게시됨
AtCoder ABC388 문제 풀이 분석
A - UPC 조합
문제 개요
입력 문자열의 첫 번째 글자 뒤에 "UPC"를 붙여 출력한다.
핵심 아이디어
문자열 인덱싱을 활용한 단순 구현.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string str;
cin >> str;
cout << str.front() << "UPC" <&l ...
5월 22일 13:43에 게시됨