알고리즘, 정수론, 그리고 행렬의 기초

Discrete Mathematics and Its Applications · Kenneth H. Rosen · Ch. 3

Intuition

문제를 해결하는 절차(알고리즘)를 정의하고, 그것이 얼마나 효율적인지(복잡도) 측정하며, 컴퓨터 연산의 핵심인 정수론과 데이터 구조의 표현 수단인 행렬을 이해한다.

One-liner

컴퓨터 과학의 핵심인 알고리즘 설계 및 분석 도구와 현대 암호학 및 데이터 처리를 지탱하는 정수론과 행렬의 기초 이론을 통합적으로 다룬다.

Prerequisites

• 기초 논리와 집합론: Ch. 1, Ch. 2 수준의 명제 논리, 집합의 표현 및 함수 개념.
• 수열과 합: 수열의 일반항 및 $\sum$ 표기법에 대한 이해 (Ch. 2).
• 기초 대수학: 다항식의 계산 및 로그 함수의 성질.

Goals

• 알고리즘의 기본 특성을 이해하고 의사코드로 표현할 수 있다.
• Big-O 표기법을 사용하여 함수의 증가 속도를 추정하고 알고리즘의 시간 복잡도를 분석할 수 있다.
• 유클리드 알고리즘, 중국인의 나머지 정리 등 정수론의 핵심 정리를 활용하여 계산 문제를 해결할 수 있다.
• 현대 공개키 암호 방식인 RSA의 수학적 원리를 설명할 수 있다.
• 행렬 산술 및 부울 행렬 연산을 수행할 수 있다.

Core Concepts

3.1 Algorithms (알고리즘)

Definition

Algorithm (알고리즘): 계산을 수행하거나 문제를 해결하기 위한 유한한 규칙 또는 지침의 집합이다. (p.168)

• 알고리즘의 특성:

  1. Input (입력): 지정된 집합에서 가져온 입력값이 있다.
  2. Output (출력): 입력에 대응하는 해결책인 출력값이 있다.
  3. Definiteness (명확성): 각 단계가 정확하게 정의되어야 한다.
  4. Correctness (정확성): 모든 입력에 대해 올바른 출력을 생성해야 한다.
  5. Finiteness (유한성): 유한한 단계 후에 종료되어야 한다.
  6. Effectiveness (유효성): 각 단계를 유한한 시간 내에 정확히 수행할 수 있어야 한다.
  7. Generality (일반성): 특정 입력만이 아닌 동일한 형태의 모든 문제에 적용 가능해야 한다.

• Greedy Algorithm (탐욕 알고리즘): 각 단계에서 전체적인 최적해를 고려하지 않고, 그 순간의 최선(locally optimal)을 선택하는 방식이다. (p.175)

• Halting Problem (정지 문제): 특정 프로그램과 입력이 주어졌을 때, 해당 프로그램이 결국 멈출지 아니면 무한히 실행될지를 판별하는 일반적인 알고리즘은 존재하지 않는다 (Alan Turing, 1936). (p.177)

3.2 The Growth of Functions (함수의 증가)

Definition

Big-O Notation: $f(x)$가 $O(g(x))$라는 것은 상수 $C$와 $k$가 존재하여 $x > k$일 때 $|f(x)| \le C|g(x)|$가 성립함을 의미한다. 이때 $C, k$를 증인(witnesses)이라 한다. (p.180)

• 주요 점근적 표기법:
  • Big-Omega ($\Omega$): 함수의 하한(lower bound)을 나타낸다.
  • Big-Theta ($\Theta$): 함수의 상한과 하한이 동일한 차수임을 나타낸다 ($f$ is of order $g$).

3.3 Complexity of Algorithms (알고리즘 복잡도)

