알고리즘 문제 해결 전략: 비트마스크부터 수론까지
격자 상태 탐색 및 비트마스크 활용
첫 번째 문제는 주어진 격자에서 특정 행과 열을 선택하여 제거했을 때, 남아있는 검은색 셀의 개수가 정확히 K 가 되는 경우의 수를 찾는 문제이다. 행과 열의 개수가 작으므로 비트마스크를 이용하여 모든 조합을 탐색하는 방식이 적합하다.
각 행과 열에 대해 선택 여부를 비트로 표현하여 반복문을 구성한다. 선택된 행이나 열에 포 ...
8월 10일 07:39에 게시됨
최대공약수 및 확장 유클리드 알고리즘: ICPC 문제 풀이 및 개념 복습
최대공약수(GCD)의 원리
gcd(x, y)와 gcd(y, x % y)가 동일한 이유는 다음과 같습니다.
x와 y의 최대공약수를 d라고 가정합니다.
x = m * d, y = n * d라고 하면,
x % y = x - (x / y) * y가 됩니다.
이때 x / y는 정수 나눗셈 결과입니다.
x % y = m * d - (x / y) * n * d = (m - (x / y) * n) * d
따라서 x % y도 d의 배수입니다.
즉, x와 y의 공약수는 y와 x % y의 공 ...
7월 25일 04:37에 게시됨
NOI2025 예선 대비 문제 풀이 정리
[NOI2025 예선 R1] A - 기본 사이클 구조
다음의 수학적 원리를 활용한다:
Cayley 정리
n개의 노드가 k개의 연결 성분으로 구성되어 있을 때, 이들을 연결하기 위해 k-1개의 간선을 추가하는 방법의 수는 n^(k−2) × ∏(i=1 to k) size_i이다.
이 정리를 바탕으로, 입력 그래프에 이미 사이클이 존재하는 경우 답을 직접 계산할 수 있다.
반면, 초기 상태에서 사이 ...
7월 24일 03:13에 게시됨
ICPC Asia EC Regionals 2024 온라인 예선 (II) 풀이
A - 지역 예선 선택 도박
문제 요약
총 $k$개의 경기가 있으며, 각 경기마다 대학당 최대 $c_i$개 팀이 참가 가능하다. $n$개 팀이 있고 각 팀은 점수와 소속 대학 정보를 가진다. 각 팀은 최대 2개 경기에 출전할 수 있다. 모든 팀이 최악의 상황에서 얻을 수 있는 최선의 순위를 구해야 한다.
핵심 아이디어
최악의 경우는 내가 참가하는 경기에 강팀들이 몰리는 상황이 ...
7월 23일 20:16에 게시됨
알고리즘 수학 핵심 정리
정수 분할 기법 (Divisor Summation)
형태가 \(\sum_{i=1}^{n} f(i) \cdot g\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\)인 합을 효율적으로 계산하는 방법입니다. \(g(x)\)와 구간 합 \(\sum_{i=l}^{r} f(i)\)를 빠르게 구할 수 있을 때 유용합니다.
핵심 원리
\(\left\lfloor\frac{n}{i}\right\rfloor\) 값이 같은 구간들을 묶어서 한 번에 처리합니다. 이 ...
7월 9일 01:52에 게시됨
세그먼트 트리와 비트셋을 활용한 쿼리 문제 해결 (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에 게시됨