Discrete Structures & Modeling

1. Overview

이산 구조 및 모델링(Discrete Structures & Modeling, DSM)은 연속적이지 않은 객체들 사이의 관계를 수학적으로 모델링하고 분석하는 분야입니다.

컴퓨터의 데이터 처리 방식(Bit/Byte) 자체가 이산적이기에, 이 노드의 지식은 알고리즘 설계, 데이터베이스 스키마 정의, 네트워크 모델링의 필수 전제 조건이 됩니다. 학습자는 공리적 집합론의 기초부터 조합론적 최적화, 그래프 모델링을 통해 논리적 사고의 틀을 완성하며, 현실의 복잡한 비선형 문제를 결정 가능한 구조로 추상화하는 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

집합과 관계: 집합 연산, 관계의 성질(반사, 대칭, 추이) 및 동치 관계, 부분 순서 집합(Poset)
계수 및 조합: 비둘기집 원리, 순열과 조합, 포함-배제 원리, 점화식(Recurrence Relations)
그래프 이론: 경로 및 회로 탐색, 트리 구조, 평면 그래프 및 색칠 문제(Graph Coloring)
재귀와 점화식: 반복 관계의 이산적 모델링 및 폐형식(Closed-form) 해 도출

Out-of-Scope

연속적인 실수 범위의 해석학적 연산 (P1 Mathematics 일반 영역)
불(Boolean) 대수의 하드웨어적 회로 설계 관점 (P2 Computer Architecture 영역으로 위임)
복잡한 확률 통계 모델 (04. Probability 노드로 위임)

Boundaries

DSM vs. Algorithms: CS2023(DS)에 따르면 DSM은 '구조의 수학적 성질(Mathematical Property)'을 증명하고 정의하는 데 집중하며, 알고리즘(04)은 이를 이용해 '실행과정(Computational Process)'을 최적화하고 복잡도를 계산합니다.

3. Counterexample

단순히 공식(순열/조합 공식)을 외워 산술 문제를 푸는 것은 DSM 학습이 아닙니다. 왜 특정 데이터 구조(예: Social Graph 또는 Git의 DAG)를 표현할 때 인접 행렬보다 인접 리스트가 적합한지 **그래프 위상 구조의 성질(Sparsity)**을 기반으로 수학적으로 모델링할 수 있어야 합니다.

4. Prerequisites

컴퓨터 과학 및 공학 (Basic): 이산 데이터가 컴퓨터 내 비트 구조로 어떻게 디지털화되는지에 대한 기본 인지가 필요합니다. (ROOT)

5. Learning Map

Foundations: 집합론과 함수, 관계를 통해 수학적 객체를 엄밀하게 정의하는 법을 익힙니다. (NC ↔ OS 연계 기반)
Counting & Recurrence: 이산적 객체의 가짓수를 측정하고 재귀적 구조를 식으로 모델링하는 기법을 배웁니다.
Graph Modeling: 현실의 복잡한 연결성을 노드와 에지로 단순화하고 트리의 위상적 특징을 분석합니다.
Discrete Apps: 이산 구조 모델이 데이터베이스의 관계 대수나 네트워크 토폴로지 설계에 어떤 기반이 되는지 연구합니다.

6. Learning Topics

Basic

Core: 집합론과 함수 기초 (Set Theory & Functions)

Why to Learn: 모든 데이터 구조와 관계 대수의 가장 원자적인 표현 수단이기 때문입니다.
What to Learn:
- 교집합, 합집합, 멱집합(Power set), 카디널리티(Cardinality)의 정의
- 단사(Injection), 전사(Surjection), 전단사(Bijection) 함수의 차이
- 집합의 크기 비교와 무한 집합의 개념
How to Learn:
- 벤 다이어그램을 이용한 집합 연산 시각화 실습
- 특정 도메인(예: 사용자 목록)을 집합으로 정의하고 관계를 함수로 매핑하는 과제 수행
Implement: 집합 연산 라이브러리(Java Set, C++ STL)를 활용한 관계 모델링 코드

Why to Learn: 자원 할당, 비밀번호 보안 강도 계산, 알고리즘 케이스 분석 등 가짓수 측정의 정밀성이 요구되기 때문입니다.
What to Learn:
- 비둘기집 원리(Pigeonhole Principle)의 증명 및 응용
- 중복 순열과 중복 조합의 변별 및 포함-배제 원리
- 이항 정리와 파스칼의 삼각형
How to Learn:
- 현실의 분배 문제(예: N개의 요청을 M개의 서버에 할당)를 조합론적으로 식으로 도출
- 제약 조건이 있는 비밀번호 조합의 전체 공간 계산 실습
Implement: 재귀 또는 동적 계획법을 이용한 조합/순열 생성 프로그램

