JUNSEOK
01 · 수학과 자료구조·16분·4개 레슨

이산수학 핵심

명제 논리, 집합, 순열·조합, 귀납법.

← 1-1 수 표현과 비트 연산다음 1-3 →

알고리즘의 언어. 드모르간으로 조건문을 리팩토링하고, 귀납법으로 재귀를 증명할 수 있는 수준이 목표다.

0. "이산"이 뭔데? — 초심자용

0-1. 연속 수학 vs 이산 수학

  • 연속 수학: 숫자가 끊어지지 않고 이어짐. 미분·적분·물리 같은 곳에 쓰임. 값이 1.0과 2.0 사이에 무한히 많다.
  • 이산 수학(Discrete Math): 값이 딱딱 끊어짐. 0과 1, 참/거짓, 개수, 노드 개수, 페이지 수. 컴퓨터가 다루는 모든 것이 여기에 속한다 — 비트는 0 아니면 1이고, 유저 수는 정수고, 그래프의 노드는 셀 수 있다.

0-2. 프론트엔드가 이걸 왜 알아야 하는가

매일 쓰지만 안 보이는 이산수학 예시:

  • if (!(user.isAdmin && user.isLoggedIn)) 를 리팩토링할 때 → 명제 논리(드모르간)
  • 배열에서 중복 제거 → 집합 연산
  • "8자리 비밀번호, 숫자+문자+특수문자" 경우의 수 → 순열·조합
  • 해시맵이 어떻게 작동하는지 → 모듈러 연산
  • 재귀 함수가 왜 끝나는지 증명 → 수학적 귀납법

프론트 개발자가 이걸 모르고도 당장은 기능을 만들 수 있다. 하지만 "왜 이 코드가 맞는가"를 설명하거나, 버그 없는 조건문을 안정적으로 작성하려면 반드시 필요하다.

0-3. 이 장에서 다루는 큰 줄기

분야뭐 하는 건데실무에서
명제 논리참/거짓의 조합 규칙복잡한 조건문 리팩토링
집합원소의 모음과 연산중복 제거, 교집합
순열·조합경우의 수 세기경우의 수 추정, 해시 충돌
모듈러"나머지" 연산해시, 순환 버퍼
귀납법"n일 때 참이면 n+1일 때도" 증명재귀 정당화

1. 왜 이산수학이 먼저인가

알고리즘은 결국 "유한한 구조 위의 연산"이다. 명제 논리는 if 조건을 다루고, 집합은 자료구조를 다루고, 순열·조합은 경우의 수를 다루고, 모듈러는 해시를 다루고, 귀납법은 재귀를 정당화한다. 이산수학의 기본기 없이 자료구조를 외우면 응용이 안 된다.

2. 명제 논리

2-1. 기본 연산자

기호이름JS 대응의미
¬부정!뒤집기
∧AND&&둘 다 참
∨OR||하나라도 참
→함의!a || ba면 b
↔동치a === b서로 같음

2-2. 드모르간 법칙

¬(A ∧ B) ≡ ¬A ∨ ¬B
¬(A ∨ B) ≡ ¬A ∧ ¬B

복잡한 조건문을 리팩토링하는 수학적 근거다.

// Before
if (!(user.isAdmin && user.isActive)) {
  return;
}

// After (드모르간)
if (!user.isAdmin || !user.isActive) {
  return;
}

두 가지 중 어느 쪽이 더 읽히는가는 맥락에 따라 다르다. "둘 다 만족"을 부정하는 맥락이면 !(A && B), "둘 중 하나라도 문제"를 체크하는 맥락이면 !A || !B.

2-3. early return과의 조합

// Before: 깊은 중첩
function submit(form) {
  if (form.email && form.email.includes('@')) {
    if (form.password && form.password.length >= 8) {
      // 실제 로직
    }
  }
}

// After: 드모르간 + guard clause
function submit(form) {
  if (!form.email || !form.email.includes('@')) return;
  if (!form.password || form.password.length < 8) return;
  // 실제 로직
}

2-4. 대우 (Contrapositive)

A → B의 대우는 ¬B → ¬A. 둘은 논리적으로 동치다. 증명에서 "∼라면 ∼이다"가 어려울 때, 대우를 증명하면 동일한 효과를 얻는다.

3. 집합

3-1. 기본 연산

연산기호JS (Set)
합집합A ∪ Bnew Set([...a, ...b])
교집합A ∩ Bnew Set([...a].filter(x => b.has(x)))
차집합A \ Bnew Set([...a].filter(x => !b.has(x)))
대칭 차집합A △ B(A ∪ B) \ (A ∩ B)

