Skip to content
code-drill
커리큘럼
유형
문제
GitHub
(opens in new tab)
←
→
to navigate
유형별 정리
자주 나오는 유형
커리큘럼이 순서대로 익히는 길이라면, 여기는 필요할 때 바로 펴보는 참고서예요. 유형마다 언제 쓰는지, 어떻게 짜는지, 어디서 실수하는지를 한 장에 모았어요.
수학·정수론
약수·소수·최대공약수처럼 수의 성질을 다루는 유형이에요. 대부분 √n이나 log 시간으로 줄이는 게 핵심이에요.
약수 구하기
약수는 짝으로 다녀요. √n까지만 훑어 O(√n)에 끝내요.
O(√n)
소수 판별
약수는 짝으로 다니니, √n까지만 나눠봐도 소수인지 알아요.
O(√n)
에라토스테네스의 체
배수를 미리 지워, N 이하의 소수를 한 번에 걸러내요.
O(N log log N)
최대공약수와 최소공배수
유클리드 호제법으로 GCD를 구하고, 곱으로 LCM을 얻어요.
O(log(min(a,b)))
소인수분해
작은 소수부터 나눠떨어질 때까지 나누며 소인수를 뽑아요.
O(√n)