개수를 세는 문제에서는 가운데에서 바깥쪽으로 영역을 채우세요. 모든 집합, 그다음 두 집합씩, 그다음 한 집합, 마지막으로 바깥쪽 순서입니다.
포함·배제 원리로 확인하세요: |A ∪ B| = |A| + |B| − |A ∩ B|.
관계는 모든 쌍에서 각 성질을 검사하고, 성립하지 않으면 반례를 하나 드세요.
함수는 B의 각 원소로 들어오는 화살표를 세세요. 많아야 하나이면 단사이고, 적어도 하나이면 전사입니다.
그래프 이론
악수 보조정리
Σ deg(v) = 2|E|
완전그래프
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
정규그래프
|E| = n·k/2
트리와 포리스트
|E| = n − 1, |E| = n − c
트리의 잎
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
오일러
회로: 모든 차수가 짝수; 경로: 차수가 홀수인 정점이 정확히 2개
Kn의 해밀턴 회로
(n − 1)!/2
다익스트라 갱신
d(v) = min(d(v), d(u) + w(u, v))
길이 L의 보행
(Mᴸ)ij
방법
모든 정점의 차수를 적으세요. 차수의 합은 간선 수의 두 배입니다.
오일러 문제에서는 그래프가 연결되어 있는지 확인하고 차수가 홀수인 정점의 수를 세세요.
트리에서는 간선이 n − 1개라는 사실과 악수 보조정리를 사용하세요.
다익스트라에서는 임시 거리 표를 만들고, 매 단계마다 확정되지 않은 정점 중 거리가 가장 작은 정점을 확정하세요.
최소 신장 트리는 간선을 가중치 순으로 정렬해 사이클을 만드는 간선을 건너뛰거나(크루스칼), 시작 정점에서 트리 하나를 키워 가세요(프림).
정수론과 모듈러 연산
나머지가 있는 나눗셈
a = q·n + r, 0 ≤ r < n
유클리드
gcd(a, b) = gcd(b, a mod b)
최소공배수
lcm(a, b) = a·b/gcd(a, b)
역행렬
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
일차 합동식
a·x ≡ b → x ≡ a⁻¹·b (mod n)
오일러 피 함수
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
페르마
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
방법
먼저 모든 수를 n으로 나눈 나머지로 줄이세요. 나머지는 0부터 n − 1 사이에 있습니다.
최대공약수는 유클리드 호제법으로 계속 나누세요. 0이 아닌 마지막 나머지가 최대공약수입니다.
역원은 확장 알고리즘을 실행해 a의 계수를 취하고, 음수이면 n을 더하세요.
a·x ≡ b는 a⁻¹을 곱해서 풀고, 두 합동식은 x = r₁ + m₁k로 써서 합치세요.
거듭제곱은 지수를 이진수로 쓰고 거듭 제곱하세요. RSA에서는 d = e⁻¹ mod φ(n)이고 φ(n) = (p − 1)(q − 1)입니다.
2연습 문제
1.명제논리와 증명보통
c → a와(과) 논리적으로 동치인 식은 어느 것인가? 클릭하세요.
c → a
1¬a ∧ ¬c
2¬c → ¬a
3¬a → ¬c
4a → c
2.명제논리와 증명어려움
진리표의 16개 행 중 몇 개에서 ¬((¬c ∧ d) ∨ c) ∧ ((¬b ∨ ¬a) ∧ a)이(가) 참인가? 이 수를 N(이)라 하자.
¬((¬c ∧ d) ∨ c) ∧ ((¬b ∨ ¬a) ∧ a)
N =
3.집합, 관계, 함수보통
R = {(1, 2), (2, 2), (3, 1), (3, 2)}은(는) {1, 2, 3} 위의 관계이다. R을 반사적으로 만들려면 추가해야 하는 순서쌍은 최소 몇 개(k)인가?
R = {(1, 2), (2, 2), (3, 1), (3, 2)}
k =
4.집합, 관계, 함수어려움
화살표 그림은 A = {1, 2, 3}, B = {a, b, c, d}인 함수 f: A → B를 보여 줍니다. f에 맞는 설명을 클릭하세요.
f = {(1, b), (2, d), (3, b)}
1단사이지만 전사는 아님
2전사이지만 단사는 아님
3전단사
4둘 다 아님
5.그래프 이론보통
트리에 차수가 3인 정점 3개, 차수가 2인 정점 3개이(가) 있고 나머지 정점은 모두 잎(차수 1)이다. 잎은 몇 개(L)인가?
3 × deg 33 × deg 2
L =
6.그래프 이론어려움
C에서 출발해 같은 정점으로 돌아오는 길이 2의 닫힌 보행은 몇 개인가? 보행에서는 정점과 간선이 반복될 수 있다. 그 수를 N(이)라 하자.
M = 인접 행렬L = 2
N =
7.정수론과 모듈러 연산보통
15x ≡ 9 (mod 17)을(를) 푸시오. 0 < x < 17인 해 x을(를) 구하시오.
15x ≡ 9 (mod 17)
x =
8.정수론과 모듈러 연산어려움
89은(는) 소수이다. 페르마의 소정리를 이용해 1898781 mod 89을(를) 구하시오.
p = 89k = 98781
1898781 mod 89 =
3용액
1.명제논리와 증명
답: ¬a → ¬c
논리적 동치: 두 식은 진리표의 모든 행에서 값이 같으면 동치(≡)입니다. 항진명제는 모든 행에서 1이고, 모순은 모든 행에서 0이며, 우연명제는 둘 다 아닙니다. 유용한 법칙: 드모르간 법칙 ¬(a ∧ b) ≡ ¬a ∨ ¬b와 ¬(a ∨ b) ≡ ¬a ∧ ¬b, a → b ≡ ¬a ∨ b ≡ ¬b → ¬a(대우), ¬(a → b) ≡ a ∧ ¬b, 그리고 분배법칙 a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
법칙
함의는 대우 ¬b → ¬a와 동치이며, 역 b → a나 이(裏) ¬a → ¬b와는 동치가 아닙니다.
c → a ≡ ¬a → ¬c
진리표로 확인
a = 1, c = 1: 1 | 0 1 1 1
a = 1, c = 0: 1 | 0 0 1 0
a = 0, c = 1: 0 | 0 1 0 1
a = 0, c = 0: 1 | 1 1 1 1
답
¬a → ¬c
막대 뒤의 열은 보기를 표시된 순서대로 나타낸 것입니다.
2.명제논리와 증명
답: N = 1
진리표: 서로 다른 변수가 n개인 식은 참값(1 = 참, 0 = 거짓)의 모든 조합마다 하나씩 2ⁿ개의 행을 가집니다. 안쪽부터 바깥쪽으로 작업하고 모든 부분식에 각각 열을 주세요. ¬a는 값을 뒤집습니다. a ∧ b는 둘 다 1일 때만 1입니다. a ∨ b는 둘 다 0일 때만 0입니다. a → b는 a = 1이고 b = 0일 때만 0입니다. a ↔ b는 양쪽이 같을 때 1입니다.
관계: 집합 X 위의 관계 R은 순서쌍 (x, y)의 집합입니다. X의 모든 x에 대해 (x, x) ∈ R이면 R은 반사적, (x, y) ∈ R이면 항상 (y, x) ∈ R도 성립하면 대칭적, (x, y)와 (y, x)가 모두 R에 있는 경우가 x = y일 때뿐이면 반대칭적, R에 (x, y)와 (y, z)가 있으면 (x, z) ∈ R이어야 하면 추이적입니다. 동치 관계는 반사적이고 대칭적이며 추이적이고, X를 서로소인 류로 나눕니다.
추가할 쌍
{(1, 1), (3, 3)}
세기
k = 2
답
k = 2
4.집합, 관계, 함수
답: 둘 다 아님
함수와 세기: 함수 f: A → B는 A의 모든 원소에 B의 상을 정확히 하나씩 대응시킵니다. 서로 다른 원소가 서로 다른 상을 가지면 f는 단사(일대일), B의 모든 원소가 상이면 전사(위로의 함수), 둘 다 성립하면 전단사입니다. |A| = m, |B| = n이면 함수는 nᵐ개, 단사 함수는 n!/(n − m)!개(m ≤ n)이고, 포함·배제에 따라 전사 함수는 Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ개입니다. |𝒫(A)| = 2ᵐ, |A × B| = m·n입니다.
단사인가?
f(1) = f(3) = b → 단사가 아님
전사인가?
a, c 화살표를 받지 않음 → 전사가 아님
답
둘 다 아님
답
둘 다 아님
5.그래프 이론
답: L = 5
오일러, 해밀턴, 트리: 연결 그래프는 모든 정점의 차수가 짝수이면 오일러 회로(모든 간선을 한 번씩 지나 출발점으로 돌아옴)를 가지고, 차수가 홀수인 정점이 정확히 두 개이면 회로가 아닌 오일러 경로를 가집니다. 이 경로는 한 홀수 정점에서 다른 홀수 정점까지 이어집니다. 해밀턴 회로는 모든 정점을 한 번씩 방문하며, Kn에는 (n − 1)!/2개가 있습니다. 정점이 n개인 트리는 간선이 n − 1개이고, 간선이 m개인 연결 그래프는 m − n + 1개의 간선을 제거한 뒤에도 신장 트리를 유지합니다.
트리에 대한 악수 보조정리
L + 15 = 2(L + 6) − 2
L = 5
답
L = 5
지름길: 차수 d ≥ 3인 정점에 대해 L = 2 + Σ (d − 2).
6.그래프 이론
답: N = 3
차수: 정점의 차수는 그 정점에 닿는 간선의 수입니다. 모든 간선은 양 끝이 있으므로 차수의 합은 간선 수의 두 배입니다: Σ deg(v) = 2|E|(악수 보조정리). 따라서 차수가 홀수인 정점의 수는 짝수입니다. Kn은 간선이 n(n − 1)/2개이고, 정점이 n개인 k-정규그래프는 nk/2개이며, 정점이 n개인 트리는 간선이 n − 1개입니다.
인접 행렬
A: 0 1 1 0 0
B: 1 0 1 1 1
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0
공통 이웃
(M²)CC = 1·1 + 1·1 + 0·0 + 0·0 + 1·1 = 3
답
N = 3
7.정수론과 모듈러 연산
답: x = 4
역원과 합동식: a는 gcd(a, n) = 1일 때, 그리고 그때에만 n을 법으로 하는 역원을 가집니다. 확장 유클리드 알고리즘은 1 = s·n + t·a로 쓰고, 그러면 a⁻¹ ≡ t (mod n)입니다. gcd(a, n) = 1인 합동식 a·x ≡ b (mod n)의 해는 x ≡ a⁻¹·b입니다. 법이 서로소인 두 합동식 x ≡ r₁ (mod m₁)과 x ≡ r₂ (mod m₂)는 m₁·m₂를 법으로 해가 하나 있습니다(중국인의 나머지 정리). 오일러 φ(n)은 1부터 n까지의 수 중 n과 서로소인 수의 개수입니다: φ(n) = n·∏(1 − 1/p).
15의 역원
r = 17, t = 0
r = 15, q = 1, t = 1
r = 2, q = 7, t = −1
r = 1, q = 2, t = 8
15−1 ≡ 8 (mod 17)
풀기
x ≡ 8·9 = 72 ≡ 4 (mod 17)
검산: 15·4 = 60 ≡ 9 (mod 17)
답
x = 4
8.정수론과 모듈러 연산
답: 1898781 mod 89 = 18
모듈러 거듭제곱과 RSA: aᵏ mod n은 반복 제곱법으로 계산합니다. k를 이진수로 쓰고, 제곱하고, 단계마다 나머지를 취하고, 비트가 1인 거듭제곱들을 곱하세요. 페르마: a를 나누지 않는 소수 p에 대해 aᵖ⁻¹ ≡ 1 (mod p)이므로 지수를 p − 1을 법으로 줄일 수 있습니다. RSA: 소수 p와 q를 고르고, n = p·q, φ(n) = (p − 1)(q − 1)입니다. 공개 지수 e는 φ(n)과 서로소이고 개인 지수는 d = e⁻¹ mod φ(n)입니다. c = mᵉ mod n으로 암호화하고 m = cᵈ mod n으로 복호화합니다.