알고리즘 문제 해설: 모듈로 합, 그래프 연결성 및 구간 쿼리
CF577B: Modulo Sum
주어진 수열에서 연속되지 않은 부분 수열을 선택하여 그 합이 특정 수 m으로 나누어 떨어지는지 판단하는 문제입니다.
해결의 핵심은 비둘기집 원리 (Pigeonhole Principle) 에 있습니다. 수열의 길이 n이 모듈로 값 m보다 크다면,PREFIX 합을 m으로 나눈 나머지는 총 m가지 경우しか 존재하지 않습니다. 따라서 n > m인 상황에서는 반드시 같은 나 ...
9월 17일 02:29에 게시됨
세그먼트 트리와 바이너리 인덱스 트리 (템플릿)
세그먼트 트리 1 - 구간 연산 및 합계
이 템플릿은 구간 더하기 연산과 구간 합을 구하는 세그먼트 트리를 구현합니다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
int arrSize, queryCount;
const int MAX ...
7월 28일 18:20에 게시됨
문자열 해시와 선분 트리, 트리 DP, 비트셋을 활용한 정사각형 탐색 문제 풀이
문제 1: 동적 문자열 집합에서 고유 문자열 수 계산
여러 개의 동일 길이 문자열이 주어지고, 각 쿼리마다 특정 문자열의 부분 구간을 같은 문자로 덮어쓴 후, 전체 집합 내 서로 다른 문자열의 개수를 출력해야 한다.
해결 핵심은 다음과 같다:
각 문자열의 해시 값을 효율적으로 갱신하기 위해 게으른 전파(lazy propagation)가 가능한 선분 트리를 사용한다.
해시 ...
7월 20일 20:48에 게시됨
트리 체인 분할을 이용한 알고리즘 구현 및 응용
개요
트리 체인 분할은 트리를 여러 체인으로 나누어 선형 자료구조를 활용할 수 있도록 하는 기법이다. 이 중 가장 널리 사용되는 방식은 Heavy-Light Decomposition(HLD)이다.
다음과 같은 개념들을 정의한다:
무거운 자식: 특정 노드의 모든 자식 중 서브트리 크기가 가장 큰 자식
가벼운 자식: 무거운 자식을 제외한 나머지 자식들
무거운 간선: 부모와 무거운 자식을 ...
7월 14일 21:25에 게시됨
세그먼트 트리를 활용한 간선 생성 최적화 기법
문제 도입
그래프 이론 문제를 해결하다 보면, 특정 노드가 구간 내의 모든 노드와 간선을 연결해야 하는 상황이 종종 발생한다. 예를 들어, "노드 u에서 구간 [L, R]에 속하는 모든 노드로 이동 가능"과 같은 제약 조건이 대표적인 경우다. 이러한 경우 단순히 모든 노드를 순회하며 간선을 생성하면 O(n²)의 시간 복잡도가 발생하여 시간 초과가 발생할 수 있다.
이러한 ...
7월 13일 21:20에 게시됨
트리 체인 분할을 활용한 경로 및 서브트리 쿼리 처리
트리 체인 분할 개요
트리 체인 분할(Heavy Path Decomposition)은 트리 구조에서 효율적인 쿼리 처리를 위한 고급 자료구조 기법이다. 이 기법은 다음 네 가지 핵심 연산을 지원한다:
두 노드 x에서 y까지의 최단 경로상의 모든 노드에 값을 더한다
두 노드 x에서 y까지의 최단 경로상의 모든 노드 값의 합을 구한다
노드 x를 루트로 하는 서브트리의 모든 노드에 값을 ...
7월 10일 17:56에 게시됨
Codeforces Round 991 (Div. 3) F - 구간 최대公约수와 차분 배열
문제 접근
이 문제는 구간 내에서의 최대公约수(GCD) 값을 구하는 문제이다. 핵심 아이디어는 차분(difference) 배열을 활용하는 것이다. 원래 배열에서 인접한 요소들의 차이를 구하면, 해당 구간의 GCD는 차분 배열의 특정 구간 GCD와 동일해진다.
따라서 우리는 구간 GCD를 효율적으로 구할 수 있는 자료구조를 사용하면 된다. 두 가지 대표적인 방법을 소개한다.
방 ...
7월 10일 06:27에 게시됨
세그먼트 트리와 비트셋을 활용한 쿼리 문제 해결 (Codeforces Round #538 Div.2 F)
문제 개요
주어진 배열에서 구간 곱과 그 결과에 대한 오일러 피 함수 값을 계산하는 문제입니다. 핵심 아이디어는 오일러 피 함수의 성질과 300 이하의 소수가 62개뿐이라는 점을 활용하는 것입니다.
수학적 배경
구간 [l, r]의 곱을 X라고 할 때, X를 소인수분해하면 다음과 같습니다:
X = ∏ p_i^{c_i} (i = 1 to n)
오일러 피 함수는 곱셈적 함수이므로:
φ(X) = φ(∏ ...
6월 29일 00:36에 게시됨
알고리즘 디버깅 노트: 실수에서 배우는 최적화
경험을 통해 배운 디버깅 사례들을 정리합니다. 비슷한 실수를 반복하지 않기 위한 기록입니다.
위상 정렬: 인덱스 실수
원본 코드:
while (front < rear) {
int cur = queue[front++];
for (int idx = adj[cur]; idx; idx = nxt[idx]) {
int nxtNode = to[idx]; // 정상
indeg[nxtNode]--;
if (indeg[nxtNode] == 0) {
...
6월 25일 21:08에 게시됨
알고리즘 문제 해결을 위한 표준 템플릿 라이브러리
알고리즘 경진대회 참가자들은 다양한 알고리즘과 자료구조를 숙지하고 있어야 하며, 이를 효율적으로 구현하기 위해 여러 템플릿을 정리해두는 것이 중요하다.
코드 작성 시 주의사항
전역 변수 사용은 피해야 한다. 디버깅이 어렵고 코드의 가독성을 해친다.
표준 라이브러리(STL)을 적극 활용하자. 스택, 큐, 벡터 등을 직접 구현하는 것보다 안정적이다.
#define in ...
5월 22일 23:09에 게시됨