Functions & Mappings

1. Overview

함수와 사상(Functions & Mappings, FAM)은 "입력값 하나에 출력값 하나가 물리적으로 고정되어 튀어나오는" 가장 예측 가능하고 안전한 데이터 변환 파이프라인의 수학적 코어입니다.

학습자는 정의역(Domain)의 데이터가 공역(Codomain)의 데이터로 쏘아지는 **매핑(Mapping)**의 수리적 역학을 뜯어보고, 이것이 왜 프로그래밍의 기본 단위인 '함수(Function)'로 번역되는지 통달합니다. 나아가 **단사(Injective), 전사(Surjective), 전단사(Bijective)**라는 함수의 3대 물리적 제약 조건을 통해, 해시 함수(Hash Function)의 충돌(Collision)이나 데이터 압축/복원(Inverse Function)의 수리적 가능성을 증명하는 아키텍처적 시야를 확보합니다.

2. Scope & Boundaries

In-Scope

• 함수의 수리적 해부 (Function Physics): 정의역(Domain), 공역(Codomain), 치역(Range), 상(Image)과 역상(Pre-image).
• 매핑의 3대 속성 (Mapping Properties): 단사 함수(One-to-One), 전사 함수(Onto), 전단사 함수(Bijection)의 원소 크기 비교($|A| \le |B|$, $|A| \ge |B|$).
• 함수의 합성과 역함수 (Composition & Inverse): $f \circ g$ 연산의 체인 룰(Chain Rule), 역함수($f^{-1}$)가 존재하기 위한 전단사 물리 조건.
• 특수 함수 역학 (Special Functions): 바닥/천장 함수(Floor/Ceiling), 팩토리얼(Factorial), 모듈로(Modulo) 연산의 메모리 해싱 활용.

Out-of-Scope

• 미적분과 연속 함수 연속성: $f(x)$가 극한값(Limit)을 가질 때 연속인지 아닌지 따지는 해석학 $\rightarrow$ 01-01-02. Calculus & Continuous Math (이 커리큘럼 외) 영역.
• 함수형 프로그래밍 언어의 모나드(Monad) 설계: Haskell 등에서 상태(State)를 감싸는 고수준의 프로그래밍 패턴 $\rightarrow$ 05-01. Language Theory 영역.

Boundaries

• FAM vs. Set Theory (01-01-01): 집합론(01-01-01)이 "데이터를 가두는 그릇"이라면, FAM은 "A 그릇의 데이터를 B 그릇의 데이터로 변환시키는 파이프라인의 수리적 밸브"입니다.

3. Counterexample

• 역함수 맹신 (Inverse Function Fallacy): 비밀번호를 암호화(MD5, SHA-256)한 뒤, "역함수(Inverse)를 써서 원래 비밀번호로 복호화할 수 있겠지"라고 믿는 무지. 해시 함수는 기본적으로 여러 개의 다른 입력값이 하나의 출력값으로 겹칠 수 있는 '비단사(Non-injective)' 물리 속성을 가지므로, 수학적으로 완벽한 역함수가 존재하지 않습니다. 전단사(Bijection) 조건이 깨진 함수에서 역함수를 찾으려는 시도는 엔트로피 역전과 같습니다.
• 모듈로 난수 폭발 (Modulo Bias Fallacy): 게임에서 1부터 10까지의 랜덤 확률을 얻고자 난수 생성기에 % 10 (모듈로) 연산을 무심코 때려 박는 행위. 시스템 난수의 최대치(공역)가 10으로 깔끔하게 나누어떨어지지 않는 전사(Surjective) 매핑의 불균형 때문에, 특정 번호(예: 1~5)가 나올 확률이 미세하게 더 높아지는 통계적 붕괴가 발생합니다.

4. Prerequisites

• 집합론과 관계 (Basic): 함수 자체가 '모든 입력 $x$가 단 하나의 출력 $y$와 짝지어지는 특수한 관계(Relation)'이기 때문에, 집합의 개념을 반드시 먼저 알아야 합니다. (01-01-01 STR)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 함수의 수리적 해부학 (Function Anatomy)

• Why to Learn: 어떤 함수 코드를 짜든, 들어올 수 있는 값(정의역)과 나갈 수 있는 값(공역)의 메모리 범위를 컴파일러에게 정확히 알려주어 런타임 에러를 막기 위해서입니다.
• What to Learn:
  • Concepts: 정의역(Domain, $X$), 공역(Codomain, $Y$), 치역(Range, $f(X)$).
  • Skills: 상(Image), 부분 함수(Partial Function) vs 전역 함수(Total Function).
  • Tools: 타입 힌팅(Type Hinting in Python, TypeScript).
  • Trade-offs: 입력값이 주어지지 않았을 때 에러(Exception)를 뱉는 엄격한 수학적 맵핑 vs null이나 undefined를 치역에 포함시켜 앱이 뻗는 걸 막아주는 유연한 맵핑 방어.
