이산 제곱근을 구해보자!
때는 바야흐로 2025년 6월 11일. 일반화학 시험을 공부를 안 해간 나는 문제를 더 풀 수가 없었다. 심지어 조기 퇴실도 안 되는 시험이라 뭐 할지 고민하다가… 이산 제곱근 알고리즘을 구현해보기로 했다! …만, 당연히 시험 중이라 인터넷 검색도 안 되고 하니 그냥 직접 이산 제곱근을 구하는 알고리즘을 만들어보기로 했다. 이산 제곱근 말 그대로...
때는 바야흐로 2025년 6월 11일. 일반화학 시험을 공부를 안 해간 나는 문제를 더 풀 수가 없었다. 심지어 조기 퇴실도 안 되는 시험이라 뭐 할지 고민하다가… 이산 제곱근 알고리즘을 구현해보기로 했다! …만, 당연히 시험 중이라 인터넷 검색도 안 되고 하니 그냥 직접 이산 제곱근을 구하는 알고리즘을 만들어보기로 했다. 이산 제곱근 말 그대로...
곱셈적 함수 정수를 정의역으로 갖는 함수 $f$가 서로소인 두 정수 $a, b$에 대해 $f(a)f(b) = f(ab)$를 만족할 때, 함수 $f$를 곱셈적이라고 합니다. 대표적인 곱셈적 함수로는 다음과 같은 함수들이 있습니다. $\mu(n)$: 뫼비우스 함수 $\tau(n)$: 약수 개수 함수 $\phi(n)$: 오일러 피 함수 $\...
시간 제한 메모리 제한 2 초 1024 MB 문제 $2$ 이상의 자연수 $N$과, $1$ 이상 $N-1$ 이하의 자연수 $a$에 대하여 $a^e\equiv 1\pmod{N}$을 만족시키는 가장 작은 $1$ 이상의 정수 $e$를 법 $N$...
베주 항등식 0이 아닌 정수 $a, b$에 대해 $ax + by = \gcd(a, b)$는 정수 해를 가진다. 강의에서는 이 명칭을 사용하지는 않았다. 유클리드 알고리즘을 사용하여 위 식의 해를 구성할 수 있다. (Constructive proof) 확장 유클리드 알고리즘 이 글에 자세히 설명해 둔 덕분에 빠르게 이해하고 넘어갈 수 있었다. 기본...
나눗셈 정리 정수 $a, b\ (b \neq 0)$에 대해 $a = bq+r\ (0 \leq r \lt \left \vert b \right \vert)$인 정수 $q, r$가 유일하게 존재한다. 이때 $q := \text{quotient(몫)}$, $r = \text{remainder/residue(나머지)}$로 정의한다. 또한 정수 $a, b$...
수능 전까지는 바쁘게 살다가 수능 끝나고는 열심히 노느라 글을 이제야 쓰네요.. ㅋㅋㅋ 저는 수능을 잘 보긴 했는데 수시로 고려대를 붙어서 정시로는 KAIST에만 지원했고, 붙어서 지금은 KAIST에 다니는 중입니다. 엊그제 개강해서 벌써 강의를 열심히 듣고 있어요. 앞으로의 블로그 계획은 잠시 내려뒀던 PS를 다시 시작하면 PS 글도 쓸 것 같고,...
수능이 두 달도 채 남지 않았지만, PS는 계속됩니다… 시간 제한 메모리 제한 1 초 1024 MB 문제 나무에서 나뭇가지가 다 사라지면? 가지런하다 동우와 재우가 $1$번부터 $N$번 정점까지 총 $N$개의 정점으로 이루어진...
고3이라 바빠서 글 올리기로 해놓고 제대로 올리지도 못했습니다… 수능 끝나면 좀 더 열심히 해 보겠습니다 시간 제한 메모리 제한 2 초 1024 MB 문제 모든 격자점이 흰색으로 칠해진 좌표평면이 있다. 지호는 서 있는 점에서 $(x_i,...
시간 제한 메모리 제한 2 초 128 MB 문제 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 ...
nflight11님이 tester로 참여하셨다는 OMCB014에 참가해 보았습니다. 사실 전에 OMCB013도 참가해 보았어요. 스터디 카페에서 풀까, 아니면 집에서 풀까 고민하다 노트를 챙기지 않았다는 사실을 깨닫고 바로 집으로 달렸습니다. A $n\text{번째로 작은 소수} = 2n + 1$인 $n$의 값을 모두 더하여라. 소수들을 나열해...