Practical

Core: 그래프 및 트리 모델링 (Graph & Tree Modeling)

Why to Learn: 현대 컴퓨팅 인프라(Network, DB, UI Tree)의 핵심 위상을 정의하는 모델링 도구이기 때문입니다.
What to Learn:
- 오일러 경로와 해밀턴 경로의 존재 조건 분석
- 트리와 일반 그래프의 차이점 및 위상적 성질(Acyclic, Connected)
- 평면 그래프(Planar Graph)와 그래프 색칠(Coloring)의 공학적 응용
How to Learn:
- 구글 맵의 경로 탐색 문제를 그래프 모델로 추상화하여 모델링
- 파일 시스템 구조를 트리 이론 기반으로 분석
Implement: 인접 행렬과 인접 리스트를 이용한 그래프 표현 및 위상 정렬 모델

Advanced

Core: 생성 함수와 점화식 분석 (Generating Functions & Advanced Recurrence)

Why to Learn: 복잡한 수열의 일반항을 도출하고 알고리즘의 비점근적 한계를 정밀하게 증명하기 위해서입니다.
What to Learn:
- 선형 동차 점화식의 해 구하기 (Closed-form)
- 생성 함수(Generating Functions)를 이용한 조합 문제의 대수적 풀이
- 대수 구조(Semiring)와 최단 경로 알고리즘의 관계
How to Learn:
- 피보나치 수열 등 주요 점화식의 특성 방정식을 통한 일반항 유도 연습
- 생성 함수를 이용해 복잡한 파티션 문제 해결 실습
Implement: 기호 연산(Symbolic Computation) 도구를 이용한 수열 분석 리포트

7. Terminology

Term (EN / ko, abbr)	1문장 정의	단계(기본/권장/실무/심화)	역할/맥락	관련 개념	유사/대비/함께 사용	오해 포인트	Evidence(Primary/Secondary/Industry)	Flags(core/misused/legacy)
Cardinality (집합 크기)	집합에 포함된 원소의 개수를 정량적으로 나타내는 척도입니다.	기본	기초 정의	Set Theory	Arity, Dimension	유한 집합에만 쓰인다고 오해	CS2023/Sets	core
Bijection (전단사 함수)	두 집합 간 일대일 응답이 완벽하게 이루어지는 함수 상태를 의미합니다.	기본	매핑 정의	Injection, Surjection	Invertibility	단순히 '일대일'로만 기억함	CS2023/Functions	core
DAG (Directed Acyclic Graph)	에지에 정의된 방향성이 있고 순환(Cycle)이 존재하지 않는 그래프 모델입니다.	실무	워크플로우 모델	Graph Theory	Tree, Cycle	모든 트리는 DAG이지만 모든 DAG은 트리가 아님	Industry Internals	core
Recurrence Relation (점화식)	수열의 각 항을 이전 항들의 관계식으로 정의하는 기법입니다.	권장	분석 모델	Induction	Closure-form	단순 반복문과 혼동	P1:CS2023/Recurrence	core

8. References

Primary References

[P1] CS2023 - Discrete Structures — Fundamental structures for computing.
[P5] SFIA - Technical Modeling — Competency in structural representation.

Secondary References

[MIT 6.042J] Mathematics for Computer Science — Core curriculum for CS theory.
[Rosen] Discrete Mathematics and Its Applications (Global Edition) — Standard textbook.

Industry References

[Google DeepMind] Graph Neural Networks Foundation — Real-world application of graph modeling.
[AWS] DynamoDB Relationship Modeling — Applying set/relation theory to NoSQL.

9. Final Checklist

Primary Checklist

주어진 이산 객체들 사이의 관계를 공리적 집합과 함수로 엄밀하게 정의할 수 있는가? (P1)
중복과 순서를 고려하여 특정 문제의 전체 경우의 수를 수학적 누락 없이 도출할 수 있는가? (P1)

Secondary Checklist

그래프의 성질(Degree, Path, Connectivity)을 이용해 네트워크의 연결 신뢰성을 판단할 수 있는가?
이산 구조가 실제 CS 분야(DB 릴레이션, 알고리즘)에서 어떤 논리적 기반이 되는지 설명 가능한가?

Industry Checklist

특정 공학적 요구사항(예: 복제 노드 할당)을 비둘기집 원리나 조합론으로 모델링하여 검증할 수 있는가?
그래프 색칠 문제를 스케줄링이나 리소스 할당 최적화에 적용할 줄 아는가? (SFIA)