집합과 논리: 드모르간과 JOIN

가입 폼의 보내기 버튼이다. 이름·이메일을 다 쓰고 약관에 동의해야 눌린다.

<button disabled={!(name && email && agreed)}>보내기</button>

동료가 괄호가 읽기 어렵다며 disabled={!name && !email && !agreed}로 바꿨다. 그 뒤로 이름만 쓰고도 버튼이 눌린다는 버그 신고가 왔다. !를 하나씩 안으로 넣었을 뿐인데 무엇이 달라졌을까? 이 Unit은 "둘 다", "하나라도", "아님"을 집합과 논리라는 두 모양으로 보고, 조건을 뒤집는 규칙인 드모르간 법칙과 SQL JOIN까지 잇는다.

집합: 중복 없는 원소의 묶음

집합(set)은 중복 없는 값의 묶음이고, 그 안의 값 하나하나를 원소(element)라고 한다. JavaScript의 Set, Python의 set이 바로 집합이다. 『한입 알고리즘』 1장의 new Set(orders.map(o => o.sku))도 주문에서 중복 없는 상품 코드의 집합을 만든다.

집합 두 개로 자주 하는 일은 세 가지다. 쿠폰을 받은 사람 A = 4와 실제로 산 사람 B = 5로 보자.

$A \cap B = \{3, 4\}$

∩는 교집합(intersection)으로, "A와 B 둘 다에 있는 원소"라고 읽는다. 쿠폰을 받고 산 사람이다.

$A \cup B = \{1, 2, 3, 4, 5\}$

∪는 합집합(union)으로, "A와 B 중 적어도 한쪽에 있는 원소"라고 읽는다. 3과 4는 양쪽에 있지만 한 번만 들어간다.

$A - B = \{1, 2\}$

−는 차집합(difference)으로, "A에는 있고 B에는 없는 원소"라고 읽는다. 쿠폰을 받고도 안 산 사람, 곧 다시 알림을 보낼 사람이다. 순서를 바꾼 B − A는 5로, 쿠폰 없이 산 사람이다.

1const coupon = new Set([1, 2, 3, 4])2const bought = new Set([3, 4, 5])3const both = new Set<number>()4const rest = new Set<number>()5for (const x of coupon) {6  if (bought.has(x)) both.add(x)7  else rest.add(x)8}9const either = new Set([...coupon, ...bought])10console.log('둘 다:', ...both)11console.log('쿠폰만:', ...rest)12console.log('하나라도:', ...either)

둘 다: 3 4
쿠폰만: 1 2
하나라도: 1 2 3 4 5

원소를 하나씩 보며 다른 집합에 있는지 has로 물으면 교집합과 차집합을 반복문으로 구할 수 있다. 반복문을 직접 쓰지 않아도 된다. Python은 연산자 &, |, -로 쓰고, JavaScript는 2024년에 Set에 같은 일을 하는 메서드가 생겼다.

1const coupon = new Set([1, 2, 3, 4])2const bought = new Set([3, 4, 5])3coupon.intersection(bought) // Set {3, 4}4coupon.union(bought) // Set {1, 2, 3, 4, 5}5coupon.difference(bought) // Set {1, 2}

intersection·union·difference는 MDN 기준 Baseline 2024로, 2024년 6월부터 주요 브라우저 최신 버전이 모두 지원한다(MDN: Set.prototype.intersection, MDN: Set.prototype.union, MDN: Set.prototype.difference). 오래된 브라우저까지 지원해야 하면 [...coupon].filter(x => bought.has(x))처럼 filter로 쓴다.

논리 연산: 그리고, 또는, 아님

집합의 "둘 다", "하나라도", "앞에만"은 조건문에서도 그대로 나온다. 참(true)·거짓(false)으로 하는 계산을 논리 연산(logical operation)이라고 하고, 기본은 셋이다.

원소 x 하나로 보면 1절의 집합 연산이 그대로 이 조건식이 된다. inA를 x가 A에 있는지(a.has(x)), inB를 x가 B에 있는지라고 하면 이렇다.

• x가 A ∩ B에 있다 = inA && inB
• x가 A ∪ B에 있다 = inA || inB
• x가 A − B에 있다 = inA && !inB

조건이 a, b 두 개면 참·거짓 조합은 2 × 2 = 4가지다. 이 네 경우를 빠짐없이 한 줄씩 적고 식의 값을 붙인 표를 진리표(truth table)라고 한다.

a && b는 마지막 줄 하나에서만 참이고, a || b는 첫 줄 하나에서만 거짓이다. 조건이 n개면 줄은 2ⁿ개다(조건마다 참·거짓 두 갈래라 2 × 2 × …, Unit 1). 조건 세 개면 8줄이라 아직 손으로 쓸 만하다.

드모르간 법칙: 아님을 안으로 넣으면 그리고와 또는이 바뀐다

1for (const a of [false, true]) {2  for (const b of [false, true]) {3    const left = !(a && b)4    const right = !a || !b5    console.log(a, b, left, right)6  }7}

false false true true
false true true true
true false true true
true true false false

