기능적 그래프와 전처리 정렬을 활용한 동적 계획법 최적화 기법
그리드 기반 사각형 조합 탐색
그리드 환경에서 특정 조건을 만족하는 부분 도형을 탐색하는 문제에서는 각 도형의 가능한 배치 위치를 체계적으로 분류한 후, 이전 단계의 상태 정보를 기반으로 현재 위치로의 효율적인 전이를 수행하는 접근법이 유용합니다. 불필요한 중복 계산을 방지하기 위해 필요한 파라미터들을 미리 계산해 두면, 단위 위치당 $O(N)$ 시간 복잡도 ...
10월 3일 09:45에 게시됨
Codeforces Round 903 (Div. 3) 풀이
이번 라운드의 A~G번 문제에 대한 핵심 아이디어와 구현 방법을 정리합니다.
A. Don't Try to Count
문자열 t가 s의 연속 부분문자열이 되도록 만드는 문제입니다. s를 반복하여 이어붙이면 길이가 2배로 늘어나는 특성을 활용합니다. n·m ≤ 25 조건 덕분에 최대 5번만 반복하면 충분합니다.
#include <bits/stdc++.h>
using namespace std;
bool isSubstr(const s ...
7월 31일 23:32에 게시됨
펜윅 트리를 활용한 역쌍 계산 알고리즘
역쌍(Inversion Pair)이란 주어진 양의 정수 배열에서 인덱스 i가 j보다 작으면서 값은 a[i]가 a[j]보다 큰 경우, 즉 i < j && a[i] > a[j]를 만족하는有序对(순서쌍)를 의미한다.
这类 문제를 풀 때 가장 먼저 떠올리는 방법은 병합 정렬을 이용하는 것이다. 그러나 今回は 펜윅 트리(Fenwick Tree) 또는 BIT(Binary Indexed Tree)라는 자료구조를 활용하여 ...
7월 25일 03:34에 게시됨
바이너리 인덱스 트리: 구현과 활용
바이너리 인덱스 트리
1. 점 업데이트와 구간 합 查询
lowbit 함수
바이너리 인덱스 트리의 핵심은 lowbit 연산입니다:
lowbit(x) = x & (-x)
이 연산은 x의 이진 표현에서 가장 오른쪽에 있는 1의 위치 값을 반환합니다.
예를 들어, x = (0010010011000)₂ 라면:
-x = ~x + 1 = (1101101101000)₂
x & (-x) = (0000000001000)₂
동작 원리
배열 a[1...n]이 ...
7월 10일 04:24에 게시됨