Lv.0 입문

수학

약수·배수, 소수, 진법, 모듈로 — 도구 네 가지를 암기하면 시험에서 시간을 버는 구간이 됩니다.

지문 신호“나누어떨어지는”“N진법”“나머지”

0/6 해결

눈으로 보기

재생을 누르고 단계별로 동작을 따라가세요

1/5유클리드 호제법으로 gcd(48, 18)를 구합니다. 원리: gcd(a, b) = gcd(b, a % b) — 나머지로 문제가 급격히 작아집니다.

막대 길이 = 수의 크기gcd(a, b) = gcd(b, a % b) 반복 — 수학 유형의 대표 도구

개념 이해

핵심 패턴 코드는 손으로 따라 쳐 보는 것을 권장

1 / 8

비유로 이해하기

가로 12cm, 세로 8cm짜리 종이를 똑같은 크기의 정사각형으로 빈틈없이 자르려면 한 변을 몇 cm로 해야 할까요. 4cm로 자르면 가로 3장, 세로 2장으로 딱 맞습니다. 이때 4를 손으로 하나씩 세어 찾지 않고, "긴 쪽에서 짧은 쪽을 계속 떼어내고 남은 조각만 다시 본다"는 규칙 하나로 찾아냅니다. 코테의 수학은 이런 식으로 직접 세는 대신 규칙으로 크기를 줄이는 일입니다.

코테 수학은 고등 수학이 아니라 정수론 기본기(약수·배수, 소수, 진법, 모듈로) + 규칙 발견입니다.

12 × 8 종이 → 8 × 8 정사각형을 떼면 → 4 × 8 조각이 남는다
4 × 8 조각 → 4 × 4를 두 번 떼면 → 남는 것이 없다 → 답은 4

위 종이를 자르는 규칙이 그대로 유클리드 호제법입니다. gcd(12, 8)을 손으로 따라가 봅니다.

단계	a	b	a % b	다음 상태
1	12	8	4	`gcd(8, 4)`
2	8	4	0	`gcd(4, 0)`
3	4	0	—	b가 0이므로 답은 4

두 번 만에 끝났습니다. 12부터 1까지 내려가며 나눠떨어지는지 확인했다면 12번 봐야 했을 일입니다. 수가 커질수록 이 차이가 그대로 시간 차이가 됩니다.

최소공배수도 같은 결과를 재활용합니다. lcm(12, 8) = (12 / 4) × 8 = 24 — 12와 8이 처음으로 다시 만나는 지점입니다.

나머지로 줄입니다 — 두 수의 최대공약수는 재귀 한 줄입니다.

const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));

최소공배수는 나눗셈을 먼저 합니다 — a * b를 먼저 계산하면 값이 넘칠 수 있습니다.

const lcm = (a: number, b: number) => (a / gcd(a, b)) * b; // 오버플로 방지 순서

소수 판정은 √N까지만 봅니다 — i * i <= n 조건이 그 의미입니다.

function isPrime(n: number): boolean {
  if (n < 2) return false;
  for (let i = 2; i * i <= n; i++) if (n % i === 0) return false;
  return true;
}

약수는 쌍으로 모읍니다 — i를 찾으면 n / i도 같이 얻습니다.

for (let i = 1; i * i <= n; i++) {
  if (n % i === 0) { divisors.push(i); if (i * i !== n) divisors.push(n / i); }
}

전체 코드 — "두 톱니바퀴가 몇 바퀴 뒤에 처음 상태로 다시 맞물리는가":

function solution(a: number, b: number): { gcd: number; lcm: number; turnsA: number } {
  // 1단계: 나머지로 줄여 최대공약수
  const gcd = (x: number, y: number): number => (y === 0 ? x : gcd(y, x % y));
  const g = gcd(a, b);
  // 2단계: 나눗셈 먼저 하여 최소공배수
  const l = (a / g) * b;
  // 두 톱니가 다시 맞물리는 이빨 수 = lcm, a는 그 사이 lcm / a 바퀴 돈다
  return { gcd: g, lcm: l, turnsA: l / a };
}

필수 도구 네 가지는 외워두면 이 유형이 시간 벌이 구간이 됩니다.

