Data Structures & Algorithms

1. Overview

자료구조와 알고리즘(Data Structures & Algorithms, DSA)은 실세계의 복잡한 문제를 컴퓨터가 이해할 수 있는 정보 모델로 변환하고, 이를 가장 효율적으로 처리하기 위한 논리적 절차를 설계하는 분야입니다. 본 카테고리는 단순한 코드 구현을 넘어, 연산에 소요되는 시간적/공간적 자원의 한계를 점근적 분석(Big-O) 기반으로 예측하고, 최상의 성능을 이끌어내기 위한 설계 패러다임을 탐구합니다.

CS2023의 Algorithms and Complexity (AL) 및 Software Development Fundamentals (SDF) 영역을 근간으로 삼아, 데이터 모델링의 기초부터 고수준 최적화 기법까지 체계적으로 다룹니다.

DSA는 모든 소프트웨어 성능 최적화의 핵심 언어입니다. 데이터베이스 엔진의 B-Tree 인덱스, 검색 엔진의 역 인덱스(Inverted Index), 네비게이션 앱의 Dijkstra 경로 탐색, AI 모델의 행렬 연산 최적화까지 — DSA 없이 구현 가능한 고성능 시스템은 없습니다. MCL(01)이 수리적 이론을 정립한다면, DSA는 그 이론을 실행 가능한 코드 레벨의 효율로 연결하는 교두보입니다.

2. Scope & Boundaries

In-Scope

추상 자료형(ADT): 데이터의 논리적 명세와 물리적 저장 구조(Array, Linked List, Tree, Graph, Heap)의 매핑 및 트레이드오프.
알고리즘 설계 및 분석: 점근적 복잡도 분석(Big-O/Θ/Ω), 분할 정복, 탐욕법(Greedy), 동적 계획법(DP), 백트래킹.
검색 및 정렬: 효율적인 데이터 탐색 알고리즘과 정렬 기법의 최적성 증명 및 안정성(Stability) 분석.
고급 모델링: 문자열 인덱싱(Trie·Suffix Array), 확률적 자료구조(Bloom Filter·Skip List), 대규모 그래프 처리(SCC·Network Flow·Topological Sort).

Out-of-Scope

프로그래밍 언어의 딥다이브: 특정 언어의 가비지 컬렉션(GC)이나 런타임 최적화 → 05. PLC 노드로 위임.
영속적 라이브러리 및 트랜잭션: 디스크 기반 인덱싱 및 ACID 보장 원리 → 06. DIM 노드로 위임.
하드웨어 가속기 활용: GPU 커널 프로그래밍이나 FPGA 기반 알고리즘 가속 → 02. CAES 노드로 위임.
분산 데이터 처리 파이프라인: MapReduce, Spark 등 다중 노드 분산 연산 → 07. SADS 노드로 위임.

Boundaries

DSA는 **'인메모리(In-memory) 연산'**의 논리적 효율성 극대화에 집중하며, 이를 네트워크로 확장하거나 영구적으로 저장하는 시점부터는 시스템 아키텍처(07. SADS) 및 데이터 관리(06. DIM) 영역으로 경계가 넘어갑니다.
알고리즘 복잡도 분석의 수리적 증명(점화식, 마스터 정리 등)은 MCL(01)과 공유되지만, DSA는 항상 '특정 문제를 해결하는 코드' 관점에서 접근합니다.

3. Counterexample

단순 코딩 테스트 기법 습득: 특정 유형의 문제를 푸는 패턴만 외우는 것은 DSA 학습이 아닙니다. 문제의 본질을 추상 그래프 모델로 변환하고, 하드웨어 특성(L1 캐시 지역성, 메모리 정렬)을 고려하여 상수항( $c$ ) 수준의 성능 차이를 이해하는 것이 핵심입니다.
표준 라이브러리 사용에만 의존: std::sort를 호출하는 능력을 넘어, 데이터의 분포가 특수할 때(예: 거의 정렬된 데이터에는 Timsort, 정수 범위가 작으면 Counting Sort) 최적의 알고리즘을 선택할 수 있어야 합니다.
Big-O가 좋으면 항상 빠르다: $O(n \log n)$ 인 병합 정렬이 $O(n^2)$ 인 삽입 정렬보다 실제로 느린 경우가 있습니다. 데이터가 거의 정렬된 경우 삽입 정렬은 캐시 친화적이고 상수항이 작아 실측 성능이 우수합니다. 이론적 복잡도와 실제 성능은 캐시·분기 예측·메모리 접근 패턴에 따라 달라집니다.