• Time Complexity (시간 복잡도): 입력 크기에 따라 알고리즘이 수행하는 연산 횟수를 분석한다.
• Worst-case Complexity (최악의 경우 복잡도): 주어진 크기의 입력 중 가장 많은 연산을 필요로 하는 경우를 분석하며, 알고리즘의 성능 보증에 필수적이다. (p.194)
• Tractable vs Intractable: 다항 시간 알고리즘($O(n^b)$)이 존재하면 해결 가능한(tractable) 문제, 그렇지 않으면 다루기 힘든(intractable) 문제로 분류한다. (p.197)

3.4 The Integers and Division (정수와 나눗셈)

Definition

Divisibility: 정수 $a \ne 0$에 대해 $b = ac$를 만족하는 정수 $c$가 존재하면 $a$가 $b$를 나눈다($a|b$)고 한다. (p.201)

• Modular Arithmetic: $a$를 $m$으로 나눈 나머지가 $b$를 $m$으로 나눈 나머지와 같을 때 $a \equiv b \pmod{m}$이라 한다. (p.203)

3.5 Primes and Greatest Common Divisors (소수와 최대공약수)

• Fundamental Theorem of Arithmetic (산술의 기본 정리): 1보다 큰 모든 양의 정수는 소수들의 곱으로 유일하게 표현될 수 있다. (p.211)
• Greatest Common Divisor (GCD): 두 정수를 동시에 나누는 가장 큰 정수. $gcd(a, b) = 1$이면 두 수는 서로소(relatively prime)이다. (p.216)

3.6 Integers and Algorithms (정수 알고리즘)

• Base Conversion: 임의의 양의 정수 $b > 1$을 기수로 하여 정수를 표현할 수 있다. (p.219)
• Euclidean Algorithm: 나눗셈의 원리를 반복하여 두 수의 최대공약수를 효율적으로 찾는 알고리즘이다. (p.228)

3.7 Applications of Number Theory (정수론의 응용)

• Chinese Remainder Theorem (중국인의 나머지 정리): 서로소인 법(moduli)들에 대한 일차 합동식 연립방정식은 유일한 해를 가짐을 보장한다. (p.236)
• RSA Cryptosystem: 매우 큰 두 소수의 곱을 인수분해하는 것이 어렵다는 점을 이용한 공개키 암호 알고리즘이다. (p.241)

3.8 Matrices (행렬)

• Matrix Multiplication: $m \times k$ 행렬 $A$와 $k \times n$ 행렬 $B$의 곱 $AB$는 $m \times n$ 행렬이 된다. (p.248)
• Zero-One Matrix: 모든 원소가 0 또는 1인 행렬로, 논리합($\vee$, Join)과 논리곱($\wedge$, Meet), 부울 곱($\odot$) 연산을 수행한다. (p.252)

Key Theorems & Formulas

Theorem (The Division Algorithm)

조건: 정수 $a$와 양의 정수 $d$.

결론: $a = dq + r$을 만족하는 유일한 정수 $q$(몫)와 $r$(나머지, $0 \le r < d$)이 존재한다. (p.202)

