문제일단 가장 먼저 떠오르는 방법은 문자열 슬라이싱을 통해 비교하는 방법이다.n,m = [int(input()) for _ in range(2)]s = input()cnt = 0pn = 'I'for _ in range(n): pn += 'OI'for i in range(m): if s[i]=='I': if s[i:i+2*n+1]==pn: cnt += 1print(cnt)하지만 위 코드를 제출하면 첫 번째 서브테스크밖에 통과를 하지 못하고 50점을 받게 된다. python에서 리스트 l[a:b]의 문자열 슬라이싱의 시간복잡도는 $O(b-a)$ 라고 한다. 주어지는 S가 커질수록 시간이 오래 걸릴 수밖에 없다. 그럼 문자열 슬라이싱 말고 그냥 부분 부분 잘라서 비교..

문제간단한 정수론 문제이다.$$ A^{B^C}, B^C / A$$결국 이 두개를 0.25초 안에 계산하면 되는 문제라고 볼 수 있다.첫번째의 경우에는 페르마의 소정리를 이용하면 간단하게 구할 수 있다. 페르마의 소정리는 아래과 같다. $$ p\text{가 소수이면, 모든 정수 }a\text{에 대해 } a^p\equiv a\left({\rm mod}\ p\right) \text{이다.}$$ 이는 동치인 아래의 정리로 바꿀 수 있다. $$ p\text{가 소수이면, 모든 정수 }a\text{에 대해 } a^{p-1}\equiv 1\left({\rm mod}\ p\right) \text{이다.}$$우리는 아래의 정리를 사용할 것이다. $  A^{7-1}\equiv 1\left({\rm mod}\ 7\righ..

문제중국인의 나머지 정리(CRT)를 알고 있는 사람이라면 바로 해당 정리를 이용해서 문제를 풀어야겠다는걸 알 수 있다. 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)알고리즘이나 정수론, 암호학을 공부하면 항상 등장하는 개념인 중국인의 나머지 정리에 대해 알아볼 것이다.중국인의 나머지 정리란?중국인의 나머지 정리는 다음과 같은 여러 선형 합동nivr4y.tistory.comCRT는 주어진 법들이 서로소 관계일때만 적용되므로, 일반적인 CRT와는 약간 다르게 바꿔서 함수를 짜야 한다.풀이import sysinput = sys.stdin.readlinedef ext_euc(a, b): if b==0: return a, 1, 0 g, x, y = ext_euc(b, a..

알고리즘이나 정수론, 암호학을 공부하면 항상 등장하는 개념인 중국인의 나머지 정리에 대해 알아볼 것이다.중국인의 나머지 정리란?중국인의 나머지 정리는 다음과 같은 여러 선형 합동식을 만족하는 유일한 해를 구할 수 있게 해주는 강력한 정리이다.$$x \equiv 1\; \mathrm{(mod \; 3)},\\ x \equiv 2 \; \mathrm{(mod \; 5)},\\ x \equiv 3 \; \mathrm{(mod \; 7)}$$합동식들의 $a \equiv b \mod m$의 형태에서, 모든 m들은 서로 서로소 관계여야 한다.또한 각 합동식에서 x의 계수가 1이 아닌 경우가 있는데, 그런 경우에는 확장된 유클리드 알고리즘(EEA)를 사용해서 곱셈 역원을 구해서 양변에 곱해준 후 CRT를 적용한다.중..

문제나의 첫 플레티넘 문제이다!! 이전 글에서 확장된 유클리드 알고리즘을 공부한것이 큰 도움이 되었다.2024.09.23 - [BOJ/이론] - Extended Euclidean Algorithm (확장된 유클리드 호제법) Extended Euclidean Algorithm (확장된 유클리드 호제법)확장된 유클리드 호제법이란?2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기  유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기유클리드 호nivr4y.tistory.com문제에서 요구하는 것을 식으로 만들어 보면 다음과 같다.$$ k \cdot x + c \cdot y \equiv 1 \mod c $$이는 확장된 유클리드 알고리즘으로 ..

확장된 유클리드 호제법이란?2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기  유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기유클리드 호제법이란?호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.호제법(互除法)이라는 단어가 따로 있는것은 아니고, 서로(互) 나누기(除nivr4y.tistory.com유클리드 호제법이 두 정수 $a$, $b$의 최대공약수 $gcd(a,b)$를 구하는 방법이였다면 확장된 유클리드 호제법은 두 양의 정수 $a$,$b$가 있을때 베주 항등식이라 불리는 아래의 식에서 $u,v$의 값을 찾아내는 효율적인 방법이라고 할 수 있다.$$ \displaystyle{\di..

문제2 x 1, 1 x 2 타일로 2 x n 짜리 타일을 채우는 방법의 수를 물어보고 있다. 이 문제를 푸는 핵심은 우리가 이전에 구했던 경우의 수 들로 다음 경우의 수를 구해야 하는 것이다. 전 항과 우리가 구하려고 하는 항의 관계를 흔히 점화식이라고 부른다.다이나믹 프로그래밍 문제를 푸는 데의 핵심은 점화식을 구하는 것에 있다. n=1 부터 초반 몇 개 항을 적다 보면, 항들 간의 관계를 생각해볼 수 있는데, 우리가 2 x k 짜리 타일을 채우는 방법을 고민할때, 2 x k 타일을 채우는 경우의 수는 2가지밖에 없다. 2 x (k-1) 짜리 타일에 1 x 2 타일을 마지막에 붙이거나, 2 x (k-2) 짜리 타일에 2 x 1 타일 2개를 2 x 2로 만들어서 붙이는 것이다. 결국 2 x n 짜리 타일..

문제정수 X를 주어진 연산을 이용해 1을 만드는 방법들 중 최솟값을 구하는 방법이다. 시간 제한은 0.15초로 여유롭지 않은 것을 알 수 있다. python은 1.5초, pypy는 0.7초이다.시간 초과 코드import sysdef solve(a): if a == int(a): a = int(a) if a == 1: return 0 if L[a] != -1: return L[a] else: t = min(1+solve(a/3), 1+solve(a/2), 1+solve(a-1)) L[a] = t return t else: return 9..

문제문제에서 주어지는 두 수 N, K를 이용해 이항 계수 $ \binom{n}{r} $ 즉, $ _nC_r $ 을 구하는 문제이다.Combination의 정의인 $ _nC_r = \frac{n!}{(n-r)!r!} $ 을 이용해서 풀 수도 있겠지만, 이전에 올렸던 이항 계수의 성질을 이용하면 훨씬 빠르고 효율적으로 구할 수 있다.2024.07.20 - [BOJ/이론] - 조합(Combination)과 이항 계수를 python으로 구현해보자. 조합(Combination)과 이항 계수를 python으로 구현해보자.조합의 정의조합(Combination) : 서로 다른 n개의 원소에서 r(단, 0를 중복 없이, 순서를 고려하지 않고 선택하는 것.중요한 것은 순열과 같이 선택해서 나열하는 것이 아닌, 선택하기만 ..

조합의 정의조합(Combination) : 서로 다른 n개의 원소에서 r(단, 0를 중복 없이, 순서를 고려하지 않고 선택하는 것.중요한 것은 순열과 같이 선택해서 나열하는 것이 아닌, 선택하기만 하기 때문에 순서는 중요하지 않다는 것이다. (1,2,3,4,5)에서 (2,3)을 뽑는 것과 (3,2)를 뽑는 것을 같은 것으로 본다는 말이다. n개 중에서 r개를 뽑는 조합을 다음과 같이 표현할 수 있다.$$ _nC_r = \binom{n}{r} $$조합을 다룰때 빠질 수 없는 순열은 다음과 같이 표현할 수 있다.$$ {}_n{\rm P}_r $$순열과 조합 $$ {}_n{\rm P}_r = \frac{n!}{(n-1)!} $$ $$ _nC_r = \frac{n!}{(n-r)!r!} $$순열과 조합을 구하는 ..