분할 정복 중요 테크닉 - 히스토그램에서 가장 큰 직사각형 찾기

1. 문제 1725번: 히스토그램 (acmicpc.net) 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 2. 풀이 히스토그램이 주어질때, 찾을 수 있는 직사각형중 넓이가 가장 큰 직사각형을 찾는 문제 위와 같은 경우 다음과 같은 직사각형을 찾을 수 있을 것이다. 히스토그램이 높이 배열 A로 주어질 때, 어떤 구간 [i,j]까지 잡았을 경우, 만들 수 있는 직사각형은 높이가 가장 낮은 min(A)에 구간의 길이 j-i+1을 곱한 값이다. 따라서 가능한 모든 경우에 대해 min..

• format_list_bulleted 분할 정복
• · 2023. 9. 22.
• textsms

Fast Fourier Transform을 이용한 빠른 다항식 곱셈 공부하기

1. 두 다항식의 곱셈 다항식 $f(x) = a_{0}x^{0} + a_{1}x^{1} + ... + a_{n-1}x^{n-1}$과 $g(x) = b_{0}x^{0} + b_{1}x^{1} + ... + b_{n-1}x^{n-1}$의 곱셈은.. $f(x)g(x) = a_{0}b_{0}x^{0} + (b_{0}a_{1} + a_{1}b_{0})x^{1} + ... + a_{n-1}b_{n-1}x^{2n-2}$로 나타날 것이다. 다항식을 각각 계수만을 가진 길이가 n인 벡터 A = [a0,a1,...,an-1], B = [b0, b1, ... , bn-1]로 나타낸다고 할때, 두 다항식의 곱셈은 길이가 2n-1인 벡터 C = [c0,c1,...,c(2n-2)]로 나타나며, $$c_{i} = \sum_{j=0..

• format_list_bulleted 대수학
• · 2023. 8. 29.
• textsms

행렬을 이용한 피보나치 수열 문제의 해법

1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. $a_{n+1} = a_{n} + a_{n-1}$ $a_{n} = a_{n} + 0$ 따라서 행렬로 나타내면 다음과 같다 $$\begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}\begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix}$$ n = 1부터 반복적으로 곱해보면... $$ $$\begin{pmatrix} a_{2} \\ a_{1} \end{pmatrix}$$ = $$\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}$$ \begin{pmatrix} a_{1} \\ a_{0..

• format_list_bulleted 선형대수학 알고리즘
• · 2023. 3. 19.
• textsms

ABC 293 복기 E - Geometric Progression - 행렬곱 배우기 -

1. 문제 E - Geometric Progression (atcoder.jp) E - Geometric Progression AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 정수 A,X,M이 주어질 때, $$\sum_{k=0}^{X-1} A^{k}$$ 를 구하는 아주 간단한 문제 2. 풀이1 이미 재귀로 푸는 방법을 배운적 있다 컴퓨터가 등비수열의 합을 구하는 방법 (tistory.com) 컴퓨터가 등비수열의 합을 구하는 방법 1. 문제 15712번: 등비수열 (acmicpc.net) 15712번: 등비수열 첫째 줄에 a..

• format_list_bulleted Atcoder
• · 2023. 3. 12.
• textsms

컴퓨터가 등비수열의 합을 구하는 방법

1. 문제 15712번: 등비수열 (acmicpc.net) 15712번: 등비수열 첫째 줄에 a, r, n, mod가 공백으로 구분되어 주어진다. a, r, n, mod는 모두 1보다 크거나 같고, 109보다 작거나 같은 자연수이다. www.acmicpc.net 초항이 a, 공비가 r, 항 수가 n인 등비수열의 합을 mod로 나눈 나머지를 구하는 간단한 문제 초항이 a이고 공비가 r이며 항 수가 n인 등비수열의 합은.. 공비 r이 1이 아니면, $$S = a \times \frac{r^{n}-1}{r-1}$$ 이라는 아주 쉬운 공식이 있고 이거에 따라 계산해서 mod로 나눈 나머지 구하면 되는거 아니냐 라고 쉽게 생각하면 이 문제는 풀수가 없다 a,r,n이 작으면 상관 없겠지만... 매우 크면 $r^{n..

• format_list_bulleted 정수론
• · 2022. 12. 20.
• textsms

페르마의 소정리 문제 풀어보면서 익히기

1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$ 이다. 1-2) p가 소수이면, 모든 정수 a에 대하여 $$a^{p} \equiv a (mod p)$$ 응용하는 방법은 여러가지가 있겠지만, 하나하나 다 나열할 수도 없고, 접한지 얼마 안되었으니 나도 다 모르고 증명도 굳이 할 필요없을 것 같고, 받아들이면서 문제를 풀면서 익혀보기로 하자 2. 응용 - 합성수 판정 페르마의 소정리 역은 성립하지 않는다. 즉, a와 p가 서로소일때, $$a^{p-1} \equiv 1 (mod p)$$ 가 성립한다면, p는 소수이다는 거짓이다. 즉, ..

• format_list_bulleted 정수론
• · 2022. 12. 15.
• textsms