토픽 5 / 21·답안작성
그림/도식 템플릿
💡
시험장에서 빠르게 그릴 수 있는 표준 도식 모음
1. 계층 구조 (Layer)
OSI 7계층
┌─────────────────┐ │ 7. Application │ HTTP, FTP, SMTP ├─────────────────┤ │ 6. Presentation│ 암호화, 압축 ├─────────────────┤ │ 5. Session │ 세션 관리 ├─────────────────┤ │ 4. Transport │ TCP/UDP, 포트 ├─────────────────┤ │ 3. Network │ IP, 라우팅 ├─────────────────┤ │ 2. Data Link │ MAC, 스위치 ├─────────────────┤ │ 1. Physical │ 케이블, 허브 └─────────────────┘
TCP/IP 4계층
┌─────────────────┐ │ Application │ HTTP, DNS, FTP ├─────────────────┤ │ Transport │ TCP, UDP ├─────────────────┤ │ Internet │ IP, ICMP, ARP ├─────────────────┤ │ Network Access │ Ethernet, WiFi └─────────────────┘
3-Tier 아키텍처
┌─────────────────┐ │ Presentation │ Web/Mobile UI ├─────────────────┤ │ Business Logic │ Application Server ├─────────────────┤ │ Data │ Database └─────────────────┘
2. 클라이언트-서버 구조
기본 구조
┌────────┐ ┌────────┐
│ Client │ ──────▶ │ Server │
│ │ ◀────── │ │
└────────┘ Request └────────┘
Response로드밸런서 포함
┌──────────┐
┌────▶│ Server 1 │
┌────────┐ │ └──────────┘
│ Client │───▶│ LB ┌──────────┐
└────────┘ │ ───▶│ Server 2 │
│ └──────────┘
└────▶┌──────────┐
│ Server 3 │
└──────────┘CDN 구조
┌────────┐ ┌──────┐ ┌────────┐
│ Client │────▶│ CDN │────▶│ Origin │
└────────┘ │ Edge │ │ Server │
└──────┘ └────────┘
↓
[캐시 히트시 바로 응답]3. 마이크로서비스 아키텍처
MSA 기본 구조
┌─────────────────────────────────┐
│ API Gateway │
└───────────┬─────────────────────┘
┌────────────────────┼────────────────────┐
▼ ▼ ▼
┌────────────┐ ┌────────────┐ ┌────────────┐
│ Service A │ │ Service B │ │ Service C │
│ ┌───┐ │ │ ┌───┐ │ │ ┌───┐ │
│ │DB │ │ │ │DB │ │ │ │DB │ │
│ └───┘ │ │ └───┘ │ │ └───┘ │
└────────────┘ └────────────┘ └────────────┘이벤트 기반 MSA
┌──────────┐ ┌─────────────────┐ ┌──────────┐
│ Service A│────▶│ Message Bus │────▶│ Service B│
└──────────┘ │ (Kafka/MQ) │ └──────────┘
└────────┬────────┘
│
┌────────▼────────┐
│ Service C │
└─────────────────┘Service Mesh (Sidecar)
┌─────────────────────────────────────┐ │ Service A │ │ ┌─────────┐ ┌───────────┐ │ │ │ App │◀────▶│ Sidecar │◀───▶│ Mesh │ └─────────┘ │ (Envoy) │ │ │ └───────────┘ │ └─────────────────────────────────────┘
4. 데이터베이스 구조
Master-Slave 복제
┌──────────┐
│ Master │
│ (Write) │
└────┬─────┘
│ Replication
┌───────┼───────┐
▼ ▼ ▼
┌──────┐ ┌──────┐ ┌──────┐
│Slave1│ │Slave2│ │Slave3│
│(Read)│ │(Read)│ │(Read)│
└──────┘ └──────┘ └──────┘샤딩 (Sharding)
┌─────────────────────────────────┐
│ Router │
└───────────┬─────────────────────┘
┌───────┼───────┬───────┐
▼ ▼ ▼ ▼
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│Shard│ │Shard│ │Shard│ │Shard│
│ A-F │ │ G-L │ │ M-R │ │ S-Z │
└─────┘ └─────┘ └─────┘ └─────┘캐시 전략 (Cache-Aside)
┌────────┐ 1.조회 ┌───────┐
│ App │─────────▶│ Cache │
└───┬────┘ └───┬───┘
│ │
│ 2.Miss시 │ 1.Hit시
▼ ▼
┌────────┐ [바로 반환]
│ DB │
└────────┘
│
└──▶ 3.Cache 갱신5. 보안 구조
방화벽 구성
┌──────────┐ ┌────────┐ ┌────────┐ ┌──────────┐
│ Internet │──▶│ FW │──▶│ DMZ │──▶│ Internal │
└──────────┘ │(외부) │ │(Web/WAS)│ │ Network │
└────────┘ └────────┘ └──────────┘
│
┌────▼────┐
│ FW │
│ (내부) │
└────┬────┘
▼
┌────────┐
│ DB │
└────────┘인증 흐름 (OAuth 2.0)
┌────────┐ ┌────────────┐
│ User │ │ Auth │
└───┬────┘ │ Server │
│ 1.로그인 요청 └─────┬──────┘
▼ │
┌────────┐ 2.인증 요청 ──────────▶│
│ Client │ │
│ App │◀──────────── 3.토큰 발급│
└───┬────┘ │
│ 4.토큰으로 API 요청 │
▼ │
┌────────────┐ 5.토큰 검증 ───────▶│
│ Resource │ │
│ Server │◀──────── 6.검증 결과 │
└────────────┘암호화 방식
대칭키:
┌─────┐ 같은 키 ┌─────┐
│평문 │──────────▶│암호문│
└─────┘ Key └──┬──┘
│ 같은 키
▼
┌─────┐
│평문 │
└─────┘
비대칭키:
┌─────┐ 공개키(암호화) ┌─────┐ 개인키(복호화) ┌─────┐
│평문 │──────────────▶│암호문│───────────────▶│평문 │
└─────┘ └─────┘ └─────┘6. 프로세스/플로우
CI/CD 파이프라인
┌──────┐ ┌───────┐ ┌──────┐ ┌──────┐ ┌────────┐
│ Code │──▶│ Build │──▶│ Test │──▶│Deploy│──▶│ Monitor│
└──────┘ └───────┘ └──────┘ └──────┘ └────────┘
│ │ │ │
└──────────┴───────────┴──────────┘
자동화 (Jenkins/GitLab CI)DevOps 무한루프
┌─────────────────────────────┐
│ │
▼ │
┌──────┐ ┌────┴───┐
│ Plan │ │ Monitor│
└──┬───┘ └────────┘
│ ▲
▼ │
┌──────┐ ┌──────┐ ┌──────┐ │
│ Code │──▶│Build │──▶│ Test │───┤
└──────┘ └──────┘ └──────┘ │
│
┌───────┐ ┌───────┐ ┌───────┐ │
│Release│─▶│Deploy │─▶│Operate│──┘
└───────┘ └───────┘ └───────┘애자일 스프린트
┌─────────────────────────────────────────────────────┐
│ Sprint (2-4주) │
│ ┌────────┐ ┌────────┐ ┌────────┐ ┌──────────┐ │
│ │Planning│─▶│ Daily │─▶│ Review │─▶│ Retro │ │
│ │ │ │ Standup│ │ │ │ │ │
│ └────────┘ └────────┘ └────────┘ └──────────┘ │
└─────────────────────────────────────────────────────┘
│
▼
┌─────────────────────┐
│ Increment (산출물) │
└─────────────────────┘7. 컨테이너/클라우드
컨테이너 vs VM
VM: Container: ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │App A│ │App B│ │App C│ │App A│ │App B│ │App C│ ├─────┤ ├─────┤ ├─────┤ └──┬──┘ └──┬──┘ └──┬──┘ │Guest│ │Guest│ │Guest│ │ │ │ │ OS │ │ OS │ │ OS │ ┌──┴───────┴───────┴──┐ ├─────┴─┴─────┴─┴─────┤ │ Container Engine │ │ Hypervisor │ │ (Docker) │ ├─────────────────────┤ ├─────────────────────┤ │ Host OS │ │ Host OS │ ├─────────────────────┤ ├─────────────────────┤ │ Hardware │ │ Hardware │ └─────────────────────┘ └─────────────────────┘
Kubernetes 구조
┌─────────────────────────────────────────────────────┐
│ Master Node │
│ ┌──────────┐ ┌──────────┐ ┌────────┐ ┌─────────┐ │
│ │API Server│ │Scheduler │ │ etcd │ │Controller│ │
│ └──────────┘ └──────────┘ └────────┘ │ Manager │ │
│ └─────────┘ │
└─────────────────────────────────────────────────────┘
│
┌──────────────┼──────────────┐
▼ ▼ ▼
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ Worker Node │ │ Worker Node │ │ Worker Node │
│ ┌─────────┐ │ │ ┌─────────┐ │ │ ┌─────────┐ │
│ │ kubelet │ │ │ │ kubelet │ │ │ │ kubelet │ │
│ └─────────┘ │ │ └─────────┘ │ │ └─────────┘ │
│ ┌───┐ ┌───┐ │ │ ┌───┐ ┌───┐ │ │ ┌───┐ ┌───┐ │
│ │Pod│ │Pod│ │ │ │Pod│ │Pod│ │ │ │Pod│ │Pod│ │
│ └───┘ └───┘ │ │ └───┘ └───┘ │ │ └───┘ └───┘ │
└─────────────┘ └─────────────┘ └─────────────┘클라우드 서비스 모델
┌─────────────────────────────────────────────────────┐ │ 사용자 관리 영역 │ │ On-Premise IaaS PaaS SaaS │ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐│ │ │ App │ │ App │ │ App │ │ ││ │ │ Data │ │ Data │ │ Data │ │ ││ │ │ Runtime │ │ Runtime │ │ │ │ ││ │ │ OS │ │ OS │ │ │ │ ││ │ │ 가상화 │ │ │ │ │ │ ││ │ │ 서버 │ │ │ │ │ │ ││ │ │ 스토리지 │ │ │ │ │ │ ││ │ │ 네트워크 │ │ │ │ │ │ ││ │ └─────────┘ └─────────┘ └─────────┘ └─────────┘│ │ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │ │ CSP 관리 영역 │ └─────────────────────────────────────────────────────┘
8. 데이터 구조
B+ Tree 인덱스
┌─────────────┐
│ 10 │ 20 │ (루트)
└──┬──┴──┬────┘
┌───────────┘ └───────────┐
▼ ▼
┌─────────────┐ ┌─────────────┐
│ 3 │ 7 │ │ 15 │ 18 │ (내부)
└─┬──┴──┬─────┘ └──┬──┴──┬────┘
│ │ │ │
┌─▼─┐ ┌─▼─┐ ┌─▼─┐ ┌─▼─┐
│1,2│→│3-6│→ ... │10-14│→│15-17│→... (리프)
└───┘ └───┘ └────┘ └────┘
↑ 리프 노드 연결 리스트 (순차 검색)해시 테이블
Key Hash Index Value
───────────────────────────
"A" ─▶ h("A") ─▶ [0] ─▶ value1
"B" ─▶ h("B") ─▶ [1] ─▶ value2
"C" ─▶ h("C") ─▶ [1] ─▶ value3 (충돌→체이닝)
↓
[value2]→[value3]스택 vs 큐
Stack (LIFO): Queue (FIFO):
┌───┐ ┌───┬───┬───┬───┐
│ 3 │ ← top ──▶│ 1 │ 2 │ 3 │ 4 │──▶
├───┤ push/pop rear└───┴───┴───┴───┘front
│ 2 │ enqueue dequeue
├───┤
│ 1 │
└───┘배열 vs 연결 리스트
배열 (Array) - 연속 메모리, 인덱스 직접 접근 ┌────┬────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ │ └────┴────┴────┴────┴────┴────┘ [0] [1] [2] [3] [4] [5] ↑ O(1) 랜덤 접근 ↑ 삽입/삭제 O(n) 이동 필요 연결 리스트 (Linked List) - 비연속 메모리, 포인터 연결 ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │ 10 │ ──────▶│ 20 │ ──────▶│ 30 │ ──────▶│ 40 │ null │ └──────────┘ └──────────┘ └──────────┘ └──────────┘ head tail | 항목 | 배열 | 연결 리스트 | |-----------|-------|-----------| | 접근 | O(1) | O(n) | | 삽입(앞/중) | O(n) | O(1) | | 삽입(뒤) | O(1)* | O(n)/O(1) | | 메모리 | 연속 | 비연속 | | 캐시 효율 | 높음 | 낮음 |
이중 연결 리스트 (Doubly Linked List)
prev next prev next prev next
null ◀─┌──────────┐──▶┌──────────┐──▶┌──────────┐─▶ null
│ Node A │ │ Node B │ │ Node C │
└──────────┘◀──└──────────┘◀──└──────────┘
head tail
삽입 (B 뒤에 X 삽입):
B.next = X X.prev = B
X.next = C C.prev = X
삭제 (B 삭제):
A.next = C C.prev = A원형 큐 (Circular Queue / Ring Buffer)
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ │ A │ B │ C │ D │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5 6 7
↑ ↑
front rear
enqueue: rear = (rear+1) % size
dequeue: front = (front+1) % size
Full: (rear+1) % size == front
Empty: front == rear덱 (Deque)
◀── push_front push_back ──▶
◀── pop_front pop_back ──▶
┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │
└───┴───┴───┴───┴───┘
front back
양쪽 삽입/삭제 O(1)이진 트리 종류
완전 이진 트리 포화 이진 트리 편향 이진 트리
(Complete) (Full/Perfect) (Skewed)
1 1 1
/ \ / \ /
2 3 2 3 2
/ \ / \ / \ /
4 5 4 5 6 7 3
/
마지막 레벨 왼쪽부터 모든 레벨 꽉 참 4
한쪽으로만 → O(n)이진 탐색 트리 (BST) - 삽입/탐색/삭제
8 삽입 5: 루트(8)→좌(3)→우(6)→좌(5)
/ \
3 10 탐색 6: 루트(8)→좌(3)→우(6) ✓
/ \ \
1 6 14 삭제 3 (자식 2개):
/ \ / → 중위 후속자(4)로 교체
4 7 13 4
/ \
1 6
/ \
5 7AVL 트리 회전
LL 회전 (Right Rotation): RR 회전 (Left Rotation):
z z
/ \ / \
y T4 → y T1 y → y
/ \ / \ / \ / \
x T3 x z T2 x z x
/ \ / \ / \ / \ / \ / \
T1 T2 T1 T2 T3 T4 T3 T4 T1 T2 T3 T4
LR 회전 (Left-Right): RL 회전 (Right-Left):
z z z z
/ \ / \ / \ / \
x T4 → y T4 → y T1 x → T1 y → y
/ \ / \ / \ / \ / \ / \
T1 y x T3 x z y T4 T2 x z x
/ \ / \ / \ / \ / \ / \ / \ / \
T2 T3 T1 T2 T1 T2 T3 T4 T2 T3 T3 T4 T1 T2 T3 T4Red-Black 트리 속성
8(B) 속성:
/ \ 1. 노드는 Red 또는 Black
4(R) 12(R) 2. 루트는 항상 Black
/ \ / \ 3. 모든 리프(NIL)는 Black
2(B) 6(B) 10(B) 14(B) 4. Red 노드의 자식은 Black
/ \ / \ / \ / \ (연속 Red 불가)
N N N N N N N N 5. 루트→리프 경로의
Black 수 동일 (Black Height)
삽입 후 재조정: Uncle이 Red → 색상 변환
Uncle이 Black → 회전 + 색상 변환B-트리 (B-Tree) - 차수 m=3
[10 | 20] ← 루트: 최대 m-1=2개 키
/ | \
[5|7] [12|15] [25|30] ← 내부: ⌈m/2⌉-1 ~ m-1개 키
/| \ / | \ / | \
... ... ... ... ... ... ... ← 모든 리프 같은 깊이
B-Tree vs B+Tree:
| 항목 | B-Tree | B+Tree |
|-----------|---------------------|----------------------|
| 데이터 위치 | 모든 노드 | 리프 노드만 |
| 리프 연결 | 없음 | 연결 리스트 |
| 범위 검색 | 비효율적 | 리프 순차 탐색 효율적 |
| 키 중복 | 없음 | 내부 키 = 리프에도 존재 |
| 주 용도 | 일반 DB | RDBMS 인덱스, 파일시스템 |힙 (Heap) - 삽입/삭제
Max-Heap: 삽입(15): 삭제(루트):
20 20 ?
/ \ / \ / \
15 10 → 15 10 → 15 10
/ \ / / \ / / \ /
8 5 3 8 5 3 8 5 3
↑ 15삽입
15와 부모 비교→교체 1) 마지막(3)을 루트로
2) 자식과 비교→swap
20 15
/ \ 배열 표현: / \
15 10 [20, 15, 10, 8, 5, 3] 10 3
/ \ / 부모: (i-1)/2 / \
8 5 3 왼자식: 2i+1 8 5
오른자식: 2i+2해시 충돌 해결 - 체이닝 vs 개방주소법
체이닝 (Chaining): 개방주소법 (Open Addressing):
┌───┐ ┌───┐
│ 0 │→ null │ 0 │ A
├───┤ ├───┤
│ 1 │→[B]→[E]→null │ 1 │ B 선형 탐사: h(k)+1, +2, +3...
├───┤ ├───┤
│ 2 │→[C]→null │ 2 │ E 이차 탐사: h(k)+1², +2², +3²...
├───┤ ├───┤
│ 3 │→ null │ 3 │ C 이중 해싱: h(k)+i·h₂(k)
├───┤ ├───┤
│ 4 │→[A]→[D]→null │ 4 │ A
└───┘ ├───┤
│ 5 │ D ← 4에서 충돌 → 5로
└───┘
| 항목 | 체이닝 | 개방주소법 |
|----------|----------|---------------|
| 충돌 처리 | 리스트 연결 | 다른 슬롯 탐색 |
| 적재율 | >1 가능 | ≤1 (70~80% 권장)|
| 삭제 | 간단 | 삭제 마커 필요 |
| 캐시 효율 | 낮음 | 높음 |
| 클러스터링 | 없음 | 발생 가능 |트라이 (Trie) 구조
(root)
/ | \ \
a b c t
| | | |
p a a o
/ \ | | |
p r t r p
| | |
l (bat) (top)
|
e
|
(apple)
검색 "bat": root→b→a→t ✓ O(L) L=문자열 길이
용도: 자동완성, 사전, IP 라우팅(Longest Prefix Match)
공간: 자식 포인터 배열 (26개 알파벳) or HashMap그래프 표현 - 인접 행렬 vs 인접 리스트
그래프: 인접 행렬: 인접 리스트:
1──2 0 1 2 3 4 1 → [2, 5]
| | 1 [0, 1, 0, 0, 1] 2 → [1, 3, 5]
5──3 2 [1, 0, 1, 0, 1] 3 → [2, 4]
| 3 [0, 1, 0, 1, 0] 4 → [3, 5]
4 4 [0, 0, 1, 0, 1] 5 → [1, 2, 4]
5 [1, 1, 0, 1, 0]
| 항목 | 인접 행렬 | 인접 리스트 |
|------------|----------|-------------|
| 공간 | O(V²) | O(V+E) |
| 간선 확인 | O(1) | O(degree) |
| 모든 인접 정점 | O(V) | O(degree) |
| 적합 | 밀집 그래프 | 희소 그래프 |유니온 파인드 (Union-Find / Disjoint Set)
초기: {1} {2} {3} {4} {5} parent: [1,2,3,4,5]
Union(1,2): {1,2} {3} {4} {5}
Union(3,4): {1,2} {3,4} {5}
Union(1,3): {1,2,3,4} {5}
트리 표현: 경로 압축 후:
1 1
/ \ / | \ \
2 3 2 3 4 (find 시 직접 루트 연결)
|
4
Find(4): 4→3→1 (경로 압축: 4→1)
Union by Rank: 낮은 트리를 높은 트리 아래 병합
시간복잡도: O(α(n)) ≈ O(1) (거의 상수)세그먼트 트리 (Segment Tree) - 구간 합
배열: [2, 1, 5, 3, 4]
[15] ← 전체 합 [0,4]
/ \
[8] [7] ← [0,2], [3,4]
/ \ / \
[3] [5] [3] [4] ← [0,1], [2,2], [3,3], [4,4]
/ \
[2] [1] ← [0,0], [1,1]
구간 합 쿼리 [1,3]: 1 + 5 + 3 = 9 → O(log n)
값 갱신 arr[2]=7: 리프→루트 경로 갱신 → O(log n)
구축: O(n) | 쿼리: O(log n) | 갱신: O(log n)블룸 필터 (Bloom Filter)
삽입 "apple": h₁("apple")=2, h₂("apple")=5, h₃("apple")=9
비트 배열: [0,0,1,0,0,1,0,0,0,1,0,0]
↑ ↑ ↑
삽입 "banana": h₁=1, h₂=5, h₃=7
비트 배열: [0,1,1,0,0,1,0,1,0,1,0,0]
↑ ↑
조회 "cherry": h₁=2, h₂=6, h₃=9
비트[2]=1 ✓ 비트[6]=0 ✗ → 확실히 없음
특징:
- False Positive 가능 (있다고 했는데 실제 없을 수 있음)
- False Negative 불가 (없다고 하면 확실히 없음)
- 삭제 불가 (Counting Bloom Filter로 해결)
- 용도: 캐시 필터, 스팸 필터, DB 조회 최적화LSM-Tree (Log-Structured Merge Tree)
Write ──▶ ┌──────────┐
│ MemTable │ (인메모리, Red-Black Tree/SkipList)
│ (정렬됨) │
└────┬─────┘
Flush ↓ (크기 초과 시)
┌──────────┐
│ SSTable │ Level 0 (디스크, 불변, 정렬됨)
│ L0 │
└────┬─────┘
Compaction ↓ (병합 정렬)
┌──────────┐
│ SSTable │ Level 1 (크기 = L0 × 10)
│ L1 │
└────┬─────┘
┌──────────┐
│ SSTable │ Level 2 (크기 = L1 × 10)
│ L2 │
└──────────┘
Write: O(1) 매우 빠름 (순차 쓰기)
Read: O(log n) (MemTable → L0 → L1 → ... 탐색)
용도: Cassandra, LevelDB, RocksDB, HBaseConsistent Hashing (일관된 해싱)
Node A (0°)
╱
──────●──────
╱ ╱╲ ╲
╱ ╱ ╲ ╲
● ╱ ● ╲ ● Node D (270°)
Node C╱ key1 ╲
(180°)╲ ╱
╲ ╲ ● ╱ ← key2
╲ ╲ ╱ ╱
────●────
Node B (90°)
key1 → 시계 방향 → Node B에 저장
key2 → 시계 방향 → Node C에 저장
Node B 제거: key1만 Node C로 이동 (다른 키 영향 없음)
가상 노드: 각 물리 노드를 여러 위치에 배치 → 균등 분배Merkle Tree (머클 트리)
Root Hash
H(H12+H34)
╱ ╲
H12 H34
H(H1+H2) H(H3+H4)
╱ ╲ ╱ ╲
H1 H2 H3 H4
H(D1) H(D2) H(D3) H(D4)
| | | |
D1 D2 D3 D4
검증: D3 변경 여부 확인에 H4, H12만 있으면 됨
H3'=H(D3') → H34'=H(H3'+H4) → Root' ≠ Root → 변조!
용도: 블록체인, Git, IPFS, 데이터 무결성 검증LRU 캐시 (HashMap + Doubly Linked List)
HashMap: key → Node 참조 (O(1) 접근)
Doubly Linked List (최근 사용 순):
head ←→ [D] ←→ [B] ←→ [A] ←→ [C] ←→ tail
(최근) (오래됨)
GET(B): B를 head로 이동
head ←→ [B] ←→ [D] ←→ [A] ←→ [C] ←→ tail
PUT(E) (캐시 Full):
1) tail의 C 제거 (evict)
2) E를 head에 삽입
head ←→ [E] ←→ [B] ←→ [D] ←→ [A] ←→ tail
시간복잡도: GET O(1), PUT O(1)이진 트리 순회 (Traversal)
1
/ \
2 3
/ \ \
4 5 6
전위 (Pre-order): 루트→좌→우 = 1, 2, 4, 5, 3, 6
중위 (In-order): 좌→루트→우 = 4, 2, 5, 1, 3, 6
후위 (Post-order): 좌→우→루트 = 4, 5, 2, 6, 3, 1
레벨 (Level-order): BFS = 1, 2, 3, 4, 5, 6
BST 중위 순회 = 정렬된 순서 출력스킵 리스트 (Skip List)
Level 3: head ──────────────────────────────▶ 25 ──▶ null Level 2: head ──────▶ 6 ──────────────────▶ 25 ──▶ null Level 1: head ──▶ 3 ─▶ 6 ──▶ 9 ──────────▶ 25 ──▶ null Level 0: head ──▶ 3 ─▶ 6 ──▶ 7 ──▶ 9 ──▶ 12 ──▶ 25 ──▶ null 탐색 9: L3→25(크다)↓ L2→6→25(크다)↓ L1→9 ✓ 평균: O(log n) 삽입/삭제/탐색 레벨 결정: 동전 던지기 (확률적, p=0.5) 용도: Redis Sorted Set, LevelDB MemTable
피보나치 힙 (Fibonacci Heap) - 연산 복잡도
┌─────────────────────────────┐
│ min │──▶ (3)──(7)──(18)──(52) ← 루트 리스트 (이중 연결)
└─────┘ | |
(8) (21) ← 자식 리스트
| |
(24) (39)
| 연산 | 이진 힙 | 피보나치 힙 |
|----------------|----------|---------------|
| Insert | O(log n) | O(1) 분할상환 |
| Find-Min | O(1) | O(1) |
| Delete-Min | O(log n) | O(log n) 분할상환|
| Decrease-Key | O(log n) | O(1) 분할상환 |
| Merge | O(n) | O(1) |9. 알고리즘 흐름
분할 정복 (퀵소트)
[3, 1, 4, 1, 5, 9, 2, 6]
↓ pivot=4
[3, 1, 1, 2] [4] [5, 9, 6]
↓ ↓
[1, 1, 2] [3] [5, 6] [9]
↓
[1, 1] [2]BFS vs DFS
1
/|\
2 3 4
/| |
5 6 7
BFS (Queue): 1 → 2 → 3 → 4 → 5 → 6 → 7
DFS (Stack): 1 → 2 → 5 → 6 → 3 → 4 → 7시간 복잡도 비교 그래프
실행
시간 │ O(n!)
↑ │ ╱
│ ╱
│ O(2ⁿ)
│ ╱
│ O(n²)
│ ╱──
│ O(n log n)
│ ╱──────
│ O(n)───────────
│ ╱─────────────────
│O(log n)────────────────
│O(1)─────────────────────
└────────────────────────────▶ 입력 크기 n
| 복잡도 | 이름 | 예시 |
|------------|---------|------------------------|
| O(1) | 상수 | 해시 조회, 배열 인덱스 |
| O(log n) | 로그 | 이진 탐색, BST 탐색 |
| O(n) | 선형 | 선형 탐색, 순회 |
| O(n log n) | 선형로그 | 병합정렬, 힙정렬 |
| O(n²) | 이차 | 버블정렬, 삽입정렬 |
| O(2ⁿ) | 지수 | 부분집합, 피보나치(재귀) |
| O(n!) | 팩토리얼 | 순열, TSP 브루트포스 |버블 정렬 (Bubble Sort) - 동작 과정
[5, 3, 8, 1, 2] 원본
패스 1: [5,3,8,1,2] → [3,5,8,1,2] → [3,5,8,1,2] → [3,5,1,8,2] → [3,5,1,2,8]
swap ok swap swap ← 8 확정
패스 2: [3,5,1,2|8] → [3,5,1,2] → [3,1,5,2] → [3,1,2,5]
ok swap swap ← 5 확정
패스 3: [3,1,2|5,8] → [1,3,2] → [1,2,3]
swap swap ← 3 확정
패스 4: [1,2|3,5,8] → ok → 완료
특징: 안정 정렬, O(n²), 이미 정렬 시 O(n) 가능 (조기 종료)선택 정렬 (Selection Sort) - 동작 과정
[29, 10, 14, 37, 13] 1회: 최솟값=10 → swap(29,10) → [10, 29, 14, 37, 13] 10 확정 2회: 최솟값=13 → swap(29,13) → [10, 13, 14, 37, 29] 13 확정 3회: 최솟값=14 → 이동 없음 → [10, 13, 14, 37, 29] 14 확정 4회: 최솟값=29 → swap(37,29) → [10, 13, 14, 29, 37] 29 확정 특징: 불안정 정렬, O(n²), 교환 횟수 최소 O(n)
삽입 정렬 (Insertion Sort) - 동작 과정
[5, 2, 4, 6, 1, 3] ─ 정렬된 부분: [5] [5, 2, 4, 6, 1, 3] 2를 삽입 → [2, 5] [2, 5, 4, 6, 1, 3] 4를 삽입 → [2, 4, 5] [2, 4, 5, 6, 1, 3] 6를 삽입 → [2, 4, 5, 6] [2, 4, 5, 6, 1, 3] 1을 삽입 → [1, 2, 4, 5, 6] [1, 2, 4, 5, 6, 3] 3을 삽입 → [1, 2, 3, 4, 5, 6] ✓ 특징: 안정 정렬, O(n²), 거의 정렬 시 O(n), 소규모 데이터에 효율적
병합 정렬 (Merge Sort) - 분할/병합 과정
분할 (Divide): 병합 (Merge):
[38, 27, 43, 3, 9, 82, 10] 정렬된 부분 배열 2개를 비교하며 병합
↓ ↓
[38, 27, 43] [3, 9, 82, 10] [27,38,43] + [3,9,10,82]
↓ ↓ i↑ j↑
[38] [27,43] [3,9] [82,10] 비교: 27 vs 3 → 3 선택
↓ ↓ ↓ 비교: 27 vs 9 → 9 선택
[27] [43] [3][9] [82][10] 비교: 27 vs 10 → 10 선택
↓ ↓ ↓ 비교: 27 vs 82 → 27 선택
[27,43] [3,9] [10,82] ...
↓ ↓ 결과: [3,9,10,27,38,43,82]
[27,38,43] [3,9,10,82]
↓
[3, 9, 10, 27, 38, 43, 82]
특징: 안정 정렬, 항상 O(n log n), 추가 공간 O(n)퀵 정렬 (Quick Sort) - 파티션 과정
[3, 6, 8, 10, 1, 2, 1] pivot=1 (마지막 원소)
i=-1, j 순회:
j=0: 3>1 → skip
j=1: 6>1 → skip
j=2: 8>1 → skip
j=3: 10>1 → skip
j=4: 1≤1 → i=0, swap(arr[0],arr[4]) → [1, 6, 8, 10, 3, 2, 1]
j=5: 2>1 → skip
pivot swap: i=1, swap(arr[1],arr[6]) → [1, 1, 8, 10, 3, 2, 6]
↑ ↑
≤pivot ≥pivot
최선/평균: O(n log n) | 최악(이미 정렬): O(n²)
불안정 정렬 | 추가 공간 O(log n) - 재귀 스택힙 정렬 (Heap Sort) - 동작 과정
[4, 10, 3, 5, 1]
1단계: Max-Heap 구축 (Build Heap)
4 10
/ \ → / \
10 3 5 3 heapify: 아래→위
/ \ / \
5 1 4 1
Max-Heap: [10, 5, 3, 4, 1]
2단계: 추출 반복 (Extract Max)
[10,5,3,4,1] → swap(10,1) → [1,5,3,4|10] → heapify → [5,4,3,1|10]
[5,4,3,1] → swap(5,1) → [1,4,3|5,10] → heapify → [4,1,3|5,10]
[4,1,3] → swap(4,3) → [3,1|4,5,10] → heapify → [3,1|4,5,10]
[3,1] → swap(3,1) → [1|3,4,5,10]
결과: [1, 3, 4, 5, 10] ✓
특징: 불안정 정렬, 항상 O(n log n), 추가 공간 O(1)계수 정렬 (Counting Sort) - 동작 과정
입력: [4, 2, 2, 8, 3, 3, 1] 범위: 0~8 1단계: 카운트 배열 index: 0 1 2 3 4 5 6 7 8 count: 0 1 2 2 1 0 0 0 1 2단계: 누적합 (안정 정렬 위해) cumul: 0 1 3 5 6 6 6 6 7 3단계: 역순 배치 arr[6]=1 → output[cumul[1]-1]=output[0]=1, cumul[1]-- arr[5]=3 → output[cumul[3]-1]=output[4]=3, cumul[3]-- ... 출력: [1, 2, 2, 3, 3, 4, 8] 특징: O(n+k), 안정, 비교 없음, 정수만 가능, 추가 공간 O(k)
기수 정렬 (Radix Sort) - LSD 방식
입력: [170, 45, 75, 90, 802, 24, 2, 66] 1의 자리 정렬: [170, 90, 802, 2, 24, 45, 75, 66] 10의 자리 정렬: [802, 2, 24, 45, 66, 170, 75, 90] 100의 자리 정렬:[2, 24, 45, 66, 75, 90, 170, 802] ✓ 각 자릿수 정렬에 Counting Sort 사용 (안정 정렬 필수) 특징: O(d × (n+k)), d=자릿수, k=기수(10), 안정 정렬
정렬 알고리즘 종합 비교표
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 | |----------|----------|----------|----------|-------|------| | 버블 | O(n) | O(n²) | O(n²) | O(1) | ✓ | | 선택 | O(n²) | O(n²) | O(n²) | O(1) | ✗ | | 삽입 | O(n) | O(n²) | O(n²) | O(1) | ✓ | | 병합 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | ✓ | | 퀵 | O(nlogn) | O(nlogn) | O(n²) | O(logn)| ✗ | | 힙 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | ✗ | | 계수 | O(n+k) | O(n+k) | O(n+k) | O(k) | ✓ | | 기수 | O(d·n) | O(d·n) | O(d·n) | O(n+k)| ✓ |
이진 탐색 (Binary Search) - 동작 과정
정렬 배열: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
1회: low=0, high=9, mid=4 → arr[4]=16 < 23 → low=5
[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
↑mid
2회: low=5, high=9, mid=7 → arr[7]=56 > 23 → high=6
[ 23, 38, 56, 72, 91]
↑mid
3회: low=5, high=6, mid=5 → arr[5]=23 = 23 → 찾음! ✓
[ 23, 38]
↑mid
시간복잡도: O(log n) | 전제: 정렬된 배열
변형: Lower Bound, Upper Bound, Parametric Search동적 프로그래밍 (DP) - 피보나치 비교
재귀 (Top-Down, 중복 계산): 메모이제이션 (Top-Down + 캐시):
fib(5) fib(5)
/ \ / \
fib(4) fib(3) fib(4) fib(3)✓캐시
/ \ / \ / \
fib(3) fib(2) fib(2) fib(1) fib(3) fib(2)✓캐시
/ \ 중복! 중복! / \
fib(2) fib(1) fib(2) fib(1)✓캐시
O(2ⁿ) 지수 시간 O(n) 선형 시간
타뷸레이션 (Bottom-Up):
dp[0]=0, dp[1]=1
dp[2]=dp[0]+dp[1]=1
dp[3]=dp[1]+dp[2]=2
dp[4]=dp[2]+dp[3]=3
dp[5]=dp[3]+dp[4]=5
→ 반복문, O(n) 시간, O(n) 또는 O(1) 공간DP - 0/1 배낭 문제 (Knapsack)
물건: (무게, 가치) = {(2,3), (3,4), (4,5), (5,6)} 배낭 용량 W=5
dp[i][w] = i번째 물건까지 고려, 용량 w일 때 최대 가치
w: 0 1 2 3 4 5
i=0: 0 0 0 0 0 0
i=1: 0 0 3 3 3 3 ← (2,3) 넣기
i=2: 0 0 3 4 4 7 ← (3,4) 넣기: dp[2][5]=max(dp[1][5], dp[1][2]+4)=7
i=3: 0 0 3 4 5 7 ← (4,5)
i=4: 0 0 3 4 5 7 ← (5,6): 용량 부족
답: dp[4][5] = 7 (물건1+물건2: 무게2+3=5, 가치3+4=7)
점화식: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ)탐욕 알고리즘 (Greedy) vs DP
거스름돈 문제 - 동전: [1, 5, 10, 25] 금액: 30
Greedy (큰 것부터): DP (최적 보장):
25 × 1 = 25 dp[0]=0
5 × 1 = 5 dp[1]=1, dp[5]=1, dp[10]=1
───────── dp[25]=1
합계: 30 ✓ (2개) dp[30]=min(dp[30-25]+1, dp[30-10]+1,
dp[30-5]+1, dp[30-1]+1) = 2
Greedy가 실패하는 경우:
동전 [1, 3, 4], 금액 6
Greedy: 4+1+1 = 3개 ✗
DP: 3+3 = 2개 ✓ (최적)
| 항목 | Greedy | DP |
|--------|---------------|-----------------|
| 선택 | 현재 최적 | 전체 최적 |
| 되돌림 | 불가 | 가능 (부분문제) |
| 속도 | 빠름 | 느림 (테이블) |
| 정확성 | 최적 보장 안됨 | 최적 보장 |
| 조건 | 탐욕 선택 속성 | 최적 부분 구조 |Dijkstra 알고리즘 - 최단 경로
1
A ──────── B
|╲ |
4| ╲2 |3
| ╲ |
C ─── D ── E
5 1
시작: A, dist=[A:0, B:∞, C:∞, D:∞, E:∞]
1) 방문 A: dist[B]=1, dist[C]=4, dist[D]=2
2) 방문 D(최소): dist[E]=min(∞, 2+1)=3, dist[C]=min(4, 2+5)=4
3) 방문 B: dist[E]=min(3, 1+3)=3
4) 방문 E: 갱신 없음
5) 방문 C: 갱신 없음
최단 경로: A→B:1, A→D:2, A→D→E:3, A→C:4
특징: 음의 가중치 불가, O((V+E)log V) (우선순위 큐)Bellman-Ford 알고리즘 - 음의 가중치 허용
-1 A ───────▶ B | | 4| 3| ▼ 2 ▼ 음의 사이클 탐지: C ───────▶ D V-1회 반복 후에도 ▲ -3 | 갱신이 발생하면 └──────────┘ → 음의 사이클 존재! V-1=3회 반복 (모든 간선 완화): 초기: [A:0, B:∞, C:∞, D:∞] 1회차: [A:0, B:-1, C:4, D:∞] A→B, A→C 2회차: [A:0, B:-1, C:4, D:2] B→D(=−1+3=2), C→D(=4+2=6→2유지) 3회차: [A:0, B:-1, C:4, D:1] 변화 있으면 계속 | 항목 | Dijkstra | Bellman-Ford | |-----------|----------------|-----------------| | 음의 가중치 | 불가 | 가능 | | 음의 사이클 | 탐지 불가 | 탐지 가능 | | 시간복잡도 | O((V+E)log V) | O(VE) | | 적합 | 양의 가중치 | 음의 가중치 존재시 |
Floyd-Warshall 알고리즘 - 모든 쌍 최단 경로
3 경유지 k를 하나씩 추가하며 갱신
1 ──────▶ 2 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
|╲ |
7| ╲1 |2 초기 (직접 연결): k=1 경유:
▼ ╲ ▼ 1 2 3 4 1 2 3 4
4 ──▶ 3 1[0, 3, 1, 7] 1[0, 3, 1, 7]
2 2[∞, 0, ∞, ∞] 2[∞, 0, ∞, ∞]
3[∞, ∞, 0, ∞] 3[∞, ∞, 0, ∞]
4[∞, ∞, 2, 0] 4[∞, ∞, 2, 0]
k=3 경유 후: 최종 결과:
1 2 3 4 1 2 3 4
1[0, 3, 1, 7] 1[0, 3, 1, 5]
2[∞, 0, ∞, ∞] 2[∞, 0, ∞, ∞]
3[∞, ∞, 0, ∞] 3[∞, ∞, 0, ∞]
4[∞, ∞, 2, 0] 4[∞, ∞, 2, 0]
특징: O(V³), 모든 쌍, 음의 가중치 가능, dp[i][i]<0이면 음의 사이클MST - Kruskal vs Prim
Kruskal (간선 정렬 + Union-Find):
가중치 순 정렬: (A-B,1) (B-C,2) (A-C,3) (C-D,4) (B-D,5)
1) A-B(1) 추가 ✓ {A,B} A ─1─ B
2) B-C(2) 추가 ✓ {A,B,C} A ─1─ B ─2─ C
3) A-C(3) 사이클! ✗ (Union-Find로 판별)
4) C-D(4) 추가 ✓ {A,B,C,D} A ─1─ B ─2─ C ─4─ D MST 완성
Prim (정점 확장 + 우선순위 큐):
시작 A: 인접 간선 {A-B:1, A-C:3}
1) 최소 A-B(1) 선택 → 정점 B 추가, 간선 추가 {B-C:2, B-D:5}
2) 최소 B-C(2) 선택 → 정점 C 추가, 간선 추가 {C-D:4}
3) 최소 C-D(4) 선택 → 정점 D 추가 → MST 완성
| 항목 | Kruskal | Prim |
|----------|-------------------|-------------------|
| 접근 | 간선 중심 | 정점 중심 |
| 자료구조 | Union-Find | 우선순위 큐(Min-Heap)|
| 시간복잡도 | O(E log E) | O(E log V) |
| 적합 | 희소 그래프(E 작음) | 밀집 그래프(E 큼) |위상 정렬 (Topological Sort) - Kahn's Algorithm
DAG: A → B → D
↓ ↓ ↑
C → E → F
진입차수: A:0, B:1, C:1, D:1, E:2, F:1
큐=[A] → 출력: A, 갱신: B(0), C(0)
큐=[B,C] → 출력: B, 갱신: D(0), E(1)
큐=[C,D] → 출력: C, 갱신: E(0)
큐=[D,E] → 출력: D
큐=[E] → 출력: E, 갱신: F(0)
큐=[F] → 출력: F
결과: A → B → C → D → E → F
사이클 존재 시: 모든 노드 출력 불가 → 탐지 가능
용도: 빌드 순서, 수강 선수과목, 작업 스케줄링백트래킹 (Backtracking) - N-Queen (N=4)
(시작)
/ | \ \
Q1열 Q2열 ...
/|\
. . .
1행1열 배치 → 2행 시도:
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
│ Q │ │ │ │ │ Q │ │ │ │ │ │ │ Q │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤
│ │ │ Q │ │ │ │ │ │ Q │ │ Q │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤
│ │ │ │ │✗ │ │ Q │ │ │ │ │ │ │ Q │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤
│ │ │ │ │ │ │ │ │ │✗ │ │ Q │ │ │ ✓해!
└───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘
4행 배치 불가→백트랙 4행 배치 불가→백트랙
가지치기(Pruning): 같은 행/열/대각선 → 즉시 포기KMP 알고리즘 - 실패 함수 + 매칭
패턴: A B A B C 실패 함수(Failure Function) 구축:
인덱스: 0 1 2 3 4 π[0]=0
π값: 0 0 1 2 0 π[1]: B≠A → 0
π[2]: A=A → 1
π[3]: B=B → 2
π[4]: C≠A → 0
텍스트: A B A B A B A B C
패턴: A B A B C
↑ 불일치! (C≠A)
π[3]=2이므로 패턴을 2칸 이동 (앞 2글자 재활용)
텍스트: A B A B A B A B C
패턴: A B A B C
↑ 불일치!
π[3]=2이므로 패턴을 2칸 이동
텍스트: A B A B A B A B C
패턴: A B A B C ← 매칭 성공! ✓
시간복잡도: O(n+m) | 브루트포스 O(nm) 대비 개선허프만 코딩 (Huffman Coding) - 압축
문자 빈도: A:5, B:9, C:12, D:13, E:16, F:45
1) 최소 2개 합치기 (우선순위 큐):
(A:5)(B:9) → (14) (C:12)(D:13) → (25)
/ \ / \
A:5 B:9 C:12 D:13
2) (14)(E:16) → (30) (25)(F:45) → 최종 트리:
/ \
(30) (70) (100)
/ \ / \ / \
(14) E (25) F (45) F:45
/\ /\ / \ 0
A B C D (25) (20)
/ \ / \
C:12 D:13 (14) E:16
/ \
A:5 B:9
코드: F=0, C=100, D=101, A=1100, B=1101, E=111
특징: 접두사 코드(prefix-free), 최적 가변 길이 코딩A* 알고리즘 - 경로 탐색
f(n) = g(n) + h(n)
↑ ↑
실제 비용 휴리스틱(추정)
┌───┬───┬───┬───┬───┐
│ S │ │ │ █ │ │ S: 시작, G: 목표, █: 벽
├───┼───┼───┼───┼───┤
│ │ █ │ │ █ │ │ h(n): 맨해튼 거리 = |x₁-x₂|+|y₁-y₂|
├───┼───┼───┼───┼───┤
│ │ █ │ │ │ │ Open List: 탐색 후보 (우선순위 큐)
├───┼───┼───┼───┼───┤ Closed List: 탐색 완료
│ │ │ │ █ │ G │
└───┴───┴───┴───┴───┘
탐색 과정 (f값 최소 우선):
S(f=6) → 인접 확장 → (1,0)(f=6) → (2,0)(f=6) → ...
┌───┬───┬───┬───┬───┐
│ S │ · │ │ █ │ │ · : 최적 경로
├───┼───┼───┼───┼───┤
│ │ █ │ · │ █ │ │ Dijkstra: h=0 (모든 방향 탐색)
├───┼───┼───┼───┼───┤ A*: h로 목표 방향 유도 → 효율적
│ │ █ │ · │ · │ │
├───┼───┼───┼───┼───┤ h가 admissible(과대추정 안함)이면
│ │ │ │ █ │ G │ 최적 경로 보장
└───┴───┴───┴───┴───┘최대 유량 (Max Flow) - Ford-Fulkerson
용량/유량 s ──16/0──▶ a ──12/0──▶ t │ │↗ ↑ │ 4/0 9/0 │ │ │╱ │ └──13/0──▶ b ──20/0────┘ 증가 경로 1: s→a→t (유량 12) s ──16/12─▶ a ──12/12─▶ t 증가 경로 2: s→b→t (유량 7, 잔여 용량 고려) s ──13/7──▶ b ──20/7──▶ t 증가 경로 3: s→b→a→t (유량 4, 잔여 간선 활용) 최대 유량 = 12 + 7 + 4 = 23 최대유량-최소컷 정리: 최대 유량 = 최소 컷 용량 용도: 네트워크 대역폭, 이분 매칭, 프로젝트 선택
Two Pointers / Sliding Window
Two Pointers (정렬 배열에서 합=target):
[1, 2, 3, 5, 8, 11, 15] target=13
L→ ←R
1+15=16 > 13 → R-- [1,2,3,5,8,11,15] L=0,R=5
1+11=12 < 13 → L++ [1,2,3,5,8,11,15] L=1,R=5
2+11=13 = 13 → 찾음!✓ O(n)
Sliding Window (크기 k=3 최대 합):
[2, 1, 5, 1, 3, 2]
├──────┤ sum=8
├──────┤ sum=8-2+1=7
├──────┤ sum=7-1+3=9 ← 최대!
├──────┤ sum=9-5+2=6
윈도우 이동 시 양 끝만 갱신 → O(n)NP-Complete 관계도
┌─────────────┐
│ 모든 문제 │
└──────┬──────┘
┌───────────┴───────────┐
▼ ▼
┌──────────┐ ┌──────────┐
│ 결정 가능 │ │결정 불가능│
│(Decidable)│ │(Undecidable)
└────┬─────┘ └──────────┘
┌──────┴──────┐ 정지 문제 등
▼ ▼
┌──────┐ ┌────────┐
│ P │ │ NP │ P: 다항 시간 풀이
│ │⊆ │ │ NP: 다항 시간 검증
└──┬───┘ └───┬────┘ NP-Hard: NP 이상 어려움
│ ┌──┴──┐ NP-Complete: NP ∩ NP-Hard
│ ▼ ▼
│ ┌─────────┐ ┌─────────┐
└───▶│NP-Complete│ │NP-Hard │
└─────────┘ └─────────┘
SAT, TSP, 정지문제,
3-COLOR, 체스 최적수
CLIQUE
P = NP? 미해결 문제 (밀레니엄 7대 난제)10. 트랜잭션/분산
2PC (Two-Phase Commit)
Coordinator
│
Phase 1: Prepare
┌────────┼────────┐
▼ ▼ ▼
┌──────┐ ┌──────┐ ┌──────┐
│Part A│ │Part B│ │Part C│
└──┬───┘ └──┬───┘ └──┬───┘
│ Vote │ Vote │ Vote
└────────┼────────┘
▼
Phase 2: Commit/AbortSaga 패턴
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
│ T1 │──▶│ T2 │──▶│ T3 │──▶│ T4 │
│주문 │ │결제 │ │재고 │ │배송 │
└──────┘ └──────┘ └──┬───┘ └──────┘
│ 실패!
▼
┌──────────────────┐
│ 보상 트랜잭션 │
│ C2(결제취소) │
│ C1(주문취소) │
└──────────────────┘CAP 정리
Consistency
/\
/ \
/ \
/ CA \
/────────\
/ CP AP \
/____________\
Partition Availability
Tolerance
분산 시스템: P 필수, C와 A 중 선택
- CP: 일관성 우선 (금융)
- AP: 가용성 우선 (SNS)11. AI/ML 구조
신경망 기본
Input Hidden Output
Layer Layer Layer
(x1)───┐
├───(h1)───┐
(x2)───┤ ├───(y)
├───(h2)───┤
(x3)───┘ │
│
└─────────────────┘
Weight × ActivationCNN 구조
┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ ┌──────┐
│ Input │──▶│ Conv │──▶│Pooling│──▶│ FC │──▶│Output│
│ Image │ │+ReLU │ │ │ │Layer │ │Class │
└───────┘ └───────┘ └───────┘ └───────┘ └──────┘
특징추출 다운샘플링 분류Transformer (Attention)
┌─────────────┐
│ Output │
└──────┬──────┘
│
┌──────▼──────┐
│ Decoder │◀─── Cross
│ ×N layers │ Attention
└──────┬──────┘
│
┌──────▼──────┐
│ Encoder │◀─── Self
│ ×N layers │ Attention
└──────┬──────┘
│
┌──────▼──────┐
│ Input │
│ Embedding │
└─────────────┘RAG 파이프라인
┌─────────┐ 1.쿼리 ┌───────────┐ 2.검색 ┌──────────┐
│ User │────────▶│ Embedding │────────▶│ Vector │
│ Query │ │ Model │ │ DB │
└─────────┘ └───────────┘ └────┬─────┘
│
3.관련 문서
│
┌─────────┐ 5.응답 ┌───────────┐ 4.프롬프트 │
│ Answer │◀────────│ LLM │◀────────────┘
└─────────┘ └───────────┘
Query + Context12. 네트워크 프로토콜
TCP 3-Way Handshake
┌────────┐ ┌────────┐
│ Client │ │ Server │
└───┬────┘ └───┬────┘
│ │
│ ───── SYN (seq=x) ────────▶ │
│ │
│ ◀── SYN+ACK (seq=y,ack=x+1) │
│ │
│ ───── ACK (ack=y+1) ──────▶ │
│ │
│ 연결 수립 완료 │TCP 4-Way Termination
┌────────┐ ┌────────┐
│ Client │ │ Server │
└───┬────┘ └───┬────┘
│ │
│ ───── FIN ────────────────▶ │
│ │
│ ◀──── ACK ──────────────── │
│ │
│ ◀──── FIN ──────────────── │
│ │
│ ───── ACK ────────────────▶ │
│ │
│ TIME_WAIT → CLOSED │TLS 1.3 Handshake
┌────────┐ ┌────────┐
│ Client │ │ Server │
└───┬────┘ └───┬────┘
│ │
│ ─── ClientHello + KeyShare ────▶ │
│ (지원 암호, 키 공유) │
│ │
│ ◀── ServerHello + KeyShare ──── │
│ {Certificate} │
│ {CertVerify} │
│ {Finished} │
│ │
│ ─── {Finished} ────────────────▶ │
│ │
│ 암호화 통신 시작 (1-RTT) │DNS 조회 과정
┌────────┐ 1.질의 ┌──────────┐
│ Client │─────────▶│ Local │
└────────┘ │ DNS │
▲ └────┬─────┘
│ 8.응답 │ 2.캐시 미스
│ ┌────▼─────┐
│ │ Root │ ← 3.TLD 정보
│ │ DNS │
│ └────┬─────┘
│ │
│ ┌────▼─────┐
│ │ TLD │ ← 5.권한 DNS 정보
│ │ DNS │ (.com, .kr)
│ └────┬─────┘
│ │
│ ┌────▼─────┐
└───────────────│권한 DNS │ ← 7.실제 IP
│(example) │
└──────────┘13. 보안 아키텍처
PKI 구조
┌─────────────┐
│ Root CA │
│ (최상위) │
└──────┬──────┘
│ 인증서 발급
┌─────────────┼─────────────┐
▼ ▼ ▼
┌───────────┐ ┌───────────┐ ┌───────────┐
│ 중간 CA 1 │ │ 중간 CA 2 │ │ 중간 CA 3 │
└─────┬─────┘ └─────┬─────┘ └─────┬─────┘
│ │ │
┌────┴────┐ ┌────┴────┐ ┌────┴────┐
▼ ▼ ▼ ▼ ▼ ▼
[서버] [서버] [서버] [서버] [서버] [서버]
인증서 인증서 인증서 인증서 인증서 인증서Zero Trust 아키텍처
┌─────────────────────────────────────────────────────┐ │ Zero Trust │ │ ┌──────────┐ ┌──────────┐ │ │ │ User │ │ Resource │ │ │ │ (Device) │ │ │ │ │ └────┬─────┘ └────▲─────┘ │ │ │ 1.접근 요청 │ │ │ ▼ │ │ │ ┌──────────────┐ 3.정책 적용 ┌─────┴────┐ │ │ │ Identity │───────────────▶│ Policy │ │ │ │ Provider │ │ Engine │ │ │ └──────────────┘ └──────────┘ │ │ │ ▲ │ │ │ 2.신원 확인 │ │ │ ▼ │ │ │ ┌──────────────┐ 컨텍스트 평가 ─────┘ │ │ │ MFA, Device │ │ │ │ Posture │ │ │ └──────────────┘ │ │ │ │ "Never Trust, Always Verify" │ └─────────────────────────────────────────────────────┘
접근통제 모델
RBAC (역할 기반): ┌──────┐ ┌──────┐ ┌──────┐ │ User │─────▶│ Role │─────▶│ Perm │ └──────┘ └──────┘ └──────┘ 관리자 ──▶ Admin ──▶ 읽기/쓰기 ABAC (속성 기반): ┌──────────────────────────────────────┐ │ IF (부서=개발) AND (등급>=3) │ │ AND (시간=업무시간) AND (위치=사내) │ │ THEN 접근 허용 │ └──────────────────────────────────────┘
14. 아키텍처 패턴
헥사고날 (포트 & 어댑터)
┌─────────────────────────────────┐
Driving │ Application │ Driven
(입력측) │ ┌───────────────────────┐ │ (출력측)
│ │ │ │
┌─────────┐ │ │ ┌───────────┐ │ │ ┌─────────┐
│ UI │──▶├──│───▶│ Domain │─────│──┬──├──▶│ DB │
└─────────┘ │ │ │ Core │ │ │ │ └─────────┘
│ │ └───────────┘ │ │ │
┌─────────┐ │ │ │ │ │ ┌─────────┐
│ API │──▶├──│ ▲ │ └──├──▶│ Queue │
└─────────┘ │ │ │ │ │ └─────────┘
│ │ 비즈니스 로직 │ │
│ └───────────────────────┘ │
│ Port Adapter │
└─────────────────────────────────┘클린 아키텍처
┌─────────────────────────────────────────────────────┐ │ Frameworks & Drivers │ │ ┌───────────────────────────────────────────────┐ │ │ │ Interface Adapters │ │ │ │ ┌─────────────────────────────────────────┐ │ │ │ │ │ Application Business │ │ │ │ │ │ ┌───────────────────────────────────┐ │ │ │ │ │ │ │ Enterprise Business Rules │ │ │ │ │ │ │ │ ┌─────────────────────────────┐ │ │ │ │ │ │ │ │ │ Entities │ │ │ │ │ │ │ │ │ └─────────────────────────────┘ │ │ │ │ │ │ │ │ Use Cases │ │ │ │ │ │ │ └───────────────────────────────────┘ │ │ │ │ │ │ Controllers, Presenters, Gateways │ │ │ │ │ └─────────────────────────────────────────┘ │ │ │ │ DB, Web, UI, External Services │ │ │ └───────────────────────────────────────────────┘ │ │ 의존성 방향: 바깥 → 안쪽 │ └─────────────────────────────────────────────────────┘
CQRS 패턴
┌───────────────────────────────────┐
│ Command │
│ ┌─────────┐ ┌─────────────┐ │
명령 ───▶│ │ Command │───▶│ Write DB │ │
(CUD) │ │ Handler │ │ (정규화) │ │
│ └─────────┘ └──────┬──────┘ │
└───────────────────────│───────────┘
│ 이벤트/동기화
┌───────────────────────│───────────┐
│ Query ▼ │
│ ┌─────────┐ ┌─────────────┐ │
조회 ───▶│ │ Query │◀───│ Read DB │ │
(R) │ │ Handler │ │ (비정규화) │ │
│ └─────────┘ └─────────────┘ │
└───────────────────────────────────┘이벤트 소싱
┌───────────────────────────────────────────────────┐
│ Event Store │
│ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │ E1 │→│ E2 │→│ E3 │→│ E4 │→│ E5 │→ ... │
│ │생성 │ │수정 │ │이동 │ │수정 │ │삭제 │ │
│ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ │
└──────────────────────┬────────────────────────────┘
│ Replay
▼
┌─────────────────┐
│ Current State │ (특정 시점 상태 복원)
│ (Aggregate) │
└─────────────────┘15. 운영체제
프로세스 상태 전이도
┌─────────────────────────────────┐
│ │
▼ │
┌──────────┐ dispatch ┌──────────┐ │
────▶│ Ready │───────────▶│ Running │──┤ 종료
생성 └────┬─────┘ └────┬─────┘ │
│ │ │
│ timeout │ I/O │
│ (선점) │ 요청 │
│ │ │
│ ┌────▼─────┐ │
│◀─────────────────│ Blocked │ │
I/O 완료 │(Waiting) │ │
└──────────┘ │
│
───▶ Terminated데드락 4조건
┌──────────────────────────────────────────────────┐ │ Deadlock 발생 조건 │ │ │ │ 1. 상호배제 2. 점유대기 │ │ ┌───┐ ┌───┐ ┌───┐ │ │ │ R │ ← 1개만 │ P │───▶│ R │ 보유하면서 │ │ └───┘ 사용 └───┘ └───┘ 다른 것 대기 │ │ │ │ 3. 비선점 4. 순환대기 │ │ ┌───┐ P1──▶R1──▶P2 │ │ │ P │ 강제회수 ▲ │ │ │ └───┘ 불가 │ ▼ │ │ P4◀──R4◀──P3 │ └──────────────────────────────────────────────────┘ 해결: 예방, 회피(Banker's), 탐지, 복구
메모리 계층 구조
┌─────┐
│ Reg │ ← 가장 빠름, 가장 작음
└──┬──┘
│
┌──▼──┐
│ L1 │ Cache (KB)
│Cache│
└──┬──┘
│
┌──▼──┐
│ L2 │ Cache (MB)
│Cache│
└──┬──┘
│
┌──▼──┐
│ L3 │ Cache (수십 MB)
│Cache│
└──┬──┘
│
┌─────▼─────┐
│ RAM │ 주기억장치 (GB)
└─────┬─────┘
│
┌─────────▼─────────┐
│ SSD / HDD │ 보조기억장치 (TB)
└───────────────────┘
가장 느림, 가장 큼16. 데이터 모델링
ER 다이어그램 표기법
Chen 표기법:
┌─────────┐ ┌───────────┐ ┌─────────┐
│ Student │──────◇ 수강 ◇──────│ Course │
└─────────┘ N └───────────┘ M └─────────┘
│ │
│ │
┌─┴─┐ ┌───┴───┐
│ID │ │코드 │
└───┘ └───────┘
Crow's Foot:
┌──────────┐ ┌──────────┐
│ Customer │──────○<─│ Order │
└──────────┘ 1 * └──────────┘
기호: ○─ 1:1 ─< 1:N >< M:N정규화 과정
┌─────────────────────────────────────┐
│ 비정규형 (Unnormalized) │
│ 주문번호, 고객명, {상품명, 수량} │
└───────────────┬─────────────────────┘
│ 반복 그룹 제거
▼
┌─────────────────────────────────────┐
│ 1NF (원자값) │
│ 주문번호, 고객명, 상품명, 수량 │
└───────────────┬─────────────────────┘
│ 부분 함수 종속 제거
▼
┌─────────────────────────────────────┐
│ 2NF (완전 함수 종속) │
│ 주문(주문번호, 고객명) │
│ 주문상세(주문번호, 상품명, 수량) │
└───────────────┬─────────────────────┘
│ 이행 함수 종속 제거
▼
┌─────────────────────────────────────┐
│ 3NF (이행 종속 X) │
│ 주문(주문번호, 고객ID) │
│ 고객(고객ID, 고객명) │
│ 주문상세(주문번호, 상품명, 수량) │
└─────────────────────────────────────┘17. AI/ML 심화
GAN (Generative Adversarial Network)
┌─────────────────────────────────────────────────────┐ │ GAN │ │ │ │ ┌─────────┐ ┌─────────────┐ │ │ │ Noise │ │ Real │ │ │ │ (z) │ │ Data │ │ │ └────┬────┘ └──────┬──────┘ │ │ │ │ │ │ ▼ │ │ │ ┌─────────────┐ │ │ │ │ Generator │ │ │ │ │ (G) │ │ │ │ └──────┬──────┘ │ │ │ │ │ │ │ │ Fake │ Real │ │ │ │ │ │ └───────────┬───────────────────┘ │ │ ▼ │ │ ┌─────────────┐ │ │ │Discriminator│ │ │ │ (D) │ │ │ └──────┬──────┘ │ │ │ │ │ ▼ │ │ Real or Fake? │ │ │ │ G 목표: D를 속이기 / D 목표: 진짜 구별하기 │ └─────────────────────────────────────────────────────┘
추천 시스템 아키텍처
┌─────────────────────────────────────────────────────┐ │ Recommendation System │ │ │ │ ┌─────────────────────────────────────────────┐ │ │ │ Data Collection │ │ │ │ (클릭, 구매, 평점, 조회시간, 검색어) │ │ │ └────────────────────┬────────────────────────┘ │ │ │ │ │ ┌────────────┼────────────┐ │ │ ▼ ▼ ▼ │ │ ┌────────────┐ ┌────────────┐ ┌────────────┐ │ │ │ 협업 필터링 │ │콘텐츠 기반 │ │ 딥러닝 │ │ │ │ (CF) │ │ (CB) │ │ (DNN) │ │ │ └─────┬──────┘ └─────┬──────┘ └─────┬──────┘ │ │ │ │ │ │ │ └──────────────┼──────────────┘ │ │ ▼ │ │ ┌─────────────────┐ │ │ │ Ensemble │ │ │ │ (앙상블) │ │ │ └────────┬────────┘ │ │ │ │ │ ▼ │ │ ┌─────────────────┐ │ │ │ Re-Ranking │ │ │ │ (비즈니스 규칙) │ │ │ └────────┬────────┘ │ │ │ │ │ ▼ │ │ [ 추천 결과 노출 ] │ └─────────────────────────────────────────────────────┘
Confusion Matrix
예측값
┌─────────┬─────────┐
│ Positive│ Negative│
┌─────────┼─────────┼─────────┤
실 │Positive │ TP │ FN │ ← Recall = TP/(TP+FN)
제 │ │ (정탐) │ (미탐) │
값 ├─────────┼─────────┼─────────┤
│Negative │ FP │ TN │
│ │ (오탐) │ (정확) │
└─────────┴─────────┴─────────┘
↑
Precision = TP/(TP+FP)
Accuracy = (TP+TN) / (TP+TN+FP+FN)
F1 Score = 2×P×R / (P+R)18. 회복성 패턴
Circuit Breaker 상태도
┌─────────────────────┐
│ │
성공 임계치 │ │ 타임아웃 후
초과 │ │ 요청 허용
▼ │
┌──────────┐ 실패 임계치 ┌──────────┐ │
│ CLOSED │───────────────▶│ OPEN │──┤
│ (정상) │ 초과 │ (차단) │ │
└────┬─────┘ └────┬─────┘ │
│ │ │
│ │ │
│ ┌─────▼─────┐ │
│ │ HALF-OPEN │──┘
│ │ (테스트) │
│ └─────┬─────┘
│ │
│◀─────────────────────────┘
테스트 성공
장애 전파 차단, 빠른 실패, 자동 복구Retry with Exponential Backoff
┌────────┐
│ 요청 1 │ ─────▶ 실패
└────────┘
│ 1초 대기
▼
┌────────┐
│ 요청 2 │ ─────▶ 실패
└────────┘
│ 2초 대기 (×2)
▼
┌────────┐
│ 요청 3 │ ─────▶ 실패
└────────┘
│ 4초 대기 (×2)
▼
┌────────┐
│ 요청 4 │ ─────▶ 성공! ✓
└────────┘
+ Jitter (랜덤 지연) 추가로 동시 재시도 방지Rate Limiting: Token Bucket
┌──────────────────────────────────────┐ │ Token Bucket │ │ │ │ ┌──────────────────────────────┐ │ │ │ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ │ │ ← 최대 용량 │ │ (토큰) │ │ │ └──────────────┬───────────────┘ │ │ │ │ │ 일정 속도로 │ 요청마다 │ │ 토큰 추가 │ 토큰 소비 │ │ (refill) ▼ │ │ ┌───────┐ │ │ Request ──▶│ Gate │──▶ 처리 │ │ (토큰 있음) └───────┘ │ │ │ │ Request ──▶ [토큰 없음] ──▶ 거부 │ └──────────────────────────────────────┘ 버스트 트래픽 허용 + 평균 속도 제한
19. 인증 프로토콜 흐름
OAuth 2.0 vs SAML 흐름 비교
OAuth 2.0 (API 인가):
┌────────┐ 1.인가요청 ┌──────────┐
│ User │─────────────▶│ Auth │
│ │◀─────────────│ Server │
└────┬───┘ 2.인가코드 └────┬─────┘
│ │
│ 3.코드전달 │
▼ │
┌────────┐ 4.토큰교환 ──────┘
│ Client │◀───────────────────
│ App │ 5.Access Token
└────┬───┘
│ 6.API 호출 (토큰)
▼
┌────────────┐
│ Resource │
│ Server │
└────────────┘
SAML 2.0 (SSO 인증):
┌────────┐ 1.서비스접근 ┌────────┐
│ User │──────────────▶│ SP │
│ │ │(Service│
└────┬───┘ │Provider)│
│ └────┬───┘
│ 2.IdP로 리다이렉트 │
▼ │
┌──────────┐ │
│ IdP │ 3.SAML Assertion│
│(Identity │──────────────────┘
│ Provider)│ (XML, 서명됨)
└──────────┘20. 빠른 그리기 팁
기본 도형 활용
□ 사각형: 시스템/컴포넌트 ○ 원: 프로세스/상태 ◇ 마름모: 분기/결정 → 화살표: 흐름/관계 ─ 점선: 옵션/참조
번호 매기기
① ② ③ 또는 1. 2. 3. 으로 순서 표시
영역 구분
┌──────────────────┐ │ 외부 영역 │ │ ┌────────────┐ │ │ │ 내부 영역 │ │ │ └────────────┘ │ └──────────────────┘
21. Saga 패턴 (분산 트랜잭션)
Choreography (이벤트 기반)
┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐
│ Order │───▶│ Payment │───▶│ Inventory│───▶│ Shipping │
│ Service │ │ Service │ │ Service │ │ Service │
└────┬─────┘ └────┬─────┘ └────┬─────┘ └──────────┘
│ │ │
│ 이벤트 발행 │ 이벤트 발행 │ 이벤트 발행
▼ ▼ ▼
┌─────────────────────────────────────────────────────────┐
│ Message Broker (Kafka/RabbitMQ) │
└─────────────────────────────────────────────────────────┘
실패 시 보상 트랜잭션:
Shipping 실패 → Inventory 롤백 → Payment 환불 → Order 취소Orchestration (오케스트레이터 기반)
┌─────────────────┐
│ Saga 오케스트레이터 │
│ (Coordinator) │
└────────┬────────┘
┌─────────┬───────┼───────┬─────────┐
▼ ▼ ▼ ▼ ▼
┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐
│ Order │ │Payment │ │Inventory│ │Shipping│
│Service │ │Service │ │Service │ │Service │
└────────┘ └────────┘ └────────┘ └────────┘
흐름: 오케스트레이터가 각 서비스를 순차/병렬 호출
실패 시: 오케스트레이터가 보상 트랜잭션 순서 결정Choreography vs Orchestration 비교
Choreography Orchestration ┌────────────────────┐ ┌────────────────────┐ │ 분산 제어 │ │ 중앙 집중 제어 │ │ 결합도 낮음 │ │ 결합도 높음 │ │ 추적 어려움 │ │ 추적 용이 │ │ 확장성 좋음 │ │ 오케스트레이터 SPOF │ │ 순환 의존 주의 │ │ 워크플로우 명확 │ └────────────────────┘ └────────────────────┘
22. API 버전 관리 전략
URL 버전 방식
/api/v1/users ─┐ /api/v2/users ─┼─ URL Path에 버전 명시 /api/v3/users ─┘ 장점: 명확, 캐싱 용이 단점: URL 변경, 클라이언트 수정 필요
헤더 버전 방식
GET /api/users Headers: Accept: application/vnd.api+json;version=2 또는 X-API-Version: 2 장점: URL 깔끔, RESTful 단점: 테스트 어려움, 가시성 낮음
API 버전 관리 흐름
┌──────────────────────────────────────────────────────────┐
│ API Gateway │
│ ┌─────────────────────────────────────────────────┐ │
│ │ Route: /api/v1/* → v1-service │ │
│ │ Route: /api/v2/* → v2-service │ │
│ │ Default: /api/* → latest-service │ │
│ └─────────────────────────────────────────────────┘ │
└──────────────────────────────────────────────────────────┘
│ │ │
▼ ▼ ▼
┌──────────┐ ┌──────────┐ ┌──────────┐
│ v1 서비스 │ │ v2 서비스 │ │ v3 서비스 │
│ (레거시) │ │ (현재) │ │ (최신) │
└──────────┘ └──────────┘ └──────────┘
Deprecation 정책:
v1: Deprecated (6개월 후 종료)
v2: Current (권장)
v3: Latest (얼리 어답터용)23. 배포 전략
Blue-Green 배포
┌─────────────────────┐
│ Load Balancer │
└──────────┬──────────┘
│
┌────────────────┴────────────────┐
│ │
┌─────▼─────┐ ┌─────▼─────┐
│ Blue │ 트래픽 전환 │ Green │
│ (v1.0.0) │ ◀═══════════════▶ │ (v2.0.0) │
│ 현재 운영 │ │ 새 버전 │
└───────────┘ └───────────┘
1단계: Green 환경에 새 버전 배포
2단계: 테스트 완료 후 LB 전환 (Blue → Green)
3단계: Blue는 롤백 대비용으로 유지
장점: 즉시 롤백 가능, 다운타임 없음
단점: 2배 인프라 비용Canary 배포
┌─────────────────────┐
│ Load Balancer │
│ (트래픽 가중치) │
└──────────┬──────────┘
│
┌─────────────────┼─────────────────┐
│ 90% │ │ 10%
┌─────▼─────┐ ┌─────▼─────┐
│ Stable │ │ Canary │
│ (v1.0.0) │ │ (v2.0.0) │
│ 대부분 │ │ 일부 사용자│
└───────────┘ └───────────┘
단계별 트래픽 증가:
10% → 25% → 50% → 75% → 100%
모니터링 지표: 에러율, 지연시간, 비즈니스 메트릭
문제 발생 시: 즉시 0%로 롤백Rolling 배포
시간 →
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
│v1 │v1 │v1 │v1 │ → │v2 │v1 │v1 │v1 │ → │v2 │v2 │v1 │v1 │
└───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘
│ │
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
→ │v2 │v2 │v2 │v1 │ → │v2 │v2 │v2 │v2 │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
K8s 설정 예시:
maxSurge: 1 (최대 추가 Pod)
maxUnavailable: 0 (최소 가용 Pod)
장점: 점진적, 리소스 효율적
단점: 롤백 시간 소요, 버전 공존A/B Testing vs Canary vs Feature Flag
┌────────────────────────────────────────────────────────┐ │ 비교 │ ├──────────────┬──────────────┬──────────────┬──────────┤ │ │ A/B Test │ Canary │Feature Flag│ ├──────────────┼──────────────┼──────────────┼──────────┤ │ 목적 │ 기능 비교 │ 안전한 배포 │ 기능 제어 │ │ 대상 선정 │ 사용자 속성 │ 랜덤 % │ 조건 기반 │ │ 측정 │ 비즈니스 지표 │ 시스템 안정성 │ 다양 │ │ 기간 │ 실험 종료까지 │ 배포 완료까지 │ 상시 │ └──────────────┴──────────────┴──────────────┴──────────┘
24. Kubernetes Pod 라이프사이클
Pod 상태 다이어그램
┌─────────┐
│ Pending │ ← 스케줄링 대기, 이미지 Pull
└────┬────┘
│ 스케줄링 완료
▼
┌─────────┐
┌────│ Running │────┐
│ └────┬────┘ │
│ │ │
정상 종료 │ 에러 발생
│ │ │
▼ ▼ ▼
┌───────────┐ ┌─────────┐ ┌──────┐
│ Succeeded │ │ Unknown │ │Failed│
│ (완료) │ │(통신불가)│ │(실패)│
└───────────┘ └─────────┘ └──────┘컨테이너 생명주기 훅
┌──────────────────────────────────────────────────────────┐ │ Pod 시작 │ ├──────────────────────────────────────────────────────────┤ │ 1. Init Container 실행 (순차적) │ │ ┌──────┐ → ┌──────┐ → ┌──────┐ │ │ │init-1│ │init-2│ │init-3│ │ │ └──────┘ └──────┘ └──────┘ │ ├──────────────────────────────────────────────────────────┤ │ 2. Main Container 시작 │ │ ┌─────────────────────────────────────────────────┐ │ │ │ postStart Hook → Main Process → preStop Hook │ │ │ │ │ │ │ │ │ │ ▼ ▼ │ │ │ │ ┌─────────┐ ┌─────────┐ │ │ │ │ │Readiness│ ← 주기적 체크 → │Liveness │ │ │ │ │ │ Probe │ │ Probe │ │ │ │ │ └─────────┘ └─────────┘ │ │ │ └─────────────────────────────────────────────────┘ │ └──────────────────────────────────────────────────────────┘ Probe 종류: - Liveness: 실패 시 컨테이너 재시작 - Readiness: 실패 시 서비스에서 제외 - Startup: 시작 시간이 긴 앱용 (초기 체크)
Pod 종료 시퀀스
┌─────────────────────────────────────────────────────────┐
│ kubectl delete pod / HPA scale-down / 노드 drain │
└────────────────────────┬────────────────────────────────┘
▼
┌──────────────────────┐
│ Pod Terminating 상태 │
└──────────┬───────────┘
│
┌────────────────────┼────────────────────┐
│ │ │
▼ ▼ ▼
┌─────────┐ ┌────────────┐ ┌─────────────┐
│Endpoint │ │ preStop │ │ SIGTERM │
│ 제거 │ │ Hook 실행 │ │ 전송 │
└─────────┘ └────────────┘ └──────┬──────┘
│
terminationGracePeriod
(기본 30초)
│
▼
┌─────────────┐
│ SIGKILL │
│ (강제 종료) │
└─────────────┘25. CI/CD 파이프라인 흐름
기본 CI/CD 파이프라인
┌────────────────────────────────────────────────────────────────┐
│ CI (Continuous Integration) │
├────────────────────────────────────────────────────────────────┤
│ │
│ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────────┐ │
│ │ Push │──▶│Build │──▶│ Test │──▶│ Lint │──▶│ Security │ │
│ │ │ │ │ │ │ │ │ │ Scan │ │
│ └──────┘ └──────┘ └──────┘ └──────┘ └────┬─────┘ │
│ │ │
└────────────────────────────────────────────────────│──────────┘
│
┌────────────────────────────────────────────────────│──────────┐
│ CD (Continuous Delivery) │ │
├────────────────────────────────────────────────────▼──────────┤
│ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ Image │──▶│ Deploy │──▶│ Deploy │──▶│ Deploy │ │
│ │ Build │ │ (Dev) │ │ (Stage) │ │ (Prod) │ │
│ └──────────┘ └──────────┘ └────┬─────┘ └──────────┘ │
│ │ │
│ 수동 승인 │
│ │
└───────────────────────────────────────────────────────────────┘GitOps 파이프라인
┌───────────────────────────────────────────────────────────────┐
│ Application Repo │
│ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────────────────┐ │
│ │ Code │──▶│Build │──▶│ Test │──▶│ Image Push to │ │
│ │ Push │ │ │ │ │ │ Container Registry│ │
│ └──────┘ └──────┘ └──────┘ └────────┬─────────┘ │
└─────────────────────────────────────────────│─────────────────┘
│
▼ 이미지 태그 업데이트
┌───────────────────────────────────────────────────────────────┐
│ GitOps Config Repo │
│ ┌────────────────┐ ┌──────────────┐ │
│ │ k8s manifests │◀──── PR/Commit ───│ Image Tag │ │
│ │ (values.yaml) │ │ Update │ │
│ └───────┬────────┘ └──────────────┘ │
└───────────│───────────────────────────────────────────────────┘
│
▼ Sync
┌───────────────────────────────────────────────────────────────┐
│ ArgoCD / Flux │
│ ┌──────────────────────────────────────────────────────┐ │
│ │ Git Repo ◀────Compare────▶ K8s Cluster │ │
│ │ │ │ │ │
│ │ └─────── Sync if Diff ────────┘ │ │
│ └──────────────────────────────────────────────────────┘ │
└───────────────────────────────────────────────────────────────┘
특징:
- Pull 기반 배포 (클러스터가 Git 감시)
- 단일 진실 공급원 (Single Source of Truth)
- 선언적 인프라 관리브랜치 전략과 환경 매핑
┌─────────────┬─────────────┬─────────────┐
│ Branch │ 환경 │ 자동화 │
├─────────────┼─────────────┼─────────────┤
│ feature/* │ - │ CI only │
│ develop │ Dev │ CI + CD │
│ release/* │ Stage │ CI + CD │
│ main │ Prod │ CI + 승인 + CD│
│ hotfix/* │ Prod │ 긴급 배포 │
└─────────────┴─────────────┴─────────────┘
Git Flow 예시:
feature/login → develop → release/1.0 → main
↓ ↓ ↓
Dev Stage Prod부록: 자주 쓰는 약어 범례
| 약어 | 의미 |
|---|---|
| LB | Load Balancer |
| FW | Firewall |
| WAS | Web Application Server |
| DB | Database |
| MQ | Message Queue |
| GW | Gateway |
| Svc | Service |
| Req/Res | Request/Response |
| Auth | Authentication |
| K8s | Kubernetes |
| HPA | Horizontal Pod Autoscaler |
| CRD | Custom Resource Definition |
| CR | Container Registry |