3-2. 왜 Set을 쓰는가

배열의 includes는 O(n). Set의 has는 평균 O(1). 두 배열의 교집합을 구할 때 배열끼리만 쓰면 O(n·m)이지만, Set으로 옮기면 O(n + m)이 된다.

// O(n * m) - 배열만 사용
function intersectSlow(a, b) {
  return a.filter(x => b.includes(x));
}

// O(n + m) - Set 사용
function intersectFast(a, b) {
  const bSet = new Set(b);
  return a.filter(x => bSet.has(x));
}

⚠️ 함정: Set의 has가 "O(1)인 이유"는 해시 기반이기 때문인데, 최악의 경우는 O(n). 해시 충돌이 극단적으로 일어나는 (공격적으로 구성된) 입력에서는 보장이 깨진다. 실전에선 신뢰해도 좋지만 알고는 있어야 한다.

3-3. 멱집합과 부분집합

  • 멱집합 P(A): A의 모든 부분집합의 집합. 크기는 2^|A|.
  • {1, 2, 3}의 멱집합 → {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} (총 8개)

부분집합 생성은 비트마스크로 쉽게 된다.

function powerSet(arr) {
  const n = arr.length;
  const result = [];
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(arr[i]);
    }
    result.push(subset);
  }
  return result;
}

4. 순열과 조합

4-1. 공식

  • 순열 nPr = n! / (n-r)! — 순서가 중요
  • 조합 nCr = n! / (r! × (n-r)!) — 순서 무관
  • 중복 순열 = n^r — 같은 원소 재사용 허용

4-2. 직관

  • 5명 중 3명을 뽑아 줄 세우기 → 순열 5P3 = 60
  • 5명 중 3명을 뽑아 팀 만들기 → 조합 5C3 = 10

4-3. 백트래킹으로 순열 생성

