이동식 저장소

프로그래머스 월간 코드 챌린지 시즌1 접수 20년 08월 27일 14:00 ~ 11월 05일 18:00 테스트 20년 09월 10일 19:30 ~ 11월 05일 22:30 programmers.co.kr 시즌 1의 마지막 대회인 11월 대회이다. 하필 준PO 2차전이랑 겹쳐서 고민했는데, 야구를 버리기로 결정. 문제 1 두 벡터 $A$와 $B$가 주어질 때, 내적 $A \cdot B$를 구하는 문제. 그냥 구현하면 된다. 난 51초만에 제출하고 넘어갔다. 이걸 16초만에 코딩하는 사람은 뭐지 ㅋㅋ 예상 난이도: 브론즈2 문제 2 이진 문자열 $x$를 주어진 규칙에 따라 변환하는 문제이다. 문제에서 요구하는 대로만 구현하면 된다. 십진법 정수를 이진법으로 표현하는 방법을 몰랐다면 어려웠을 수도? 예상 난이..

이번주면 정수론은 끝난다. 다음주에는 지금 배우는 내용을 바로 써먹을 수 있는 암호를 공부한다. $a|bc,~\gcd(a,~b)=1 \Rightarrow a|c$ $a$가 $bc$를 나눈다. 그런데 $a$와 $b$의 최대공약수가 $1$이라면 $a$는 $b$를 나누지 못한다. 따라서 $a$가 $c$를 나눠야만 한다. 직관적으로는 당연하지만 한번 증명해 보자. 증명 $a|bc$이므로 $bc=ka$를 만족하는 정수 $k$가 존재한다. 또한 $\gcd(a,~b)=1$이므로 $ax+by=1$을 만족하는 정수 $x,~y$가 존재한다. $ax+by=1$의 양변에 $c$를 곱하면 $acx+bcy=acx+kay=a(cx+ky)=c$이다. $c=k'a$ 꼴로 나타낼 수 있으므로 $a$가 $c$를 나누고, $a|c$이다. ..

개강 8주만에 정수론을 시작한다. 예제 $n$이 음이 아닌 정수일 때, $2^{a}+3^{n}=n!$를 만족하는 음이 아닌 정수 $a,~b$를 찾으시오. $n \ge 2$일 때 $n!$는 짝수이다. 그런데 $2^{a}$는 $a \ge 1$일 때 짝수, $3^{b}$는 모든 $b \ge 0$에 대해 홀수이므로 주어진 방정식은 $a=0$일 때만 해를 가질 수 있다(해가 있는지는 둘째치고). 따라서 $1+3^{b}=n!$을 만족시키는 $b$를 찾자. 계산해보면 $n=2$일 때 $a=b=0$의 해가 존재한다. 이것이 유일한 해일까? $n \ge 3$일 때 $n!$은 $3$의 배수이다. 그런데 $1+3^{b}$는 모든 음이 아닌 정수 $b$에 대해 3의 배수가 아니다. 따라서 주어진 방정식의 해는 $n=2$일 때..

10253번: 헨리 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T 가 정수로 주어진다. 각 테스트 데이터는 한 줄로 구성되며, 여기 www.acmicpc.net 뭔가 흥미로운 수학 이야기가 있다. 문제에서 시키는 대로 구현하면 된다. 단, 아주 나이브하게 이중 반복문으로 구현하면 시간 초과가 난다. 다음의 세 가지를 고려해야 한다. 1. $\frac{1}{x} \le \frac{a}{b}$인 최대의 $\frac{1}{x}$ 찾기 부동 소수점 연산을 피하기 위해 수식을 $b \le ax$로 바꾸자. 조건을 만족하는 가장 큰 $\frac{1}{x}$를 찾으려면 가장 작은 $x$를 찾으면 된다. 물론 $x=b$부터 시작하여 조건을..

매우 오랜만에 코포에 참가한다. Dashboard - Codeforces Round #677 (Div. 3) - Codeforces codeforces.com A. Boring Apartments 매우 간단한 수학 문제이다. 예상 난이도: 브론즈2 B. Yet Another Bookshelf 문제를 읽었을 땐 뭔가 어려워 보였는데, 생각해 보니 (인접한 두 segment 간의 거리)-1을 모두 더하면 답이 된다. B번을 너무 어렵게 생각해서(약 15분) D번 풀 시간이 부족해졌다.. 예상 난이도: 실버4 C. Dominant Piranha C번도 간단해 보이는 구현 문제이다. 우선 정답의 후보는 크기가 가장 큰 피라냐들로 한정한다. 가장 크지 않은 피라냐도 정답이 될 수 있는 경우가 있지만, 알고리즘을 ..