전체 글(77)
-
[BOJ 12797] 연금술
굉장히 오랜만에 올리는 포스팅~ 방학동안 버클리에 가 있어서 백준을 못한게 크다 ㅜㅜ. 본론으로 들어가자. 문제는 $m$개의 재료 중에서 $n$개를 선택해서 그 값들의 곱을 모두 더하는 것이다!! 간단히 주어진 예제로 생각해보면 값이 각각 $x, y, z$라고 할 때 \[x^{3}+y^{3}+z^{3}+x^{2}(y+z)+y^{2}(z+x)+z^{2}(x+y)+xyx\] 를 구하는 것이다. 우리가 생각할 수 있는 것은 이 식을 어떻게 좀 간단하게 할 수 있냐는 것이다. 놀랍게도 위의 식은 다음과 같이 간단하게 표현된다! \[\frac{x^{5}}{(x-y)(x-z)}+\frac{y^{5}}{(y-x)(y-z)}+\frac{z^{5}}{(z-x)(z-y)}\] 값이 서로 다른 $m$개의 재료 중에서 $n$..
2022.08.20 -
가을학기 수강 계획
방학때 버클리에서 현대대수학 1을 들으면서 현대대수학 2를 스터디해서 가을 학기에는 현대대수학 2를 듣기로 결정! 버클리 현대대수학 1은 현대대수학 2 내용까지 일부 나가서 오히려 좋다. 응미방은 수리 전공을 위해서 들어야하는 기선이다. 저거까지 듣고 다른 과 기선 들어야지! 라고 생각했지만 다른 과는 들을 과목이 없으니까 확률 및 통계를 듣지 않을까 싶다. 미적분학 2랑 일반 물리학 2를 빨리 없애야지. 일반 생물학이랑 일반 물리학 실험 1이 남긴 했지만 1학기에 일반 화학 실험을 B+받은 뒤로 보고서를 쓰기 싫어져 버렸다. 2학기에는 전공 과목을 조금 듣는 시기로 선형대수학을 포함했다. 1학기때 선형 대수학 개론을 들었으니까 잘 되겠지?ㅎ 입학 영어 시험이 망해서 가을 학기에 영어 한 과목을 또 청산..
2022.07.14 -
Extension of Wilson's Theorem and its application
이라는 제목의 논문(?)을 써보았다. 내 블로그에 있는 증명에 있는 오류를 모두 수정하여 썼다~ 한참 전에 썼었는데 까먹고 못 올리고 있었다ㅎㅎ 블로그에 신경쓸 수 없을 정도로 바빴다. 물론 지금도 바쁘고! 윌슨의 정리 확장을 이용한 재미있는 알고리즘을 소개했으니 한 번 읽어보기를 바란다!
2022.07.14 -
[BOJ 16123] 피타고라스 쌍
문제에서 주어진 조건으로부터 $(n,m)=1$이고 $m\not\equiv n\pmod{2}$라는 사실을 알 수 있다. 그럼 우리가 구하고자 하는 값은 다음과 같다. \[\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1][n=odd][m=even]\] 위 식을 변형 시키면 다음을 얻는다. \[=\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1](1-[2|n])[2|m]\] \[=\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1][2|m]-\sum_{n=1}^{L}\sum_{m=1}^{L}[(n,m)=1][2|n][2|m]\] 이때 오른쪽 항은 항상 0이 된다는 사실을 알 수 있다. \[=\sum_{n=1}^{L}\sum_{m=1}^{L}\sum_{s=1..
2022.07.14 -
[BOJ 15868] Yule Lads
Yule lads라는 산타클로스(?)가 왜서 불을 끄고 키고 한다는 문제이다. 총 $N$개의 집이 있고 모두 불이 켜져있다. 크리스마스의 $n$째날 전에는 $n$의 배수 번째 집의 불이 꺼지고 마지막에 숫자 1을 제외하고 모든 집에 불이 꺼질 경우 몇 명의 Yule Lads가 올 수 있을까?를 묻고 있다. 이런 경우에는 소수를 먼저 보자. 소수 번째 집에는 반드시 YL(Yule Lad)이 와야한다. 그럼 서로 다른 소수의 곱 번째 집($pq$)에는 $p$가 한 번 왔다가고 $q$가 한번 왔다 가므로 $pq$는 반드시 들러야한다. 일반화해보면 $n$의 약수의 개수가 짝수 개이면 된다는 것이다. 그런데 소수의 제곱수들을 생각해보자. 이들은 약수가 홀수 개이므로 YL이 오지 않는다. 서로 다른 $n$개의 소수..
2022.06.17 -
[BOJ 13729] 1013 피보나치
이 문제 역시 교육적인 문제. 부분 조건을 이용해 전체 조건을 만족시키게 하는 문제이다. 문제에서 주목할 부분은 $F_{n} \bmod{10^{13}} =N$이 되는 $n$이 있냐는 것이다. 다른 말로 하면 $F_{n}\bmod{10}=N\bmod{10}$이고 $F_{n}\bmod{100}=N\bmod{100}$이고 ...를 만족하는 $n$이 있냐는 것이다. 우린 modulo가 $10^{3}$인 곳에서 시작한다. 왜냐면.. 그때부터 피보나치 수열의 피사노 주기가 $10^{n-1}*15$이기 때문이다. 알고리즘의 작동 원리는 간단하다. 법 $10^{3}$에 대해 $i$번째 피보나치 수와 $N$이 합동인 $i$들을 모아놓자. 이론적으로 1500개만 검사하면 되므로 금방 모인다. 그럼 방금 구한 각각의 인덱스..
2022.06.16