이산수학은 연속적인 값을 다루는 미적분과 달리 서로 분리된 개체와 구조를 다루는 수학이다.
프로그래밍에서 사용하는 자료구조와 알고리즘 대부분이 이산적인 구조를 가지고 있기 때문에 개발자에게 상당히 중요한 수학이다.
예를 들어
논리 -> 조건문
집합 -> 데이터 그룹
함수 -> 입력과 출력
관계 -> 객체 간 연결
그래프 -> 경로 탐색
트리 -> 계층 구조
조합 -> 경우의 수
점화식 -> 재귀 알고리즘
수학적 귀납법 -> 알고리즘 증명
등으로 연결된다.
이산수학을 한마디로 표현하면
“컴퓨터가 다루는 구조를 수학적으로 표현하고 분석하는 방법”
이라고 볼 수 있다.
명제
명제(Proposition)는 참 또는 거짓을 명확하게 판단할 수 있는 문장이다.
예를 들어
1 + 1 = 2
는 참인 명제다.
반면
오늘 날씨가 좋다.
처럼 기준이 명확하지 않은 문장은 일반적인 의미의 명제로 다루기 어렵다.
명제는 보통
P
Q
R
등의 기호로 표현한다.
논리 연산
명제 여러 개를 논리 연산으로 결합할 수 있다.
대표적인 것은
AND -> ∧
OR -> ∨
NOT -> ¬
이다.
예를 들어
P = 플레이어가 살아있다
Q = 공격 범위 안에 있다
라면
P ∧ Q
는
플레이어가 살아있다 AND 공격 범위 안에 있다
라는 뜻이다.
프로그래밍에서는
if (isAlive && distance <= attackRange)
{
Attack();
}
와 같은 형태로 나타난다.
논리적 동치
두 논리식이 모든 경우에 같은 결과를 낸다면 논리적으로 동치라고 한다.
대표적인 것이 드모르간 법칙이다.
¬(P ∧ Q) = ¬P ∨ ¬Q
¬(P ∨ Q) = ¬P ∧ ¬Q
프로그래밍에서도 조건식을 변형할 때 자주 등장한다.
!(A && B)
는
!A || !B
와 같은 논리적 의미를 가진다.
명제와 조건문
논리에서
P -> Q
는 “P이면 Q이다”라는 의미다.
이를 함의(Implication)라고 한다.
중요한 것은
P -> Q
와
Q -> P
는 서로 다른 명제라는 것이다.
예를 들어
플레이어가 죽었다 -> 체력이 0 이하이다
가 참이라고 해서
체력이 0 이하이다 -> 플레이어가 죽었다
가 항상 참이라고 할 수 있는 것은 게임 시스템의 정의에 따라 다르다.
필요조건과 충분조건
P -> Q에서
P -> Q
라면
P는 Q의 충분조건
Q는 P의 필요조건
이다.
예를 들어
HP <= 0 -> Death State
라면 HP <= 0은 Death State의 충분조건이 될 수 있다.
이런 조건 관계를 정확하게 이해하면 복잡한 게임 로직을 설계할 때 도움이 된다.
술어와 한정자
변수에 대한 조건을 표현할 때 술어(Predicate)를 사용한다.
예를 들어
P(x) = x는 짝수이다
라고 할 수 있다.
여기에 한정자를 붙일 수 있다.
∀ -> 모든
∃ -> 어떤 것이 존재
예를 들어
∀x P(x)
는 모든 x에 대해 P(x)가 참이라는 의미다.
∃x P(x)
는 P(x)를 만족하는 x가 적어도 하나 존재한다는 의미다.
집합
집합(Set)은 특정한 대상들을 하나의 그룹으로 묶은 것이다.
A = {1, 2, 3}
집합의 원소는
1 ∈ A
처럼 표현한다.
반대로
5 ∉ A
는 5가 A에 포함되지 않는다는 뜻이다.
부분집합
집합 A의 모든 원소가 집합 B에도 포함된다면 A는 B의 부분집합이다.
A ⊆ B
예를 들어
A = {1,2}
B = {1,2,3}
이면
A ⊆ B
이다.
합집합과 교집합
두 집합을 결합할 수 있다.
합집합은
A ∪ B
이고 두 집합에 속하는 모든 원소를 포함한다.
교집합은
A ∩ B
이고 두 집합에 동시에 속하는 원소만 포함한다.
예를 들어
A = {1,2,3}
B = {3,4,5}
이면
A ∪ B = {1,2,3,4,5}
A ∩ B = {3}
이다.
게임에서는 태그나 카테고리 등을 집합으로 생각할 수 있다.
Player
-> Character / Mage / FireElement
같은 분류를 집합의 포함 관계로 볼 수 있다.
차집합
A에서 B에 포함된 원소를 제거한 집합이다.
A - B
또는
A \ B
로 표현한다.
예를 들어
A = {1,2,3}
B = {2,3,4}
라면
A \ B = {1}
이다.
집합의 크기
집합에 포함된 원소의 개수를 기수(Cardinality)라고 한다.
|A|
로 표현한다.
예를 들어
A = {1,2,3,4}
라면
|A| = 4
이다.
유한한 집합에서 합집합의 크기는
|A ∪ B| = |A| + |B| - |A ∩ B|
이다.
순서쌍
두 값을 순서대로 묶은 것을 순서쌍이라고 한다.
(a,b)
순서가 중요하다.
(a,b) != (b,a)
일반적으로 성립한다.
좌표 역시 순서쌍이다.
(x,y)
게임의 위치나 상태를 표현할 때 자연스럽게 사용된다.
데카르트 곱
두 집합에서 원소를 하나씩 선택해서 만들 수 있는 모든 순서쌍의 집합이다.
A × B
예를 들어
A = {1,2}
B = {a,b}
라면
A × B =
{(1,a), (1,b), (2,a), (2,b)}
이다.
집합의 크기는
|A × B| = |A||B|
이다.
관계
관계(Relation)는 두 대상 사이의 연결을 표현한다.
예를 들어
Player -> owns -> Item
같은 관계를 생각할 수 있다.
수학적으로는 순서쌍들의 집합으로 표현할 수 있다.
R ⊆ A × B
관계의 성질
관계에는 여러 가지 성질이 있다.
대표적으로
반사성
대칭성
반대칭성
추이성
이 있다.
반사성
모든 원소가 자기 자신과 관계를 가지면 반사적이다.
aRa
대칭성
aRb -> bRa
가 항상 성립하면 대칭적이다.
추이성
aRb AND bRc -> aRc
가 성립하면 추이적이다.
이런 성질을 이용하면 복잡한 관계 구조를 분류할 수 있다.
동치관계
동치관계는
반사성
대칭성
추이성
을 모두 만족하는 관계다.
동치관계는 서로 비슷한 성질을 가진 대상을 같은 그룹으로 묶을 수 있게 한다.
전체 집합
-> 동치관계
-> 여러 개의 동치류
함수
함수는 하나의 입력에 정확히 하나의 출력이 대응되는 관계다.
f : A -> B
여기서
A -> 정의역
B -> 공역
이다.
프로그래밍의 함수와 매우 비슷한 형태로 생각할 수 있다.
Input -> Function -> Output
게임에서는
Level -> Required XP
Distance -> Damage
Time -> Position
같은 관계를 함수로 표현할 수 있다.
전사, 단사, 전단사
함수의 대응 관계를 더 세밀하게 분류할 수 있다.
단사 함수
서로 다른 입력이 같은 출력으로 가지 않는 함수다.
x1 != x2 -> f(x1) != f(x2)
전사 함수
공역의 모든 값이 적어도 하나의 입력과 연결되는 함수다.
전단사 함수
단사와 전사를 모두 만족한다.
전단사 함수는 역함수를 만들 수 있다.
f : A -> B
f⁻¹ : B -> A
경우의 수
경우의 수는 가능한 결과가 몇 개인지 계산하는 방법이다.
가장 기본적인 원칙은 곱셈 법칙이다.
어떤 작업을
A -> m가지
B -> n가지
방법으로 할 수 있다면 전체 경우의 수는
m * n
이다.
예를 들어 캐릭터의
무기 5종
방어구 4종
을 조합할 수 있다면
5 * 4 = 20
가지 조합이 가능하다.
순열
순서를 고려해서 선택하는 경우다.
n개 중 r개를 순서 있게 선택하면
P(n,r) = n! / (n-r)!
이다.
예를 들어 5명 중 3명을 순서대로 배치한다면
P(5,3) = 5 * 4 * 3 = 60
이다.
조합
순서를 고려하지 않고 선택하는 경우다.
C(n,r) = n! / (r!(n-r)!)
이다.
5명 중 3명을 선택한다면
C(5,3) = 10
이다.
게임에서는 파티 구성, 아이템 조합, 카드 선택 등의 경우의 수를 계산할 때 사용할 수 있다.
이항정리
두 항의 거듭제곱을 전개하는 공식이다.
(a+b)^n
을 전개하면
(a+b)^n = Σ C(n,k)a^(n-k)b^k
가 된다.
이항계수는 조합과 연결된다.
C(n,k)
는 n개 중 k개를 선택하는 경우의 수다.
이항정리는 이항분포와도 직접 연결된다.
재귀
재귀(Recursion)는 함수가 자기 자신을 호출하는 구조다.
Function
-> Function
-> Function
-> ...
재귀 알고리즘은 이산수학의 점화식과 밀접하게 연결된다.
대표적으로 팩토리얼은
n! = n * (n-1)!
이고
0! = 1
이라는 기저 조건을 가진다.
코드로 표현하면
int Factorial(int n)
{
if (n == 0)
return 1;
return n * Factorial(n - 1);
}
이다.
점화식
점화식(Recurrence Relation)은 이전 항을 이용해서 다음 항을 정의한다.
대표적인 예가 피보나치 수열이다.
F(n) = F(n-1) + F(n-2)
기저 조건은
F(0) = 0
F(1) = 1
이다.
알고리즘의 시간 복잡도를 분석할 때도 점화식이 사용된다.
예를 들어 병합 정렬은 대략
T(n) = 2T(n/2) + O(n)
형태로 표현할 수 있다.
그래프
그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 구조다.
Vertex <-> Edge <-> Vertex
예를 들어
A -- B
| |
C -- D
같은 구조다.
게임 개발에서는 그래프가 매우 중요하다.
맵
-> 지역
-> 연결 관계
-> 그래프
로 생각할 수 있기 때문이다.
방향 그래프
간선에 방향이 존재하는 그래프다.
A -> B
B -> C
와 같은 형태다.
A에서 B로 이동할 수 있어도 B에서 A로 이동할 수 있다는 보장은 없다.
게임의 일방통행 길이나 스킬 의존 관계 등을 표현할 수 있다.
가중치 그래프
간선마다 비용이나 거리가 붙어 있는 그래프다.
A --5-- B
B --2-- C
A --9-- C
여기서 숫자는 이동 비용이라고 생각할 수 있다.
게임의 경로 탐색에서는
Node -> Edge Cost -> Path
가 중요하다.
A*와 Dijkstra 알고리즘도 이런 그래프 구조를 기반으로 한다.
경로
그래프에서 정점을 따라 이동하는 순서를 경로라고 한다.
A -> B -> C -> D
경로의 비용이 존재한다면 각 간선의 비용을 합산할 수 있다.
Path Cost = Cost(A,B) + Cost(B,C) + Cost(C,D)
최단 경로 문제는 게임 AI에서 매우 중요한 문제다.
Map
-> Graph
-> Path Search
-> Shortest / Optimal Path
트리
트리(Tree)는 사이클이 없는 연결 그래프다.
일반적으로
Root
-> Child
-> Child
-> ...
형태의 계층 구조를 가진다.
게임에서 매우 많이 사용한다.
Scene
-> GameObject
-> Component
Skill
-> Skill Tree
AI
-> Behavior Tree
UI
-> Panel
-> Button
트리의 용어
트리에서 자주 사용하는 용어는
Root -> 최상위 노드
Parent -> 부모
Child -> 자식
Leaf -> 자식이 없는 노드
Depth -> 루트에서 떨어진 정도
Height -> 트리의 최대 깊이
이다.
이진 트리
각 노드가 최대 두 개의 자식을 가지는 트리다.
A
/ \
B C
/ \
D E
이진 탐색 트리(Binary Search Tree)에서는 정렬 규칙을 추가해서 탐색을 효율적으로 할 수 있다.
힙
힙(Heap)은 우선순위를 효율적으로 관리하기 위한 트리 기반 자료구조다.
대표적으로 최소 힙에서는
Parent <= Child
관계가 유지된다.
우선순위 큐를 구현하는 데 사용한다.
A*나 Dijkstra에서 다음에 처리할 노드를 선택할 때 우선순위 큐가 사용되며, 내부적으로 힙을 사용하는 경우가 많다.
그래프 탐색
그래프를 탐색하는 대표적인 방법은
DFS
BFS
다.
DFS
깊이 우선 탐색이다.
한 방향으로 최대한 깊게 들어간다.
Start
-> 깊게 탐색
-> 더 이상 갈 수 없음
-> Backtracking
-> 다음 경로
재귀나 Stack으로 구현할 수 있다.
BFS
너비 우선 탐색이다.
가까운 노드부터 순서대로 탐색한다.
Start
-> 거리 1
-> 거리 2
-> 거리 3
-> ...
Queue를 사용한다.
가중치가 없는 그래프에서 최단 간선 수 경로를 찾는 데 사용할 수 있다.
그래프와 게임 AI
게임 AI에서 그래프는 매우 중요한 모델이다.
게임 월드
-> Node
-> Edge
-> Graph
-> Pathfinding
예를 들어
NavMesh
-> 이동 가능한 영역
-> 연결 관계
-> 그래프
-> 경로 탐색
처럼 생각할 수 있다.
A* 알고리즘은
현재 비용 g(n)
+
목표까지 예상 비용 h(n)
=
f(n)
을 이용한다.
f(n) = g(n) + h(n)
이산수학에서 배우는 그래프와 조합 개념이 실제 게임 AI로 연결되는 대표적인 사례다.
수학적 귀납법
수학적 귀납법은 어떤 명제가 모든 자연수에 대해 참임을 증명하는 방법이다.
기본 구조는 두 단계다.
기초 단계
-> n = 1에서 참인지 확인
귀납 단계
-> n = k에서 참이라고 가정
-> n = k+1에서도 참임을 증명
그러면 모든 자연수 n에 대해 명제가 참임을 증명할 수 있다.
알고리즘과 귀납법
귀납법은 알고리즘이 올바르게 동작한다는 것을 증명할 때 사용할 수 있다.
특히
재귀 알고리즘
-> 기저 조건
-> 재귀 단계
를 검증할 때 자연스럽게 연결된다.
예를 들어 팩토리얼 함수가
Factorial(n) = n * Factorial(n-1)
을 정확히 계산한다는 것을 귀납적으로 증명할 수 있다.
불변식
알고리즘이 실행되는 동안 항상 유지되어야 하는 조건을 불변식(Invariant)이라고 한다.
예를 들어 정렬 알고리즘에서
이미 처리한 영역은 항상 정렬되어 있다.
라는 조건을 유지할 수 있다.
초기 상태
-> 불변식 성립
-> 연산
-> 불변식 유지
-> 연산
-> ...
-> 종료
불변식은 알고리즘의 정확성을 증명하는 데 매우 유용하다.
그래프 색칠
그래프의 인접한 정점들이 서로 다른 색을 갖도록 색을 배정하는 문제다.
A -- B
| |
C -- D
같은 구조에 색을 배정할 수 있다.
그래프 색칠은 스케줄링, 자원 배분, 충돌 회피 등의 문제와 연결된다.
부울 대수
부울 대수(Boolean Algebra)는 참과 거짓을 대상으로 하는 대수다.
기본값은
0 -> False
1 -> True
이다.
대표적인 연산은
AND
OR
NOT
이다.
프로그래밍의 조건식뿐만 아니라 CPU의 논리 회로와 비트 연산에도 연결된다.
논리
-> Boolean Algebra
-> Logic Gate
-> Digital Circuit
-> Computer
비트와 이산수학
컴퓨터는 기본적으로 비트 단위의 데이터를 처리한다.
0
1
비트 여러 개를 조합하면 더 많은 상태를 표현할 수 있다.
n개의 비트가 있다면 가능한 상태의 수는
2ⁿ
이다.
예를 들어
8 bit -> 2⁸ = 256가지
이다.
게임에서 Layer Mask나 Flag를 비트 단위로 관리하는 것도 이런 원리를 이용한다.
[Flags]
enum UnitType
{
Player = 1 << 0,
Enemy = 1 << 1,
NPC = 1 << 2
}
복잡도와 이산수학
알고리즘의 입력 크기가 증가할 때 필요한 계산량을 분석하는 것도 이산수학과 밀접하다.
대표적인 표기법이 Big-O다.
O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(2ⁿ)
일반적으로 입력 크기가 커질수록 계산량이 얼마나 증가하는지를 나타낸다.
예를 들어
O(n)
은 입력 크기에 비례해서 증가하고,
O(n²)
은 입력 크기의 제곱에 비례해서 증가한다.
게임에서는 매 프레임 실행되는 코드라면 이런 차이가 특히 중요하다.
이산수학과 자료구조
자료구조 대부분은 이산적인 수학 구조로 설명할 수 있다.
Array -> 순차적인 데이터
Linked List -> 연결 관계
Stack -> LIFO
Queue -> FIFO
Tree -> 계층 구조
Heap -> 우선순위 구조
Graph -> 연결 구조
Hash Table -> 매핑 구조
따라서 자료구조를 단순한 코드 구현으로만 이해하기보다 수학적인 구조로 보면 각 자료구조의 특성을 이해하기 쉬워진다.
이산수학과 알고리즘
알고리즘도 이산수학과 직접 연결된다.
논리
-> 조건 판단
집합
-> 데이터 분류
조합
-> 경우의 수
그래프
-> 탐색 / 경로
트리
-> 계층 구조
점화식
-> 재귀 알고리즘
귀납법
-> 정확성 증명
Big-O
-> 복잡도 분석
결국 알고리즘은 문제를 이산적인 구조로 모델링한 뒤 그 구조를 효율적으로 처리하는 과정이라고 볼 수 있다.
핵심 정리
이산수학에서 개발자가 우선적으로 이해해야 할 내용은 다음과 같다.
논리
-> 명제 / AND / OR / NOT / 함의
집합
-> 부분집합 / 합집합 / 교집합 / 차집합
함수
-> 정의역 / 공역 / 단사 / 전사 / 전단사
관계
-> 반사성 / 대칭성 / 추이성 / 동치관계
조합
-> 순열 / 조합 / 경우의 수
재귀
-> 재귀 함수 / 점화식
그래프
-> 정점 / 간선 / 방향 / 가중치 / 경로
트리
-> Root / Parent / Child / Leaf / Depth
탐색
-> DFS / BFS / 최단 경로
논리회로
-> Boolean Algebra / Bit
증명
-> 귀납법 / 불변식
복잡도
-> Big-O
이산수학의 핵심은 공식을 많이 외우는 것이 아니다.
문제를 어떤 구조로 표현할 것인가가 핵심이다.
게임 개발을 예로 들면 다음과 같이 연결된다.
게임 상태
-> 논리식
-> 조건 판단
게임 월드
-> 그래프
-> 탐색
-> 경로
게임 오브젝트
-> 트리
-> 계층 구조
아이템 / 캐릭터 조합
-> 경우의 수
-> 조합 / 순열
재귀 시스템
-> 점화식
-> 복잡도 분석
컴퓨터 데이터
-> 비트
-> Boolean Algebra
-> 논리 회로
결국 이산수학은 컴퓨터가 다루는 이산적인 구조를 논리적으로 모델링하고, 그 구조를 분석하는 수학이다.
선형대수학이 공간과 변환을 이해하기 위한 수학이라면, 미적분이 변화와 누적을 이해하기 위한 수학이고, 확률과 통계가 불확실성과 데이터를 다루기 위한 수학이라면, 이산수학은 논리, 구조, 관계, 조합, 알고리즘을 이해하기 위한 수학에 가깝다.
게임 개발에서는 특히 자료구조와 알고리즘을 제대로 이해하기 위한 기반으로 볼 수 있다.