• How to Learn:
  • 1단계: '모든 사람($X$)은 단 한 명의 생모($Y$)를 갖는다'는 명제가 어떻게 완벽한 함수의 수리적 조건을 만족시키는지, 그리고 왜 '형제'는 함수가 안 되는지 뜯어봅니다.
  • 2단계: C++나 Java에서 함수의 반환 타입(Return Type)을 선언하는 것이, 치역(Range)이 공역(Codomain)을 벗어나지 못하도록 컴파일 타임에 멱살을 잡는 물리적 제약임을 확인합니다.
• Implement: 입력값(Domain)을 검증하여 치역에 맞지 않는 악성 데이터(예: 음수 나이)가 들어왔을 때, 함수의 수리적 맵핑 규칙 위반으로 차단하는 방어적 래퍼(Wrapper) 함수 작성.

Recommended

Core Topic 02: 단사, 전사, 전단사 물리 조건 (Injective & Surjective)

• Why to Learn: 두 개의 다른 파일이 같은 해시값을 가져서(충돌) 데이터가 덮어씌워지는 치명적 버그를 수리적으로 예측하고 회피하기 위함입니다.
• What to Learn:
  • Concepts: 단사 함수(Injective/One-to-One), 전사 함수(Surjective/Onto), 전단사 함수(Bijective).
  • Skills: 비둘기집 원리(Pigeonhole Principle), 해시 충돌(Hash Collision), 가역성(Invertibility).
  • Tools: Cryptographic Hash Functions (SHA-256).
  • Trade-offs: 정의역 크기를 무제한으로 열어두고 공역을 256비트로 좁혀서 검색 속도를 미친 듯이 올리는 해싱(전사, 단사 아님) vs 데이터의 1비트도 잃어버리지 않고 완벽히 복원하는 무손실 압축 알고리즘(전단사 요구).
• How to Learn:
  • 1단계: "입력이 다르면 출력이 무조건 다르다($a \neq b \implies f(a) \neq f(b)$)"는 단사 함수의 법칙이, DB의 기본 키(Primary Key)가 갖춰야 할 필수 물리 조건임을 증명합니다.
  • 2단계: 10마리의 비둘기(정의역)를 9개의 방(공역)에 넣는 함수는 죽었다 깨어나도 단사 함수가 될 수 없다는 비둘기집 원리를 통해, 해시 충돌의 필연적 발생 물리를 계산합니다.
• Implement: 1,000개의 무작위 문자열을 크기가 100인 배열(공역)에 매핑하는 커스텀 해시 함수를 짜고, 단사 조건이 붕괴하며 발생하는 충돌 횟수(Collision Count)를 측정하는 시뮬레이터 작성.

Practical

Core Topic 03: 역함수와 합성을 통한 파이프라인 (Inverse & Composition)

• Why to Learn: 데이터를 이리저리 꼬아서 암호화(합성)한 뒤, 반대편에서 정확하게 원래 데이터로 풀어내는(역함수) 엔드투엔드 파이프라인을 구축하기 위함입니다.
• What to Learn:
  • Concepts: 역함수(Inverse Function, $f^{-1}$), 함수의 합성(Composition, $f \circ g$).
  • Skills: 가역 함수(Invertible Function), 교환 법칙 성립 불가($f \circ g \neq g \circ f$), 함수형 프로그래밍 파이프라인.
  • Tools: 함수 체이닝(Function Chaining), 커링(Currying).
  • Trade-offs: 작은 함수 여러 개를 합성($f(g(h(x)))$)하여 단위 테스트(Unit Test)를 완벽히 통제하는 모듈성 vs 함수를 부를 때마다 콜 스택(Call Stack)이 쌓이면서 미세하게 깎여나가는 CPU 지연 시간 오버헤드.
• How to Learn:
  • 1단계: 함수가 역함수를 가지려면 반드시 전단사(Bijective)여야 한다는 수리적 증명을 통해, 대칭키 암호화 알고리즘이 왜 1<1> 무손실 맵핑 구조를 강제하는지 뜯어봅니다.
  • 2단계: 양말을 신고($g$) 신발을 신는($f$) 순서($f \circ g$)와 신발을 신고 양말을 신는 순서($g \circ f$)가 물리적으로 완전히 다른 결과를 낳는 합성 함수의 비환원적 특성을 분석합니다.