두 규칙을 합쳐 드모르간 법칙(De Morgan's laws)이라고 한다.

$\neg(a \land b) = \neg a \lor \neg b$

"'a 그리고 b'라는 말 전체가 아님은, a가 아님 또는 b가 아님과 같다"고 읽는다. 코드로는 !(a && b) === (!a || !b)다. 예를 들어 a = true, b = false면 왼쪽은 !(false) = true, 오른쪽은 false || true = true다.

$\neg(a \lor b) = \neg a \land \neg b$

"'a 또는 b'라는 말 전체가 아님은, a도 아니고 b도 아님과 같다"고 읽는다. 코드로는 !(a || b) === (!a && !b)다.

외울 것은 하나다. !를 괄호 안으로 넣으면 각 조건을 뒤집고, &&와 ||를 서로 바꾼다. 처음 장면에 대 보자.

!만 넣고 &&를 ||로 바꾸지 않아서 "하나라도 빠졌다"가 "셋 다 빠졌다"로 바뀌었다. 이런 실수를 줄이는 쉬운 길은 긍정형 이름을 하나 만들고 한 번만 뒤집는 것이다. const canSubmit = name && email && agreed를 두고 disabled={!canSubmit}으로 쓰면 바꿀 식이 없다.

&&와 ||를 섞을 때는 묶이는 순서도 본다. JavaScript는 &&를 ||보다 먼저 계산해서 a || b && c는 a || (b && c)다(MDN: 논리 AND). Python의 not > and > or, SQL의 NOT > AND > OR도 같은 순서다(Python 문서: 연산자 우선순위, PostgreSQL 문서: 연산자 우선순위). 헷갈리면 괄호를 친다.

단락 평가: 답이 정해지면 뒤를 보지 않는다

a && b에서 a가 false면 b가 무엇이든 결과는 false다. 그래서 JavaScript와 Python은 b를 아예 계산하지 않는다. a || b도 a가 true면 b를 건너뛴다. 이것을 단락 평가(short-circuit evaluation)라고 한다(MDN: 논리 AND, Python 문서: 불리언 연산). user && user.name이 user가 null일 때 오류 없이 지나가는 것도, isCached() || fetchData()가 캐시가 있으면 요청을 보내지 않는 것도 이 덕분이다. 그래서 순서에도 뜻이 있다. a && b와 b && a는 값이 같아도 먼저 계산되는 쪽이 다르다. user.name && user는 user가 null이면 앞쪽 user.name에서 오류가 난다. 앞에 오는 조건이 뒤 조건의 안전장치가 되도록 쓴다.

SQL로 잇기: JOIN은 교집합을 닮았다

사용자 표 users와 주문 표 orders가 있다. 주문이 있는 사용자만 보려면 INNER JOIN을 쓴다.

SELECT u.name, o.id
FROM users u
JOIN orders o ON o.user_id = u.id

JOIN(INNER JOIN)은 users의 행마다 ON 조건을 만족하는 orders의 행을 짝지어 한 행씩 만든다(PostgreSQL 문서: 조인). 짝이 없는 사용자와 짝이 없는 주문은 결과에 없다. 양쪽에 다 있는 것만 남으니 교집합을 닮았다.

LEFT JOIN은 먼저 INNER JOIN을 하고, 짝을 못 찾은 왼쪽 표의 행은 오른쪽 열을 NULL로 채워 덧붙인다(같은 문서). 그래서 왼쪽 표의 행은 결과에 적어도 한 번씩 다 나온다. 여기에 WHERE o.id IS NULL을 붙이면 "주문이 없는 사용자"만 남는다. 사용자 집합에서 주문한 사용자를 뺀 차집합이다.

WHERE의 AND·OR는 앞 절의 논리 연산 그대로다. WHERE status = 'paid' OR status = 'shipped' AND total > 100000은 AND가 먼저 묶여서 "결제됨 전부, 또는 배송 중이면서 10만 원 초과"가 된다. "결제됨 또는 배송 중, 그중 10만 원 초과"를 원했다면 OR 쪽에 괄호를 친다.

하나 더 조심할 것은 NULL이다. SQL의 조건은 참·거짓 말고 "알 수 없음"(NULL)이라는 셋째 값이 될 수 있다. WHERE id NOT IN (SELECT user_id FROM orders)로 주문 없는 사용자를 찾는데 orders.user_id에 NULL이 하나라도 있으면, 어느 사용자에게도 NOT IN이 참이 되지 않는다(NULL은 "알 수 없음"이라 "없다"고 단정할 수 없어서). PostgreSQL 문서는 같은 값이 없고 오른쪽에 NULL이 하나라도 있으면 NOT IN의 결과가 참이 아니라 NULL이라고 적는다(PostgreSQL 문서: NOT IN). WHERE는 참인 행만 남기므로 결과가 0행이 된다. 주문 없는 사용자 찾기에는 앞의 LEFT JOIN … WHERE o.id IS NULL이나 NOT EXISTS를 쓴다.

INTERSECT·UNION·EXCEPT가 각각 교집합·합집합·차집합이고, UNION은 DISTINCT처럼 중복 행을 없앤다(PostgreSQL 문서: 쿼리 합치기). JOIN 결과의 행 수가 예상보다 많으면 "한 행이 여러 행과 짝지어졌나?"를 먼저 의심한다.

이 Unit이 쓰이는 곳

• 『한입 알고리즘』 0장 루프 안의 includes: 3절 "Set으로 바꾸기"에서 고른 id를 Set에 담아 has로 묻는다. 이 Unit 2절에서 원소 x가 A에 있는지를 a.has(x)로 묻는 것과 같은 일이다.
• 『한입 알고리즘』 1장 해시: 첫 장면의 new Set(orders.map(o => o.sku))가 중복 없는 상품 코드의 집합을 만든다. 4절에서는 배열을 Set에 넣으면 내용이 같아도 다른 원소가 된다.
• 『한입 CS』 8장 데이터베이스: 2절의 조건 user_id = 7 AND created_at > 지난주를 복합 인덱스로 좁히고, 4절은 WHERE id = 1 AND stock > 0으로 재고가 남았을 때만 차감한다. 둘 다 두 조건이 모두 참인 행만 남기는 "그리고"다.

|A| + |B| + |C| = 5 + 4 + 3 = 12
|A ∪ B ∪ C| = ?