나름 개발자의 IT블로그

인터넷을 찾아보다가 우연히 Online Math Contest라는 사이트를 알게 되었다. 일본에서 운영하는 온라인으로 수학문제을 푸는 대회사이트이다. 딱 앳코더의 수학버전이다. 앳코더나 코드포스처럼 콘테스트에 참여하면 레이팅을 얻고 닉네임에 색을 입힐 수 있는 시스템인 것 같다. 재밌어보여서 바로 가입하고 가장 최근에 있었던 OMC 207 (for beginners)에 도전해봤다. 결과는 2솔하고 손도 못댔다. ㅋㅋ 출제 범위는 고등 ~ 대학 수학정도이고 아직 많이 보진 않았지만 대수학, 정수론, 기하학 위주로 출제되는 것 같다. 스코어보드를 봤는데 사람들 푸는 속도가 어마어마했다. 그리고 수학 대회이기 때문에 코드를 작성하면 부정행위이다. (애초에 코딩으로 해결할 수 있는 문제가 많지 않다.) 대신에 ..

(알고리즘보단 수학에 가까운 내용인데 백준문제 풀다가 나와서 알고리즘 카테고리에 정리하겠습니다.) 백준 문제 풀다가 재밌고 신기한 정리가 있어서 정리하고자 한다. 문제는 여기 https://www.acmicpc.net/problem/2710 2710번: 삼각형 정원 각각의 테스트에 대해 한 줄에 fx1, fy1, fx2, fy2, rl(fx1

요즘 빠른 3솔을 목표로 하고 있는데 이번은 C에서 너무 막혔다. A - Square Counting [Solved!] $n+1$개의 수 $a_1, a_2, ..., a_n, a_{n+1}$이 주어질 때 $0\le a_i < n$이거나 $a_i = n^2$을 만족한다. 그리고 $\sum_{i=1}^{n+1} a_i = s$를 만족하는 $a_i = n^2$의 개수를 구하는 문제이다. $s$에 $n^2$을 최대한 많이 넣으면 된다. 이를 구하려면 $\lfloor \frac{s}{n^2} \rfloor$을 계산하면 된다. B - Quality vs Quantity [Solved!] 수열 $a_1, a_2, \dots, a_n$이 주어지고 각 수를 빨간색, 파란색, 색칠하지 않음 중 하나의 상태로 만들 때 빨간..

민트를 복구할 수 있는 기회였는데 아쉽게 실패하고 말았다. 3솔에 블루퍼포가 나와서 싱글벙글하고 있었는데 B가 TLE로 터져버렸다. 알고보니 sys.stdin.readline을 쓰지 않아 생긴 문제였다. C문제도 같은 이유로 프리테스트에서 TLE가 발생했지만 B에서도 나올줄은 전혀 몰랐다. (두 문제 모두 $O(n)$으로 해결했었다.) 앞으로는 확인을 꼼꼼히 해야겠다. (후에 라인 추가로 AC받긴 했다.) A - Reverse [Solved!] 배열의 중간 일부 구간을 뒤집었을 때 사전순으로 가장 앞서는 배열을 출력하는 문제이다. 인덱스와 배열값이 다른 부분이 나오는 곳부터 그 이후에 나오는 최솟값이 있는 곳까지 뒤집으면 된다. B - Odd Swap Sort [Solved?] 배열에서 연속한 두 원소의..

문제가 그렇게 어렵지 않고 재미있는 문제들이 많아 남겨보고자 한다. (푸는대로 업데이트 할 예정..) A. 2의 보수 정수를 하나 입력받아 그 수의 2의 보수를 출력하면 된다. 입력받은 정수를 $a$라고 하면 $a \oplus (2^{32}-1) + 1$ 이 정답이다. (지난 코드포스 768에서 영감받음) B. 조커 찾기 카드 27장을 섞는 방법이 주어졌을 때 $n$번 섞고 난 후 조커($1$번 카드)가 어디있는지 찾는 문제이다. - 덱 위에서 13장을 왼쪽, 14장을 오른쪽으로 보낸다. - 배열 $a$가 있을 때 $i$가 홀수이면 오른쪽, 짝수이면 왼쪽에서 $a_i$장을 가져와 새 덱 밑에 추가한다. 문제에서 나타낸대로 구현하면 된다. 파이썬으로 큐를 사용해봤는데 시간초과가 나서 리스트 전체를 조작하는..

이전 글에서 피보나치 수를 구하다가 빠른 거듭제곱이 나와 따로 글로 남기게 되었다. 거듭제곱을 위해 다음 코드를 작성하면 $O(N)$의 시간이 필요하다. def pow(a,n): r = 1 for _ in range(n): r *= a return r 위 코드는 거듭제곱을 $a^n=a^{n-1} \times a$ 방식으로 구한다. 이것을 빠르게 해 보자! $n$이 짝수이면 $a^n = a^{n/2} \times a^{n/2}$ $n$이 홀수이면 $a^n = a^{n/2} \times a^{n/2} \times a$ 가 된다. 이제 이것을 재귀적으로 계산하면 된다. 예를 들어 $3^{60}$을 계산해보자 $3^{60} = 3^{30} \times 3^{30}$ $3^{30} = 3^{15} \times 3..