공부 기록

버츄얼 돌다 만난 문제. 투포인터랑 부분합을 더 많이 풀어봐야겠다는 생각이 들었다. 일단 버츄얼 중에는 B를 만나고 멘탈에 많은 타격이 들어와 슼보를 왔다갔다 하며 C를 풀까말까 했다. 결국 B와 C 모두 풀지 못했다. 문제 핵심 아이디어$pfx$ 배열의 단조성을 이용하여 이분탐색 or 투포인터를 사용해야한다. 일단 m개의 creature에게 분배될 수 있는지부터 확인해야 하기 때문에 이를 관리해주어야 한다. $pfx[i]$를 앞에서부터 $i$ 까지 봤을 때 분배해줄 수 있는 creature 수라고 하고 $sfx[i]$를 뒤에서부터 $i$ 까지 봤을 때 분배해줄 수 있는 creature 수라고 하자.  이는 투포인터로 연속된 구간의 합을 합/차 해가며 그리디하게 $pfx$ 배열에 기록해주면 된다. 포인터..

codeforces 2024. 11. 22. 11:03

버츄얼을 돌던 중 만난 문제이다. 발상이 조금 특이해 블로그에 기록한다. 1. permutation 만드는 것이 가능한 경우 일단 permutation을 만들 수 있는 경우만 생각해 보면 $b$가 0 이상이면 다 된다. 모든 원소가 unique하기 때문에 $[0,n-1]$을 만들 수 있다. 이때 원소 중 $0\leq x$0\leq x 2. 불가능한 경우버츄얼 때에는 $b=0\;and\;c=0$으로 잡아서 틀렸다. (\앞으로 더 신중하게 반례를 생각해볼 필요가 있을 것 같다.\) 불가능한 경우는 $b=0$일 때를 주목하면 된다. $b=0$일 때 모든 원소는 $c$로 구성되어있다. 이들에 대해 연산을 진행하다보면 순환을 만나게 되는데 바로 $c+1\rightarrow c+2\;\;c+2\rightarrow..

codeforces 2024. 11. 11. 23:09

오일러 피함수는 양의 정수 $n$에 대하여 $n$보다 작은 양의 정수 $m$에 대해 $gcd(n,m)=1$인 $m$의 개수를 세는 함수이다. 오일러 피함수는 다음과 같이 정의되기도 한다. $\varphi (n)=|\{m|1\leq m\leq n,gcd(n,m)=1\}|$ 오일러 피함수는 특별한 성질을 가지고 있는데 바로 곱셈적 함수라는 것이다. $gcd(a,b)=1$ 인 $a,b$에 대해 $\varphi (ab)=\varphi (a)\varphi (b)$가 성립한다는 것이다. 증명은 다음 자료를 참고했다.  https://blog.chodaeho.com/posts/2021/eulers-totient-function/ 오일러 피 함수$Euler's phi (totient$ function)오일러 피 함수(..

정수론 2024. 11. 8. 19:15

이번 글에서는 에라토스테네스의 체를 이용해 소인수분해를 빠르게 하는방법을 다루고자 한다. https://www.acmicpc.net/problem/3142 이 문제를 풀던 도중 이 방법을 알게 되었다.기본적인 에라토스테네스의 체 구현보다 최적화된 구현과 함께 알게 되었다.https://velog.io/@pakuland3/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4-%EC%B5%9C%EC%A0%81%ED%99%94optimized-sieve-of-eratosthenes 에라토스테네스의 체 최적화$optimized sieve of eratosthenes$보통 에라토스테네스의 체를 구현할 때면$i$ 루프( ..

정수론 2024. 9. 29. 18:06

잠깐 복습용으로 페르마의 소정리를 적는다. $p$가 소수일 때 모든 정수 $a$에 대해 $a^p\equiv a\;modp$$p$가 소수이고 $a$가 $p$의 배수가 아닐 때 $a^{p-1}\equiv 1\;\;mod\;p$   출처: https://velog.io/@junttang/BOJ-11401-%EC%9D%B4%ED%95%AD-%EA%B3%84%EC%88%98-3-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5-C

정수론 2024. 9. 1. 19:52

모듈러 연산모듈러 연산은 어떤 수 $a$를 $0$ 아닌 수 $b$로 나누었을 때의 나머지를 구하는 연산이다. 예를 들어 $17\;mod\;5=2$이며 모듈러 연산에서는 동치 표현을 $\equiv$로 표시한다. $7\equiv 2\;mod\;5$로 표현할 수 있다. 모듈러 연산은 프로그래밍에서 $%$ 기호로 표시된다. 모듈러 덧셈 역원모듈러 덧셈 역원이란 어떤 수 $a$와 $b$에 대해 $(a+b)mod\;N=0$을 만족하는 쌍을 의미한다. $n=5$일 때 $2$의 덧셈 역원은 $5k+3$으로 나타낼 수 있다. 모듈러 곱셈 역원 모듈러 곱셈 역원이란 어떤 수 $a$에 대해 $a\cdot a^{-1}\;mod\;N=1$로 표현할 수 있으며 곱셈 역원을 $a^{-1}$로 표현한다. 곱셈 역원은 덧셈 역원과는 ..

정수론 2024. 9. 1. 18:22

정수론 | 기호 $a|b$는 $b$가 $a$로 나누어 떨어진다는 뜻이다. 더불어 $a|b$는 $a$가 $b$의 약수라는 것을 의미한다. 유클리드 호제법 유클리드 호제법은 GCD $GreatestCommonDivisor$ 알고리즘이라고도 불리우며 어떤 두 수 $a$와 $b$의 최대공약수를 구하는 알고리즘이다. 유클리드 호제법은 재귀적으로 실행되며 과정은 다음과 같다. int gcd$int a, int b${ int c; while$b${ c=a%b; a=b; b=c; } return a;} 확장 유클리드 알고리즘을 배우기 전에는 베주 항등식을 알아두어야 한다.  베주 항등식베주 항등식이란 식 $ax+by=g$ $(a,b$는 정수$)$ $(..

정수론 2024. 9. 1. 15:48

pygame 라이브러리를 이용해 미니체스를 만들어보았습니다. 시작화면은 아래와 같습니다. 게임시작 버튼을 누르게 되면 게임시작이 됩니다.원래 체스 규칙이 적용됩니다.폰은 처음 시작 시 두 칸 이동 가능합니다.룩은 십자로 이동 가능합니다.룩은 십자로 이동하며 폰을 먹을 수 있습니다.폰은 룩이 자신의 대각선에 있을 때 먹을 수 있습니다.+ 턴이 나뉘어 진행됩니다.\(게임의 우측 상단에 턴이 나옵니다.\)  게임의 종료 조건은 다음과 같습니다.  1.1 승리 - 폰폰이 전진하며 끝 칸에 도달했을 때 남아있는 룩이 하나도 존재하지 않을 때  폰이 승리하면 다음과 같은 장면이 연출됩니다.   1.2 승리 - 룩남아있는 폰이 하나도 존재하지 않을 때   2. 무승부폰의 턴일때 폰이 이동하는 경우의 수가 존재하지 않..

프로그램 2022. 7. 31. 23:43