Data Structures & Algorithms

1. Overview

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

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

2. Scope & Boundaries

In-Scope

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

Out-of-Scope

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

Boundaries

• DSA는 **'인메모리(In-memory) 연산'**의 논리적 효율성 극대화에 집중하며, 이를 네트워크로 확장하거나 영구적으로 저장하는 시점부터는 시스템 아키텍처 및 데이터 관리 영역으로 경계가 넘어갑니다.

3. Counterexample

• 단순 코딩 테스트 기법 습득: 특정 유형의 문제를 푸는 패턴만 외우는 것은 DSA 학습이 아닙니다. 문제의 본질을 추상 그래프 모델로 변환하고, 하드웨어 특성(L1 캐시, 메모리 정렬)을 고려하여 상수항($c$) 수준의 성능 차이를 이해하는 것이 핵심입니다.
• 표준 라이브러리 사용에만 의존: std::sort를 호출하는 능력을 넘어, 데이터의 분포가 특수할 때(예: 이미 거의 정렬된 경우) 최적의 성능을 낼 수 있는 맞춤형 자료구조(예: Segment Tree)를 설계하거나 선택할 수 있어야 합니다.

4. Prerequisites

• 수학과 컴퓨팅 논리 (Basic): 점화식의 해를 구하고 정수론 기반의 해시 함수를 이해하기 위한 수리적 기반이 필수입니다. (P1)
• 컴퓨터 구조 (Recommended): 캐시 계층 구조(LRU)와 메모리 로컬리티(Spatial/Temporal Locality)가 실제 성능에 미치는 영향 이해. (P1)
• 기초 프로그래밍 역량 (Basic): 조건/반복문, 함수 호출 스택, 참조(Reference) 및 포인터 개념의 숙련도. (P1)

5. Learning Map

1. Foundations & Complexity: 시간/공간 복잡도 이론과 선형 구조의 물리적 배치를 이해합니다. (P1)
2. Core Data Structures: 비선형 계층 구조(Tree)와 평균 상수 시간 탐색을 보장하는 해싱(Hashing)을 익힙니다. (P1)
3. Design Techniques: 분할 정복, 탐욕법, DP를 통해 문제를 효율적인 부분 문제로 분해하고 정복하는 법을 배웁니다. (P1)
4. Advanced Optimization: 복잡한 관계망(Graph)과 고수준 패턴 매칭(String), 그리고 계산 한계(NP)를 정복합니다. (P1)

6. Learning Topics

Basic

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

• Why to Learn: 데이터 규모가 무한히 커질 때 알고리즘이 시스템 자원을 얼마나 소요할지 객관적으로 예측하여 붕괴하지 않는 설계를 하기 위함입니다.
• What to Learn:
  • Concepts: Big-O, Omega, Theta 표기법의 정의, 최악/평균/최선 케이스 분석, 분할 상환 분석(Amortized Analysis).
  • Skills: 코드 루프 분석을 통한 복잡도 수식 도출, 마스터 정리(Master Theorem)를 이용한 재귀식 풀이.
  • Tools: 복잡도 비교 차트(Cheat Sheet), 시각화 도구(VisuAlgo).
  • Trade-offs: 시간 복잡도를 줄이기 위한 공간 복잡도의 희생 (Space-Time Trade-off).
• How to Learn:
  • 1단계: 서로 다른 정렬 알고리즘의 실행 시간을 데이터 크기에 따라 측정하여 로그 스케일 그래프로 그려 봅니다.
  • 2단계: 동일한 기능을 하는 $O(N^2)$ 코드와 $O(N \log N)$ 코드의 처리 임계점을 실험을 통해 도출합니다.
• Implement: 특정 알고리즘의 복잡도를 수학적으로 유도하고 실험 데이터로 검증한 성능 분석 보고서.

Recommended

Core Topic 02: 비선형 자료구조와 계층적 탐색 (Non-linear Structures)