4. Prerequisites

수학과 컴퓨팅 논리 (Basic): 점화식의 해(마스터 정리), 집합·관계·로그 연산 등 복잡도 분석을 위한 수리적 기반이 필수입니다. (P1)
기초 프로그래밍 역량 (Basic): 조건/반복문, 재귀 함수, 함수 호출 스택, 참조(Reference) 및 포인터 개념의 숙련도. (P1) Python, Java, C++ 중 하나로 자료구조를 직접 구현해 본 경험이 있어야 합니다.
컴퓨터 구조 (Recommended): 캐시 계층 구조(LRU)와 메모리 지역성(Spatial/Temporal Locality)이 실제 성능에 미치는 영향 이해. (P1) 이론적 복잡도와 실측 성능의 차이를 이해하는 데 필수입니다.

5. Learning Map

Sequence	Core Cluster	Objective & Description	Evidence (BoK)
1	Foundations & Complexity	점근적 복잡도 이론(Big-O)과 선형 구조의 특성을 이해하고, 시간/공간 트레이드오프(Space-Time Trade-off)를 고려한 성능 예측 모델을 구축합니다.	P1
2	Core Data Structures	대규모 데이터의 고속 탐색을 위한 비선형 트리(Tree) 구조와 평균 상수 시간( $O(1)$ ) 접근을 보장하는 해싱(Hashing) 기법을 물리적으로 설계합니다.	P1
3	Design Techniques	분할 정복(Divide & Conquer), 탐욕법(Greedy), 동적 계획법(DP)을 통해 지수 시간이 소요되는 중복 문제를 효율적인 다항 시간 내에 해결합니다.	P1
4	Advanced Optimization	네트워크 유량(Flow), 위상 정렬 등 복잡한 연결망(Graph)을 다루는 알고리즘을 최적화하고, 계산 복잡도(P vs NP)의 한계를 수리적으로 정복합니다.	P1

6. Learning Topics

Basic

Core Topic 01: 점근적 분석과 복잡도 이론 (Asymptotic Analysis & Big-O)

Why to Learn: 데이터 규모가 무한히 커질 때 알고리즘이 시스템 자원을 얼마나 소모할지 수리적으로 예측하여, 운영 단계에서 서비스가 붕괴하지 않는 구조를 설계하기 위함입니다.
What to Learn:
- Concepts: Big-O(상한), Big- $\Omega$ (하한), Big- $\Theta$ (평균/밀착 정답) 표기법, 최악·평균·최선 케이스 분석, 분할 상환 분석(Amortized Analysis).
- Skills: 중첩 루프 코드를 분석하여 수학적 다항식 도출, 마스터 정리(Master Theorem)를 이용한 재귀 함수 복잡도 계산.
- Tools: Big-O Cheat Sheet, Python timeit 모듈, 프로파일링 도구(cProfile).
- Trade-offs: 시간 복잡도를 줄이기 위해 메모리를 캐시로 사용하는 공간 복잡도 희생(Space-Time Trade-off) — 반대로 메모리가 극도로 제한된 임베디드에서는 연산 시간이 늘어나더라도 In-place 알고리즘을 선택합니다.
How to Learn:
- 1단계: 버블 정렬과 병합 정렬의 실행 시간을 데이터 크기( $N=10^2 \sim 10^6$ )에 따라 실측하고, 로그 스케일 그래프를 그려 이론적 $O(N^2)$ 과 $O(N \log N)$ 곡선과 비교합니다.
- 2단계: 동적 배열(예: C++ std::vector, Python list)의 원소 삽입 과정에서 발생하는 메모리 재할당 비용을 분할 상환 분석(Amortized $O(1)$ )으로 증명합니다.
Implement: 특정 알고리즘의 복잡도를 수학적으로 유도하고, 실측 데이터로 검증한 성능 분석 보고서.

