Lesson 10 of 20

함수 — 하나에 하나씩만 짝지어 주는 규칙

단사 · 전사 · 전단사, 그리고 해시와 암호

9강의 관계 중에서 특별한 조건을 만족하는 것을 함수(function)라고 부릅니다. 조건은 딱 두 가지예요.

출발 집합(정의역)의 모든 원소에 짝이 있다 — 빠뜨리는 게 없다
각 원소의 짝은 정확히 하나다 — 화살표가 두 개 나가면 안 된다

"자판기"를 떠올리면 쉽습니다. 버튼을 누르면(입력) 음료가 하나 나옵니다(출력). 같은 버튼을 눌렀는데 어떨 땐 콜라, 어떨 땐 사이다가 나오면 고장난 자판기죠 — 그건 함수가 아닙니다.

📥

정의역

넣을 수 있는 것 전체

📤

공역

나올 수 있는 후보 전체

🎯

치역

실제로 나온 것들

High school하나에 하나씩만 짝지어 주는 규칙

9강의 관계 중에서 특별한 조건을 만족하는 것이 함수입니다.

모든 입력에 답이 정확히 하나씩 있어야 한다

두 조건

조건	어기면
빠짐없이	답이 없는 입력 ⚠
하나씩만	답이 둘인 입력 ⚠

관계는 자유롭고 함수는 규칙적이다

왜 이 제한이 유용한가

제한 덕에	가능해지는 것
답이 하나	계산할 수 있다
빠짐없다	예외를 안 따진다
—	합성할 수 있다

제한이 다룰 수 있게 만든다 — 이 강의의 반복 주제다

비유 — 자판기

버튼	나오는 것
같은 버튼	항상 같은 음료 ✔
—	두 개 나오면 고장
—	안 나오면 고장

"고장이 아니다" 는 조건이 곧 함수의 정의다

프로그래밍의 함수와 비교하면

	수학의 함수	코드의 함수
같은 입력	항상 같은 출력	다를 수 있다 ⚠
부작용	없다	있을 수 있다

수학의 함수처럼 짠 것을 순수 함수라 한다 — 테스트가 쉽다

치역 ⊆ 공역. 안 쓰인 값이 있어도 함수는 함수입니다.

Python Runs in your browser

# 함수는 딕셔너리로 표현하면 정확합니다 — 열쇠 하나에 값 하나
정의역 = ["민준", "서연", "지호", "하윤"]
공역   = [1, 2, 3, 4, 5, 6]          # 나올 수 있는 조 번호

배정 = {"민준": 1, "서연": 2, "지호": 1, "하윤": 3}    # f: 학생 → 조

print("f =", 배정)
print("정의역의 모든 원소에 짝이 있는가?", all(x in 배정 for x in 정의역))
print("치역 (실제로 쓰인 값):", sorted(set(배정.values())))
print("공역 중 안 쓰인 값:", sorted(set(공역) - set(배정.values())))

🎮 화살표를 그어 보세요

왼쪽 원소를 오른쪽 원소에 이어 보세요. 함수인지 아닌지, 함수라면 단사·전사·전단사 중 무엇인지 즉시 판정해 드립니다. 화살표를 두 개 그으면 왜 함수가 아닌지도 보여 줘요.

High school단사 · 전사 · 전단사

세 가지 성질을 왜 나누는지와 함께.

이름	뜻	일상어로
단사	서로 다른 입력 → 다른 출력	겹치지 않는다
전사	모든 출력값이 쓰인다	빠짐없다
전단사	둘 다	완벽한 일대일 짝

전단사여야 역함수가 있다 — 되돌릴 수 있다

왜 그런가

빠지면	되돌릴 때 문제
단사가 아니다	어느 입력이었는지 모른다 ⚠
전사가 아니다	어떤 값은 돌아갈 곳이 없다

되돌리려면 일대일 대응이어야 한다

전단사의 힘 — 세는 도구

두 집합 사이에 전단사가 있으면 크기가 같습니다.

쓰임	예
부분집합 ↔ 비트열	7강 — 2ⁿ ⭐
자연수 ↔ 짝수	무한인데 크기가 같다

직접 세지 않고 짝을 지어 센다 — 조합론의 기본 기술

비유 — 의자와 사람

확인	알 수 있는 것
다들 앉았고 빈 의자가 없다	인원 = 의자 수 ✔

세어 보지 않고도 같다는 것을 압니다. 그게 전단사의 힘이에요.

무한집합에서는 이 방법밖에 없다 — 셀 수가 없으니까

세 가지 이름

이름	조건	비유
단사 (일대일, injective)	서로 다른 입력 → 서로 다른 출력	도착지 원소에 화살표가 많아야 하나
전사 (위로의, surjective)	공역의 모든 원소가 쓰인다	도착지에 화살표가 적어도 하나씩
전단사 (일대일 대응, bijective)	단사이면서 전사	도착지에 화살표가 정확히 하나씩

전단사일 때만 역함수가 있습니다. 되돌리려면 짝이 딱 맞아떨어져야 하니까요. 암호를 복호화할 수 있는 것도, 압축을 풀 수 있는 것도 그 변환이 전단사이기 때문입니다.