function permutations(arr) {
  const result = [];
  const used = new Array(arr.length).fill(false);
  const current = [];

  function backtrack() {
    if (current.length === arr.length) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      current.push(arr[i]);
      backtrack();
      current.pop();
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

permutations([1, 2, 3]);
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

4-4. 조합 생성

function combinations(arr, r) {
  const result = [];
  const current = [];

  function backtrack(start) {
    if (current.length === r) {
      result.push([...current]);
      return;
    }
    for (let i = start; i < arr.length; i++) {
      current.push(arr[i]);
      backtrack(i + 1);  // 같은 건 두 번 뽑지 않음
      current.pop();
    }
  }

  backtrack(0);
  return result;
}

combinations([1, 2, 3, 4], 2);
// [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

5. 모듈러 연산

5-1. 기본 성질

(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a × b) mod n = ((a mod n) × (b mod n)) mod n

덧셈과 곱셈은 "먼저 모듈러를 취해도 결과가 같다". 큰 수 계산의 오버플로 방지에 필수다.

5-2. 해시 함수가 % size를 쓰는 이유

해시 값은 임의의 정수. 이를 버킷 인덱스(0 ~ size-1)로 매핑하려면 % size가 필요하다. size가 소수(prime)일 때 충돌이 적어진다 — 합성수면 특정 패턴에 쉽게 몰리기 때문.

5-3. ⚠️ 함정: 음수 모듈러

-1 % 5;   // JS: -1   (C, Java와 동일)
-1 mod 5; // 수학적으로는 4 (항상 양수)

JS에서 "항상 양수인 모듈러"를 쓰려면 보정이 필요하다.

function mod(a, n) {
  return ((a % n) + n) % n;
}
mod(-1, 5);  // 4

원형 배열 인덱싱, 오른쪽으로 회전 등에서 이 패턴을 많이 쓴다.

6. 수학적 귀납법

6-1. 구조

어떤 명제 P(n)이 모든 자연수 n에 대해 참임을 증명하려면:

  1. 기저 (Base): P(1)이 참임을 보인다.
  2. 귀납 (Inductive step): P(k)가 참이면 P(k+1)도 참임을 보인다.

그러면 도미노처럼 P(1) → P(2) → P(3) → … 모든 경우가 참이 된다.

6-2. 재귀 정당성 증명

재귀 함수가 올바른지 증명할 때 자연스럽게 귀납법이 쓰인다.

function sum(n) {
  if (n === 0) return 0;          // 기저: sum(0) = 0 ✓
  return n + sum(n - 1);          // 귀납: sum(k-1)이 옳으면 sum(k)도 옳음
}
  • P(0): sum(0) = 0 — 참 (기저).
  • P(k)가 참이라 가정: sum(k) = 0 + 1 + ... + k.
  • P(k+1) 증명: sum(k+1) = (k+1) + sum(k) = (k+1) + k(k+1)/2 = (k+1)(k+2)/2 ✓.

6-3. 반복문 불변량 (Loop Invariant)

반복문의 정당성도 같은 구조로 증명한다. "매 반복 직전/직후에 유지되는 성질"을 찾으면 된다.

function findMax(arr) {
  let max = arr[0];
  // 불변량: max는 arr[0..i-1] 중 최댓값
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}
  • 초기 (i=1): max = arr[0]은 arr[0..0]의 최댓값 ✓
  • 유지: i번째 반복에서 arr[i] > max면 갱신 → 여전히 arr[0..i]의 최댓값
  • 종료 (i=n): max = arr[0..n-1]의 최댓값 ✓

이게 "알고리즘 증명"의 실체다. 코테 고수가 구현 전에 "불변량이 뭐지?"를 먼저 생각하는 이유가 이것이다.

연습 문제

  1. 드모르간 법칙을 써서 다음 조건을 리팩토링하라: !(a > 0 && b > 0 && c > 0).
  2. 집합 {1, 2, 3, 4}의 멱집합을 비트마스크로 출력하라.
  3. 5C3 = 10임을 공식과 재귀 C(n, r) = C(n-1, r-1) + C(n-1, r) 양쪽으로 확인하라.
  4. 음수 인덱스가 들어올 수 있는 원형 배열 접근자 circular(arr, i)를 작성하라.
  5. sum(n) = n(n+1)/2을 수학적 귀납법으로 증명하라.

연습 문제 정답

1. 드모르간 리팩토링

// 원본: 하나라도 0 이하
!(a > 0 && b > 0 && c > 0)
// 드모르간
!(a > 0) || !(b > 0) || !(c > 0)
// 정리
a <= 0 || b <= 0 || c <= 0

2. 비트마스크 멱집합

const arr = [1, 2, 3, 4];
for (let mask = 0; mask < (1 << arr.length); mask++) {
  const subset = arr.filter((_, i) => mask & (1 << i));
  console.log(subset);
}
// [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3], [4], [1,4], ..., [1,2,3,4]

3. 5C3

  • 공식: 5! / (3! × 2!) = 120 / (6 × 2) = 10
  • 재귀: C(5,3) = C(4,2) + C(4,3) = 6 + 4 = 10 ✓
    • C(4,2) = C(3,1) + C(3,2) = 3 + 3 = 6
    • C(4,3) = C(3,2) + C(3,3) = 3 + 1 = 4

4. 원형 배열

function circular(arr, i) {
  return arr[((i % arr.length) + arr.length) % arr.length];
}
circular([10, 20, 30], -1);  // 30
circular([10, 20, 30], 5);   // 30 (5 mod 3 = 2)

5. 수학적 귀납법

기저 n = 0: sum(0) = 0 = 0 × 1 / 2 ✓

가정 sum(k) = k(k+1)/2가 참이라고 하자.

귀납 sum(k+1) 증명:

sum(k+1) = (k+1) + sum(k)
         = (k+1) + k(k+1)/2
         = (k+1)(2 + k) / 2
         = (k+1)(k+2) / 2 ✓

체크리스트

  • 드모르간 법칙으로 복잡한 if 조건을 재작성할 수 있다
  • 대우를 이용한 증명을 안다
  • 교집합을 Set으로 O(n+m)에 구현할 수 있다
  • 멱집합의 크기가 2^n인 이유를 안다
  • 순열과 조합을 상황에 맞게 구분할 수 있다
  • 순열/조합을 백트래킹으로 구현할 수 있다
  • 모듈러 연산의 분배 법칙을 안다
  • 음수 모듈러를 양수로 정규화하는 관용구를 안다
  • 수학적 귀납법의 기저/귀납 단계를 구분할 수 있다
  • 반복문 불변량으로 알고리즘의 정당성을 설명할 수 있다

이전: 1-1. 수 표현과 비트 연산 | 다음: 1-3. 복잡도 분석

진도 체크시작 전
NEXT · 1-3

복잡도 분석

빅오, 분할상환, JS 내장 연산의 숨은 복잡도.

이어서 학습하기 →