데이터 구조 활용 알고리즘 풀이: 시뮬레이션 대회 기법 분석
문제 풀이 개요
이번 기술 평가에서는 다양한 데이터 구조 및 알고리즘 패턴을 요구하는 네 가지 문제를 다뤘습니다. 전반적으로 전처리 기법과 효율적인 데이터 접근 방식이 핵심이었으며, 다음과 같이 분류할 수 있습니다.
T1: 수직선상에서의 가중치 구간 합 계산 (좌표 압축 및 누적 합)
T2: 트리의 서브트리 내 희귀 요소 카운팅 (DFS 및 비트집합 병합)
T3: 제한 조 ...
8월 18일 01:36에 게시됨
트리 배열을 활용한 효율적인 구간 합 계산
트리 배열(Fenwick Tree 또는 Binary Indexed Tree, BIT)는 동적 배열에서 구간 합과 단일 요소 갱신을 매우 효율적으로 처리할 수 있도록 설계된 자료구조입니다. 이 구조는 O(log n) 시간 내에 전위 합(prefix sum)을 계산하고, 특정 위치의 값을 수정할 수 있어 빈번한 갱신과 질의가 필요한 문제에서 큰 성능 이점을 제공합니다.
기본 원리
트리 배열은 ...
7월 22일 06:38에 게시됨
구간 내 고유 요소 개수 구하기 - 펜윅 트리와 오프라인 처리
이 문제는 주어진 배열의 특정 구간에 존재하는 서로 다른 숫자의 개수를 구하는 것을 목표로 합니다. 이를 해결하기 위해 펜윅 트리(Fenwick Tree)와 오프라인 쿼리 처리 기법을 활용합니다.
펜윅 트리를 사용할 때 핵심은 각 위치에서 해당 요소가 마지막으로 등장한 위치를 추적하고, 새로운 위치에서 등장할 경우 이전 위치의 값을 제거하고 현재 위치를 갱신하는 것 ...
7월 17일 22:50에 게시됨
2025-10-21 XQQ 라운드 후기 및 문제 분석
대회 흐름 요약
T1을 먼저 시작, 고민 후 즉시 해결. 대양에서 한 번에 통과.
T2도 비슷한 방식으로 빠르게 해결. 역시 대양에서 통과.
15:48 T3에 접근, 그러나 잘못된 접근으로 실패. 다만
7월 1일 07:06에 게시됨
동적 역순 쌍 계산 문제
문제 개요
길이가 \(n\)인 순열 \(a\)가 주어진다. 두 원소를 교환할 때마다 역순 쌍의 개수를 2로 나눈 나머지를 출력해야 한다.
입력 형식
첫 번째 줄에는 양의 정수 \(n\)이 주어진다.
두 번째 줄에는 순열 \(a\)를 구성하는 \(n\)개의 숫자가 주어진다.
세 번째 줄에는 질의 수 \(q\)가 주어진다.
다음 \(q\)줄에는 각각 두 개의 양의 정수가 주어지며, 이는 \(a_i\)와 ...
6월 11일 16:49에 게시됨
BIT(페니크 트리) 개념 정리 및 문제 풀이
BIT(페니크 트리) 개요
BIT(Binary Indexed Tree)는 구간 합을 빠르게 계산하고, 특정 인덱스의 값을 업데이트할 수 있는 자료구조입니다.
lowbit 연산을 기반으로 하여 시간 복잡도 O(log N)을 보장합니다.
P3374: 기본적인 BIT 연산
단일 값 갱신과 구간 합을 처리하는 가장 기초적인 템플릿 문제입니다.
#include <bits/stdc++.h>
using namespace std;
int n ...
5월 26일 07:58에 게시됨