같은 규칙이라도 공역을 어떻게 잡느냐에 따라 전사 여부가 달라집니다.

Python Runs in your browser

def 판정(f, 정의역, 공역, 이름):
    값들 = [f(x) for x in 정의역]
    단사 = len(set(값들)) == len(값들)
    전사 = set(값들) == set(공역)
    종류 = "전단사 (역함수 있음!)" if (단사 and 전사) else \
           "단사" if 단사 else "전사" if 전사 else "그냥 함수"
    print(f"{이름:<22} 단사 {단사!s:<6} 전사 {전사!s:<6} → {종류}")

A = [1, 2, 3, 4]
판정(lambda x: x + 10,   A, [11, 12, 13, 14], "f(x) = x + 10")
판정(lambda x: x % 2,    A, [0, 1],           "f(x) = x % 2")
판정(lambda x: x * x,    A, [1, 4, 9, 16, 25], "f(x) = x²")

High school단사가 깨지면 되돌릴 수 없습니다

note 의 이 경고가 해시와 암호로 이어집니다.

여러 입력이 같은 출력이면 — 원래를 못 찾는다

해시 함수가 그렇습니다

—	—
입력	임의 길이 — 무한
출력	고정 길이 — 유한

무한을 유한에 넣으니 반드시 겹친다 — 16강 비둘기집

그런데 이게 '장점' 이기도 합니다

용도	단사가 아닌 것이
비밀번호 저장	좋다 ✔ — 되돌릴 수 없어야
해시 테이블	충돌 처리로 해결
암호화	나쁘다 ⚠ — 복호화해야 한다

되돌릴 수 없음이 목적일 때와 문제일 때가 다르다

해싱과 암호화는 다릅니다

	해싱	암호화
되돌리기	불가능	가능 (열쇠로)
함수 성질	단사 아님	전단사 ✔
쓰임	비밀번호 · 무결성	비밀 통신

비밀번호를 암호화하면 잘못이다 — 해싱해야 한다

암호화는 열쇠가 있으면 풀립니다. 그 열쇠가 유출되면 전부 뚫려요.

비유 — 지문과 사진

	지문 (해시)	사진 (암호화)
본인 확인	된다 ✔	된다
지문에서 사람을 복원	불가능 ✔	가능

확인은 되는데 복원은 안 되는 것 — 그게 해시가 하는 일이다

합성함수 — 자판기를 이어 붙이기

(g ∘ f)(x) = g(f(x)). f 의 출력을 g 에 넣는 것입니다. 순서가 중요합니다 — 양말을 신고 신발을 신는 것과 반대는 결과가 다르죠.

전단사이므로 딕셔너리를 통째로 뒤집어 역함수를 만들 수 있습니다.

Python Runs in your browser

def f(x): return x + 3
def g(x): return x * 2

for x in range(1, 5):
    print(f"x={x}  g(f(x)) = g({f(x)}) = {g(f(x))}    f(g(x)) = f({g(x)}) = {f(g(x))}")
print()
print("→ 합성은 순서를 바꾸면 결과가 달라집니다 (교환법칙이 성립하지 않음)")

# 전단사 함수의 역함수
암호화 = {c: chr((ord(c) - 97 + 3) % 26 + 97) for c in "abcdefghijklmnopqrstuvwxyz"}
복호화 = {v: k for k, v in 암호화.items()}      # 뒤집기 — 전단사라서 가능합니다
말 = "hello"
숨김 = "".join(암호화[c] for c in 말)
print(f"\n'{말}' → '{숨김}' → '{''.join(복호화[c] for c in 숨김)}'  (카이사르 암호)")

High school꼭 기억하세요

10강의 정리와 합성 이야기입니다.

함수 = 답이 정확히 하나인 관계

함수의 합성

함수를 이어 붙일 수 있습니다.

(g∘f)(x) = g(f(x)) — f 를 하고 그 결과에 g 를

성질	성립하나
결합법칙	✔ — (h∘g)∘f = h∘(g∘f)
교환법칙	안 된다 ⚠ — 순서가 중요

"양말 신고 신발 신기" 와 반대는 다르다

합성이 성질을 물려받습니다

f 와 g 가	g∘f 도
둘 다 단사	단사 ✔
둘 다 전사	전사 ✔
둘 다 전단사	전단사 ✔

좋은 성질은 이어 붙여도 유지된다 — 그래서 조립할 수 있다

프로그래밍에서

result = g(f(x))          # 합성
pipeline = compose(g, f)  # 함수를 값처럼

분야	합성이 쓰이는 곳
함수형 프로그래밍	파이프라인
유닉스	`\|` — `/os` 10강 ⭐
딥러닝	층을 쌓는 것 — `/dl` 3강

"작은 것을 이어 붙인다" 는 발상이 세 분야에 같은 모양으로 있다

그리고 /dl 4강의 연쇄법칙도 합성함수의 미분입니다. 여기서 이어져요.

🤔 Check yourself

어떤 규칙이 함수가 아닌 경우는?

🤔 Check yourself

역함수가 존재하기 위한 조건은?

🤔 Check yourself

비밀번호를 해시로 저장하는 이유를 함수의 언어로 말하면?