Why to Learn: 배열이나 연결 리스트 같은 선형 탐색( $O(N)$ )으로는 해결할 수 없는 대규모 데이터의 인덱싱과 우선순위 관리를 대수적 시간( $O(\log N)$ ) 또는 상수 시간( $O(1)$ )으로 단축하기 위함입니다.
What to Learn:
- Concepts: 해시 테이블(Chaining, Open Addressing), 자가 균형 이진 검색 트리(AVL, Red-Black Tree), 우선순위 큐와 이진 힙(Binary Heap).
- Skills: 로드 팩터(Load Factor) 조절을 통한 해시 충돌(Collision) 방어, 트리 순회(In-order/Pre-order/Post-order) 및 회전(Rotation) 디버깅.
- Tools: Graphviz(자료구조 시각화), Java HashMap 인터널 소스 코드 분석.
- Trade-offs: 트리 기반( $O(\log N)$ )의 안정성과 범위 검색 지원 vs 해시 기반( $O(1)$ )의 극단적 단건 검색 속도 — 데이터의 순서 유지 필요 여부에 따라 선택이 갈립니다.
How to Learn:
- 1단계: 라이브러리를 쓰지 않고 직접 배열 기반의 최소 힙(Min-heap)을 구현하여, 원소 삽입·삭제 시의 Sift-up/Sift-down 과정을 시각화합니다.
- 2단계: 나쁜 해시 함수(모든 키가 같은 버킷으로 쏠림)를 의도적으로 작성하여 해시 테이블이 $O(N)$ 으로 퇴화하는 현상을 벤치마크합니다.
Implement: 배열 자동 확장과 충돌 해결 체이닝 기법이 적용된 정밀한 Hash Map 구현체.

Practical

Core Topic 03: 동적 계획법과 파라메트릭 최적화 (Dynamic Programming)

Why to Learn: 완전 탐색 시 지수 시간( $O(2^N)$ )이 걸리는 중복 부분 문제(Overlapping Subproblems)를 메모이제이션(Memoization)을 통해 다항 시간 내에 해결하는 실무적 최적화의 정수입니다.
What to Learn:
- Concepts: 최적 부분 구조(Optimal Substructure), 메모이제이션(Top-down) vs 테이블화(Bottom-up), 배낭 문제(Knapsack), 최장 공통 부분 수열(LCS).
- Skills: 주어진 문제의 점화식(Recurrence Relation) 유도, 상태 공간(State Space) 정의, 슬라이딩 윈도우 DP를 통한 공간 복잡도 최적화( $O(N) \rightarrow O(1)$ ).
- Tools: 재귀 트리(Recursion Tree) 시각화기, 메모리 프로파일러.
- Trade-offs: Top-down 방식의 재귀 호출 스택 오버헤드 vs Bottom-up 방식의 전체 테이블 계산 낭비(필요 없는 부분 문제까지 계산).
How to Learn:
- 1단계: 0-1 배낭 문제를 단순 재귀, Top-down, Bottom-up 세 가지 방식으로 구현하고 실행 시간을 비교합니다.
- 2단계: 최단 경로 알고리즘(Floyd-Warshall)의 중간 노드 전이 과정을 2차원 테이블의 변화로 직접 추적합니다.
Implement: 다차원 상태 공간을 정의하여 캐싱 메커니즘을 얹은 실제 비즈니스 로직(예: 재고 최적화 알고리즘) 프로토타입.

Advanced

Core Topic 04: 고급 그래프 모델링과 네트워크 흐름 (Advanced Graph & Flow)