• Implement: 텍스트를 대문자로 바꾸는 함수 $A$와 공백을 지우는 함수 $B$를 파이프 연산자(Pipe)처럼 무한히 합성할 수 있는 compose(A, B, C...) 형태의 고위 함수(Higher-Order Function) 엔진 구현.

Advanced

Core Topic 04: 컴퓨터 공학을 위한 특수 알고리즘 함수 (Algorithmic Functions)

• Why to Learn: CPU의 ALU(산술논리장치)가 가장 빠르고 좋아하게끔 수학 방정식을 코드로 비틀어 버리는 성능 최적화의 끝판왕이기 때문입니다.
• What to Learn:
  • Concepts: 바닥/천장 함수($\lfloor x \rfloor$, $\lceil x \rceil$), 모듈로(Modulo, $a \pmod b$), 지수/로그 함수($e^x$, $\log x$).
  • Skills: 모듈로 연산을 이용한 원형 큐(Circular Queue) 포인터 랩어라운드(Wraparound), $O(\log N)$ 알고리즘 시간 복잡도.
  • Tools: CPU Bitwise Operations (&, >>).
  • Trade-offs: $N$으로 모듈로 연산(% N)을 수행하는 느린 나눗셈 회로 vs $N$이 2의 거듭제곱일 때 비트 연산(& (N-1))으로 치환하여 연산 속도를 10배 끌어올리는 극단적 마이크로 최적화.
• How to Learn:
  • 1단계: 이진 탐색(Binary Search) 알고리즘에서 탐색 범위가 반씩 썰려나가는 과정이 왜 수학적으로 $\log_2 N$ 함수 곡선을 그리며 떨어지는지 수리적 점근선을 증명합니다.
  • 2단계: 1부터 10번까지 버퍼가 있을 때, 11번째 데이터가 다시 1번으로 돌아가 덮어씌우는 원형 배열(Ring Buffer)의 물리적 주소 계산을 모듈로 함수 1줄로 처리하는 마법을 해부합니다.
• Implement: 배열 사이즈가 $2^K$인 커스텀 링 버퍼(Ring Buffer)를 만들고, 인덱스 초과 시 배열 처음으로 돌아가는 로직을 일반 모듈로(%) 연산과 비트 마스크(&) 연산으로 각각 짜서 1억 번 수행 후 CPU 틱(Tick)을 프로파일링하는 벤치마크.

7. Terminology

8. References

Primary References

• [P1] CS2023 - DS/Discrete Structures and Modeling — Core functions and mapping.
• [P2] SWEBOK v4.0 - Computing Foundations / Discrete Mathematics — Applied foundations.

Secondary References

• [Discrete Mathematics Tutorial] Stanford CS103 — Rigorous approach to proofs and functions.
• [Book of Proof] Richard Hammack — Step-by-step function mapping logic.

Industry References

• [Type Systems in Programming Languages] Benjamin Pierce — Function types and safety.
• [Purely Functional Data Structures] Chris Okasaki — Functional mapping in practice.

9. Final Checklist

Primary Checklist

• 특정 대응 규칙이 왜 '함수'가 될 수 없는지(혹은 왜 함수인지) 공리적 정의를 바탕으로 입증할 수 있는 가? (P1)
• 함수의 합성 ($g \circ f$) 결과가 단사/전사가 되기 위해 원래 함수 $f, g$가 갖춰야 할 최소 조건을 추론 가능한가? (P1)

Secondary Checklist

• 해시 충돌(Hash Collision) 현상을 비둘기집 원리를 이용해 수학적으로 모델링하고, 충돌 없는 해시가 존재하기 위한 공간 조건을 제시할 수 있는가?
• 바닥 함수와 천장 함수의 성질을 이용해 부동 소수점 연산에서 발생할 수 있는 오차를 정수 범위로 제한하는 논리를 설계할 수 있는가?

Industry Checklist

• API 설계 시, 입력 파라미터(Domain)와 리턴 타입(Codomain)의 일관성을 함수적 무결성 관점에서 검증하고 타입 오류를 예방할 수 있는가? (SFIA)
• 함수형 프로그래밍 아키텍처를 도입할 때, 모나드(Monad)나 파이프라인 구조가 왜 수학적 '함수 합성'의 연장선에 있는지 동료에게 설명할 수 있는 가?