gubshig

별로 대단한 내용은 아니고 알고 있는 내용일수도 있다. 갑자기 생각나서 써본다. 등비수열 합 공식은 $$\frac{a(r^n - 1)}{r-1}$$ 으로 그냥 외우는 사람이 많다. 증명도 되게 간단하지만 왜 공식이 이렇게 생겼는지 명확하게 설명해주진 못한다고 생각한다. $$r^n - 1 = (r - 1)(r^{n-1} + r^{n-2} + r^{n-3} ... + 1)$$ 이 항등식이 성립하는걸 생각해보자. 증명은 자명하니 생략하겠다. 양변을 r - 1로 나누어주고 첫항을 곱해주면... $$\sum_{i = 1}^{n}ar^{n - 1}$$ 가 나온다! 다항식의 인수분해로 이해하면 좀 더 이해하기 쉽다고 생각한다.

https://www.acmicpc.net/problem/1750 1750번: 서로소의 개수 예제 1의 경우 가능한 경우의 수는 (2, 3), (4, 3), (2, 4, 3)이다. www.acmicpc.net 배낭 문제로 풀리는걸 깨달으면 쉬운 문제이다. 수열의 원소를 선택해서 어떤 연산을 해서 나오는 경우의 수를 구할때, 배낭 문제를 사용하면 쉽게 풀 수 있다는걸 잊지 말자. 단, 연산의 교환법칙이 성립해야한다. import sys import math mod = 10000003 input = sys.stdin.readline n = int(input()) a = [int(input()) for _ in range(n)] ans = 0 SZ = max(a) + 1 dp = [0] * SZ for i i..

생각보다 문제의 풀이를 작성하는것이 재밌어서 앞으로 자주 할 것 같다. https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 간단한 배낭 dp 문제이다. dp(i, j)를 i번까지 추를 사용해서 무게 j를 만들 수 있는가? 로 정의하자. 구슬의 무게를 확인할 수 있다는 것이 무슨 뜻일까? 구슬을 왼쪽 저울에 고정한다 할 때, 오른쪽에 추를 올리는것은 추의 무게를 더한다고 할 수 있고, 왼쪽에 추를 올리는 것은 추의 무게를 뺀다 할 수 있다. dp(0,..

이 문제는 서브테스크를 긁고 최적화를 할 방법을 모르겠어서 풀이를 봤다. 풀이가 신기하고 좋은 문제라고 생각해서 풀이를 올려본다. https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 이 문제를 요악하자면 트리를 S라는 집합의 정점들로만 한정지었을때, 생기는 각 컴포넌트들의 연결 되어있는 노드의 개수를 구하면 된다. 연결 개수는 컴포넌트의 노드 개수를 n이라 했을때, nC2가 된다. 나이브하게 매 쿼리마다 dfs를 돌리며 컴포넌트의 개수를 ..

최근에 1차 대회 문제 몇개를 풀었는데, 문제 퀄리티가 좋다고 생각해서 풀이를 정리해볼까 한다. https://www.acmicpc.net/problem/25379 25379번: 피하자 음이 아닌 정수로 이루어진 길이 N의 배열 A = [A1, A2, · · · , AN]가 있다. 배열 A에서 인접한 두 수를 교환하는 시행을 원하는 만큼 할 수 있다. 이 때, 홀수와 짝수가 인접한 경우가 최대 1번 등장 www.acmicpc.net 처음 봤을땐 구현을 어떻게 해야하나 막막했는데, 차분히 생각해보니 구현이 어려운 문제는 아니었다. 결국 홀수와 짝수를 한쪽으로 밀어야하는데, 홀수를 밀든 짝수를 밀든 결국 횟수는 같다. mod 2를 해주고 왼쪽으로 밀어보고, 오른쪽으로도 밀어본 다음 최솟값을 출력하면 된다. ..

개요 FFT는 이산적인 영역에서 하는 푸리에 변환인 DFT(Discrete Fourier Transform)을 분할정복 기법을 이용하여 $\Theta (n\,log\, n)$ 시간 내에 수행하는 알고리즘 입니다. 이를 보통 PS에서는 두 다항식의 곱셈을 $\Theta (n\,log\, n)$ 에 처리하기 위해 사용합니다. 이 글을 이해하기 위한 사전지식으로는 기초적인 프로그래밍 지식과 복소수 지수에 대한 이해가 필요합니다. DFT (Discrete Fourier Transform) 우선 DFT의 정의부터 살펴봅시다. 수열 $a_{0}, \,a_{1}, \,a_{2} , \,a_{3},\,...\, a_{n-1}$ 에 대하여, $\omega_{N} = e^{-2\pi i/N}$, $\hat{a}_{n} ..

알고리즘, 수학에 관심이 있는 평범한 고등학생 입니다. 관련된 것으로 공부한 내용을 정리하거나, 재밌는 문제들의 풀이 등을 업로드 할 예정입니다.