• Why to Learn: 단순 탐색으로 해결할 수 없는 수백만 건의 데이터 인덱싱과 우선순위 관리에서 대수적 수준($O(\log N)$)의 성능 보장을 하기 위함입니다.
• What to Learn:
  • Concepts: 해시 테이블(Chaining, Open Addressing), 자가 균형 이진 검색 트리(AVL, RB-Tree), 우선순위 큐와 힙(Heap).
  • Skills: 해시 충돌(Collision) 발생 시 성능 저하율 측정, 트리 순회(BFS/DFS) 및 구조 재조정 실습.
  • Tools: Graphviz (자료구조 시각화), HashMap 인터널 소스 코드 분석.
  • Trade-offs: 트리 구조의 엄밀한 균형 유지 비용 vs 검색 속도 향상분.
• How to Learn:
  • 1단계: 라이브러리를 쓰지 않고 직접 최소 힙(Min-heap)을 배열로 구현하여 힙 정렬을 수행합니다.
  • 2단계: 해시 함수의 균등 분포 특성을 분석하기 위해 실제 데이터의 버킷 점유도를 시각화해 봅니다.
• Implement: 자가 균형 트리 또는 정밀한 해시 맵 구현체 코드.

Practical

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

• Why to Learn: 지수 시간($O(2^n)$)이 걸리는 중복 문제의 해를 부분 문제의 저장(Memoization)을 통해 다항 시간 내에 해결하는 실무적 최적화의 정수입니다.
• What to Learn:
  • Concepts: 최적 부분 구조(Optimal Substructure), 중복 부분 문제, 메모이제이션(Top-down) vs 테이블화(Bottom-up), Knapsack 문제, LCS.
  • Skills: 재귀적 관계에서 점화식 도출하기, 공간 복잡도를 상수($O(1)$) 수준으로 낮추는 슬라이딩 윈도우 DP 기법.
  • Tools: 재귀 트리(Recursion Tree) 분석기.
  • Trade-offs: 재귀 호출의 스택 오버헤드 vs 반복문 테이블 관리 가독성.
• How to Learn:
  • 1단계: 피보나치 수열을 단순 재귀, 메모이제이션, 테이블화 방식으로 각각 구현하여 실행 속도를 비교합니다.
  • 2단계: 최단 경로 알고리즘(Floyd-Warshall)의 중간 노드 전이 과정을 테이블로 직접 추적합니다.
• Implement: 다차원 상태 공간을 가진 실제 비즈니스 최적화 알고리즘 프로토타입.

Advanced

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

• Why to Learn: 네트워크 용량 설계, 작업 스케줄링, 이미지 세분화 등 다차원적 공학 제약 조건을 한계점까지 해결하기 위함입니다.
• What to Learn:
  • Concepts: 강력 연결 요소(SCC: Tarjan), 위상 정렬(Topological Sort), 최대 유량/최소 컷(Ford-Fulkerson), 이분 매칭.
  • Skills: 현실 세계의 의존성 문제를 DAG로 모델링하고 순서 배정하기, 용량 제한 하의 유량 최대화 설계.
  • Tools: Graph modeling libraries, Flow simulation tools.
  • Trade-offs: 알고리즘의 이론적 최적성 vs 대규모 분산 그래프에서의 실제 구현 가능성.
• How to Learn:
  • 1단계: 오픈 소스 프로젝트의 패키지 의존성을 읽어 위상 정렬을 수행하고 순환 참조(Cycle)를 탐지합니다.
  • 2단계: 네트워크 유량 알고리즘을 사용하여 팀원-프로젝트 배정 문제를 최적으로 해결해 봅니다.
• Implement: 실시간 트래픽 환경 또는 배선 최적화 문제에 대한 고도화된 그래프 연산 엔진.

7. Terminology

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)을 극대화하기 위해 배열 기반의 캐시 친화적 설계를 수행했는가?