Why to Learn: 도로망 탐색, 네트워크 대역폭 할당, 작업 스케줄링, 이미지 세분화 등 다차원적 공학 제약 조건을 한계점까지 해결하는 모델링 도구입니다.
What to Learn:
- Concepts: 강력 연결 요소(SCC: Tarjan/Kosaraju), 위상 정렬(Topological Sort), 최소 신장 트리(MST: Kruskal/Prim), 네트워크 유량(Network Flow: Ford-Fulkerson, Edmonds-Karp), 이분 매칭(Bipartite Matching).
- Skills: 현실 세계의 의존성 문제를 방향 비순환 그래프(DAG)로 모델링하기, 잔여 네트워크(Residual Network) 구축을 통한 유량 최대화 설계.
- Tools: networkx(Python), Neo4j(그래프 데이터베이스), 유량 시뮬레이션 시각화.
- Trade-offs: DFS/BFS 기반 알고리즘의 얕은 구현 난이도 vs 복잡도 최적화를 위한 고급 자료구조(Fibonacci Heap 등) 결합에 따른 유지보수 난이도.
How to Learn:
- 1단계: 패키지 관리자의 의존성 목록을 파싱하여 위상 정렬을 수행하고, 순환 참조(Cycle)를 탐지하는 코드를 작성합니다.
- 2단계: 네트워크 유량(Flow) 알고리즘을 사용하여 N명의 인원을 M개의 프로젝트에 제약 조건에 맞게 배정(이분 매칭)하는 문제를 최적으로 해결합니다.
Implement: 실시간 트래픽 환경 또는 배선 최적화 문제에 대한 고도화된 방향 그래프(DAG) 연산 엔진.

7. Terminology

Term (EN / ko, abbr)	1문장 정의	단계(기본/권장/실무/심화)	역할/맥락	관련 개념	유사/대비/함께 사용	오해 포인트	Evidence(Primary/Secondary/Industry)	Flags(core)
Big-O Notation, 빅오 표기법	알고리즘의 실행 시간이 입력 크기에 따라 증가하는 상한선을 수치화한 것입니다.	기본	성능 측정	Complexity	vs. Omega, Theta	정확한 실행 시간을 초 단위로 나타내는 것으로 혼동	Primary	core
Abstract Data Type (ADT)	데이터의 논리적 명세만을 정의하고 물리적 세부 구현은 감춘 상태입니다.	기본	설계 모델	Interface	stack, queue	실제 코드 클래스와 완전히 동일하게 오인함	Primary	core
Space-Time Trade-off	메모리 자원을 더 사용하여 처리 속도를 높이거나 그 반대의 결정을 내리는 설계 원칙입니다.	실무	최적화	Memoization	vs. Brute-force	언제나 속도가 빠른 것이 최선이라는 편견에 주의	Industry Practice	core
Amortized Analysis, 분할 상환 분석	최악의 연산 비용이 매우 드문 경우, 연산 시퀀스의 전체 평균 비용을 계산하는 방식입니다.	심화	정밀 분석	Dynamic Array	vs. Average Case	단순한 확률적 기대값이나 평균 케이스와 같은 개념으로 오인	Primary	core

8. References

Primary References

[P1] CS2023: AL — Algorithms and Complexity.
[P1] CS2023: SDF — Software Development Fundamentals Basics.
[P5] SFIA v9: Data Engineering — 데이터 처리 알고리즘 및 구조 설계 역량.

Secondary References

[CLRS] Introduction to Algorithms — Cormen, Leiserson, Rivest, Stein (자료구조 알고리즘의 표준).
[Sedgewick] Algorithms — Robert Sedgewick, Kevin Wayne (시각적 설명과 자바 기반의 실무 예제).

Industry References

[Google Engineering] Searching and Sorting — 구글 엔지니어링에서 사용하는 데이터 처리 성능 최적화 사례.
[AWS Builders' Library] Reliability and Algorithms — 분산 환경에서의 알고리즘 선택 트레이드오프.

9. Final Checklist

Primary Checklist

주어진 문제 상황을 Graph나 Tree와 같은 논리적 ADT 모델로 정확히 매핑할 수 있는가? (P1-SDF)
특정 알고리즘 선택 시, 데이터 규모( $n$ ) 증가에 따른 리소스 상한선(Boundary)을 수식으로 증명 가능한가? (P1-AL)

Secondary Checklist

정렬 알고리즘의 안정성(Stability)과 메모리 절약(In-place) 특성을 비즈니스 요구사항에 맞춰 선택할 수 있는가?
해시 테이블 사용 시 내부의 충돌 방지 전략(Open Addressing vs Chaining)에 따른 최악의 성능 케이스를 인지하고 있는가?

Industry Checklist

대용량 실시간 트래픽 환경( $10^5$ tps 이상)에서 지연 시간 한계를 보장하기 위한 알고리즘을 제안했는가?
프로세서의 캐시 정렬(L1 Cache alignment)을 극대화하기 위해 배열 기반의 캐시 친화적 설계를 수행했는가?