Theorem (Fermat's Little Theorem)

조건: 소수 $p$와 $p$로 나누어지지 않는 정수 $a$.

결론: $a^{p-1} \equiv 1 \pmod{p}$ 이며, 모든 정수 $a$에 대해 $a^p \equiv a \pmod{p}$이다. (p.239)

Theorem (Euclidean Algorithm Lemma)

조건: $a = bq + r$ ($a, b, q, r$은 정수).

결론: $gcd(a, b) = gcd(b, r)$. (p.228)

Intuitions

• Big-O의 직관: 함수의 세세한 변동이나 상수는 무시하고, 입력이 무한히 커질 때 "가장 지배적인 증가 요인"이 무엇인지만 보겠다는 선언이다.
• Binary Search의 직관: 정렬된 리스트에서 매 단계마다 탐색 범위를 절반씩 날려버리므로, 선형 탐색($O(n)$)보다 압도적으로 빠른 로그 시간($O(\log n)$) 복잡도를 갖는다.
• Modular Arithmetic의 직관: 숫자를 직선이 아닌 시계와 같은 '원형 구조' 위에서 파악하는 것이다. 현대 암호학에서 숫자의 범위를 제한하면서도 복잡한 연산을 수행하는 핵심 도구가 된다.

Worked Examples

Example 1: Finding Witnesses for Big-O

문제: $f(x) = x^2 + 2x + 1$이 $O(x^2)$임을 증명하라.

핵심 단계:

1. $x > 1$일 때, $x < x^2$ 및 $1 < x^2$임을 이용한다.
2. $x^2 + 2x + 1 \le x^2 + 2x^2 + x^2 = 4x^2$가 성립한다.
3. 따라서 $C = 4, k = 1$을 증인으로 선택할 수 있다.

요점: 적절한 상한을 설정하기 위해 부등식을 활용하여 $C$와 $k$를 찾아내는 과정이 핵심이다.

Example 2: Euclidean Algorithm

문제: $gcd(414, 662)$를 구하라.

핵심 단계:

1. $662 = 414 \cdot 1 + 248$
2. $414 = 248 \cdot 1 + 166$
3. $248 = 166 \cdot 1 + 82$
4. $166 = 82 \cdot 2 + 2$
5. $82 = 2 \cdot 41 + 0$

요점: 나머지가 0이 되기 직전의 마지막 0이 아닌 나머지인 2가 최대공약수이다.

Common Pitfalls

Pitfall

나눗셈 알고리즘의 명칭: "Division Algorithm"은 이름과 달리 현대적 의미의 알고리즘(절차)이라기보다 정수의 존재성에 관한 '정리'에 가깝다. 실제 계산 절차는 별도로 구현해야 한다.

Pitfall

Big-O와 등호: $f(x) = O(g(x))$에서 등호는 수학적 동일함이 아니라 "집합에 속한다" 또는 "부등식 관계가 있다"는 의미의 관습적 표기이다. $O(g(x)) = f(x)$와 같이 거꾸로 쓸 수 없다.

Connections

• 선행 개념: Ch. 1 기초 논리와 증명 기법 - 알고리즘의 정확성 증명 및 정수론 정리에 필수적이다.
• 후속 개념: Ch. 4 수학적 귀납법 - 알고리즘의 정당성을 증명하는 강력한 도구로 연결된다. Ch. 7 고급 계수 기법 - 분할 정복 점화식과 마스터 정리로 확장된다.
• 응용 분야: 암호학 (RSA), 알고리즘 분석 (알고리즘론), 데이터베이스 (해싱 함수).

Critical Notes

교재가 강조하는 것

• 알고리즘을 단순한 코딩이 아닌 수학적 구조(입력, 출력, 명확성 등)로 엄밀히 정의하는 것.
• 정수론이 현대 암호학(RSA)에서 어떻게 실용적으로 사용되는지 보여주는 연결성.

실제로 중요한 것

• 시간 복잡도 분석: 단순 구현보다 효율성 판단 능력이 실무와 시험에서 훨씬 중요하다.
• 유클리드 알고리즘: 모든 정수론 문제의 계산적 토대가 된다.

교재가 생략하거나 얼버무리는 것

• 정지 문제(Halting Problem)의 증명은 다소 직관적으로 서술되어 있으며, 엄밀한 이해를 위해서는 튜링 머신(Turing Machine)에 대한 보충 학습이 필요하다.
• 알고리즘 복잡도의 평균 케이스(Average-case) 분석은 확률론적 배경이 필요하여 간단한 사례만 다루고 넘어간다.

Open Questions

이해하지 못한 것

• NP-완전(NP-complete) 문제들의 구체적인 증명 과정. (교재에서는 개념만 소개하고 Ch. 12를 기약함)

더 알고 싶은 것

• RSA 암호를 깨기 위한 양자 알고리즘(Shor's algorithm)의 수학적 원리.
• Big-O 외에 알고리즘의 공간 복잡도(Space Complexity)를 측정하는 구체적인 방법론.