// 1) 최대공약수 — 유클리드 호제법
const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));
const lcm = (a: number, b: number) => (a / gcd(a, b)) * b; // 오버플로 방지 순서

// 2) 소수 판정 — √N까지만
function isPrime(n: number): boolean {
  if (n < 2) return false;
  for (let i = 2; i * i <= n; i++) if (n % i === 0) return false;
  return true;
}
// 범위 내 모든 소수 → 에라토스테네스의 체 O(N log log N)

// 3) 약수 나열 — √N까지 쌍으로
for (let i = 1; i * i <= n; i++) {
  if (n % i === 0) { divisors.push(i); if (i * i !== n) divisors.push(n / i); }
}

// 4) 진법 변환
n.toString(2);        // 10진 → 2진 문자열
parseInt("1011", 2);  // 2진 문자열 → 10진

모듈로(%) 감각

순환에는 항상 모듈로: 원형 자리 (i + k) % n, 요일, 시계
JS의 %는 음수에서 음수가 나올 수 있음 → ((x % n) + n) % n
"답이 크니 1e9+7로 나눈 나머지를" → 매 덧셈·곱셈마다 % MOD (마지막에 한 번이 아니라)

소수 판정을 N까지 순회 — √N이면 충분 (i * i <= n)

for (let i = 2; i < n; i++) ...        // 잘못된 코드 — N이 10억이면 그대로 시간 초과
for (let i = 2; i * i <= n; i++) ...   // 고친 코드 — 약 3만 번이면 끝

lcm을 a * b / gcd로 — 곱이 먼저 오버플로. 나눗셈 먼저

const bad = (a * b) / gcd(a, b);   // 잘못된 코드 — a * b가 먼저 커진다
const good = (a / gcd(a, b)) * b;  // 고친 코드 — 나누고 나서 곱한다

음수 모듈로 — 위의 이중 모듈로 패턴

const bad = -1 % 5;          // 잘못된 코드 — -1 (배열 인덱스로 쓰면 터진다)
const good = ((-1 % 5) + 5) % 5; // 고친 코드 — 4

부동소수점 비교 0.1 + 0.2 === 0.3 — 정수로 스케일링하거나 오차 허용 비교

if (0.1 + 0.2 === 0.3) ...                  // 잘못된 코드 — false입니다
if (Math.abs(0.1 + 0.2 - 0.3) < 1e-9) ...   // 고친 코드

"규칙 찾기" 문제에서 손으로 몇 항을 안 써봄 — 수열 문제는 항을 6개쯤 나열하면 대부분 보입니다

큰 수 주의: JS number는 2^53까지만 정확합니다. 곱셈이 그 이상으로 커지는 문제는 BigInt(10n ** 18n)를 쓰고, BigInt와 number를 섞어 연산하면 에러라는 점을 기억하세요.
왜 호제법이 성립하는가: a와 b의 공약수는 a - b의 약수이기도 합니다. 이를 반복하면 a % b까지 내려가고, 값이 매 두 단계마다 절반 이하로 줄어들어 O(log(min(a, b)))에 끝납니다.
에라토스테네스의 체: N 이하 소수를 전부 구할 때는 판정을 N번 반복하지 말고 배수를 지워나갑니다. 안쪽 루프를 i * i부터 시작하는 것이 요령입니다.

function sieve(n: number): number[] {
  const isComposite = new Uint8Array(n + 1);
  const primes: number[] = [];
  for (let i = 2; i <= n; i++) {
    if (isComposite[i]) continue;
    primes.push(i);
    for (let j = i * i; j <= n; j += i) isComposite[j] = 1; // i*i 미만은 이미 지워짐
  }
  return primes;
}

모듈로 분배 법칙: (a + b) % M = ((a % M) + (b % M)) % M, 곱셈도 같습니다. 뺄셈만 음수가 될 수 있어 ((a - b) % M + M) % M으로 감쌉니다.

문제로 확인

난이도 순서대로 6문제 — 막히면 개념으로 돌아왔다 다시

1FizzBuzz#004다음 풀 문제쉬움 2약수의 합#060쉬움 3두 수의 최대공약수#070쉬움 4사라진 숫자#074쉬움 5배열 오른쪽으로 k칸 회전#076쉬움 6락업 기간이 걸린 사내 주식 매도#018중간