Foundations & Complexity

1. Overview

기초 및 복잡도(Foundations & Complexity, FC)는 우리가 짠 코드의 성능을 '내 컴퓨터에서 0.5초가 걸렸다'는 식의 주관적이고 환경 의존적인 느낌이 아니라, 입력 데이터의 크기 변화에 따른 자원(시간, 공간)의 수학적 확장성(Scalability)으로 엄밀하게 측정하는 표준 잣대를 다룹니다.

알고리즘의 세계에서 가장 중요한 언어는 빅오(Big-O) 표기법입니다. 학습자는 점근적 분석(Asymptotic Analysis)을 통해 알고리즘의 최악의 경우(Worst-case) 성능 한계를 규명하고, $O(1)$, $O(\log n)$, $O(n \log n)$ 등 주요 복잡도 클래스의 차이를 직관적으로 파악합니다. 나아가 이런 수학적 잣대를 배열(Array)과 연결 리스트(Linked List) 등 기초 자료 구조의 탐색, 삽입, 삭제 오버헤드에 적용해 보며, 연속된 메모리 배치와 참조 지역성(Locality)이 실제 하드웨어 성능에 미치는 물리적 영향력까지 종합적으로 학습합니다.

2. Scope & Boundaries

In-Scope

• 성능 측정과 복잡도 언어 (Complexity Theory): 빅오($O$), 빅오메가($\Omega$), 빅세타($\Theta$) 표기법의 수학적 정의, 시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity) 산출.
• 점근적 분석 기법 (Asymptotic Analysis): 최선(Best), 최악(Worst), 평균(Average) 케이스 분석 및 마스터 정리(Master Theorem)를 이용한 재귀식 풀이.
• 물리적 메모리 배치 (Memory Mechanics): 배열의 연속 할당(Contiguous Allocation)과 캐시 친화성(Cache Friendliness) vs 연결 리스트의 불연속 포인터 점프(Pointer Chasing).
• 기초 선형 자료구조 (Linear Foundations): 정적 배열, 동적 배열(Vector)의 크기 확장 역학, 단일/이중 연결 리스트 알고리즘.
• 분할 상환 분석 (Amortized Analysis): 동적 배열 확장과 같이 가끔 발생하는 무거운 연산 비용을 여러 연산에 걸쳐 평균적으로 분담하는 회계적 분석.

Out-of-Scope

• 고차원적인 알고리즘 설계 패러다임: 동적 계획법(DP), 탐욕법(Greedy), 백트래킹(Backtracking) 기법 설계 → 04-03 Algorithm Design 영역으로 위임.
• 고급 자료 구조 설계: 트리(Tree), 그래프(Graph), 해시 테이블(Hash Table)의 심화 로직 구현 → 04-02 Core Data Structures 및 이후 하위 노드로 위임.
• C++/Java 표준 라이브러리(STL) 맹신: std::vector나 ArrayList의 내부 소스코드 구조 자체를 외우는 행위 (언어론적 접근) → 05. Programming Languages 영역으로 위임.

Boundaries

• FC vs. Math: 이산 수학(01-01) 영역이 점화식을 풀고 귀납법을 '증명'하는 순수 논리에 초점을 맞춘다면, FC는 그 수학을 도구 삼아 '내 코드가 천만 개의 데이터를 처리할 때 서버가 터질 것인가'를 예측하는 실용적 '엔지니어링 잣대'에 초점을 맞춥니다.

3. Counterexample

• "이 코드는 이중 for 문이 있으니 무조건 $O(N^2)$이다"식의 맹목적 추종: 안쪽 루프가 1부터 $N$까지 도는 것이 아니라, $1, 2, 4, 8 \dots$ 식으로 두 배씩 점프한다면 전체 시간 복잡도는 $O(N \log N)$이 됩니다. 또한 루프 내부의 함수 호출(strlen() 등)이 숨겨진 $O(N)$을 발생시킬 때 이를 놓치고 $O(N)$이라 우기는 것은 치명적 오해입니다. 코드의 물리적 실행 횟수를 시그마($\Sigma$) 기호를 통해 정확히 합산하는 수리적 근거가 수반되어야 합니다.
• Big-O 표기법의 오용: "이 배열 탐색 알고리즘은 최악의 경우 $O(N)$이고, 최선의 경우 $O(1)$이다"라고 할 때, 기호의 의미를 혼동하여 "최선의 경우는 $\Omega(1)$이다"라고 말하는 식의 표기법 오류. (Big-O는 '상한선'을 뜻하는 함수 군(Family)이지 '최악의 경우' 그 자체와 동의어가 아닙니다.) 엄밀한 점근 표기법 사용 훈련이 필요합니다.

4. Prerequisites

• 이산 구조 및 모델링 (Recommended): 지수와 로그 연산, 등차/등비 수열의 합, 귀납법 등 고등학교 수준 이상의 이산 대수학 기초가 요구됩니다. (01-01. Discrete Structures)
• 디지털 논리 및 하드웨어 (Basic): 배열과 리스트의 성능을 논할 때 '참조 지역성(Spatial Locality)'과 '포인터'를 이해하기 위해 물리적 메모리 주소 개념이 선행되어야 합니다. (02-01. DLP)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 알고리즘 복잡도 언어와 점근적 분석 (Complexity & Notation)

• Why to Learn: CPU 클럭 속도나 언어(C vs Python)에 상관없이, 알고리즘 자체가 가진 순수한 '확장 능력'을 동료 엔지니어와 소통하기 위함입니다.
• What to Learn:
  • Concepts: 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity), 알고리즘의 확장성(Scalability).
  • Skills: 점근 표기법 $O$(빅오, Upper Bound), $\Omega$(빅오메가, Lower Bound), $\Theta$(빅세타, Tight Bound)의 수학적 한계 정의(예: $f(n) \le c \cdot g(n)$ for $n \ge n_0$).
  • Tools: 복잡도 그래프 시각화(Desmos 등).
  • Trade-offs: 완벽한 정확도를 위해 계수와 상수항($3N + 5$)을 모두 표기하는 수고 vs 입력 크기 $N$이 무한대로 갈 때 아무 의미 없어지는 최고차항($N$)만 남기는 '추상화' 간의 타협.
• How to Learn:
  • 1단계: $N$, $\log N$, $N \log N$, $N^2$, $2^N$, $N!$ 의 증가 속도 그래프를 그려보고, $N$이 1,000만 넘어가도 지수 시간($2^N$) 알고리즘은 우주의 수명이 다하도록 끝나지 않음을 수치적으로 체감합니다.
  • 2단계: 크기 $N$인 배열에서 짝수만 출력하는 코드의 시간 복잡도를 측정할 때, "할당 1번, 비교 N번, 출력 N/2번" 식의 카운팅에서 어떻게 상수를 버리고 최종적으로 $O(N)$으로 귀결되는지 증명합니다.
• Implement: 데이터 크기 $N$을 1만에서 10만까지 늘려가며 버블 정렬($O(N^2)$)과 $O(N)$ 스캔을 실행해, 실제 경과 시간(ms)이 $N$과 $N^2$ 곡선에 어떻게 피팅(Fitting)되는지 출력하는 벤치마크 코드.

Recommended

Core Topic 02: 분석 기법과 재귀 성능 측정 (Analysis Mechanics)

• Why to Learn: 복잡하게 얽힌 이중/삼중 루프나, 자기 자신을 여러 번 부르는 재귀 함수의 숨겨진 시한폭탄(병목)을 수학적으로 분해해 내기 위해서입니다.
• What to Learn:
  • Concepts: 최선(Best-case), 최악(Worst-case), 평균(Average-case) 케이스 분석.
  • Skills: 중첩 반복문의 시그마($\sum$) 기반 연산 횟수 도출, 재귀 트리를 이용한 스택 프레임 전개 및 깊이 산출.
  • Tools: 마스터 정리(Master Theorem) 적용.
  • Trade-offs: 모든 입력 확률이 동일하다고 가정한 순수 수학적 평균 케이스($\Theta$) vs 실제 프로덕션 환경에서 발생할 수 있는 악의적 데이터 배열(Worst Case)을 방어하기 위한 보수적 성능 평가의 괴리.
• How to Learn:
  • 1단계: for (i=0; i<N; i++) for (j=i; j<N; j++) 형태의 이중 루프가 실행되는 총 횟수가 등차수열의 합($N(N+1)/2$)임을 수식으로 풀고 $O(N^2)$임을 증명합니다.
  • 2단계: 분할 정복 알고리즘(예: 병합 정렬 $T(N) = 2T(N/2) + O(N)$)의 점화식을 세우고, 마스터 정리에 대입하여 단숨에 시간 복잡도 $O(N \log N)$을 도출하는 훈련을 합니다.
• Implement: 단순 피보나치 재귀 $O(2^N)$ 함수의 콜 트리(Call Tree) 노드 개수 증가를 시각화하여 로깅하는 코드.

Practical

Core Topic 03: 메모리 배치와 정적/동적 배열 (Memory Layout & Arrays)

• Why to Learn: Big-O 표기법 상으로는 똑같은 성능이라도, 실제 하드웨어 CPU 캐시가 데이터를 어떻게 읽어오느냐(공간 지역성)에 따라 실행 속도가 10배 이상 차이 나는 물리적 현실을 다루기 위함입니다.
• What to Learn:
  • Concepts: 배열의 연속 메모리 할당(Contiguous Allocation), 인덱스를 통한 $O(1)$ 무작위 접근(Random Access), 공간 지역성(Spatial Locality).
  • Skills: 동적 배열(Dynamic Array)의 두 배 크기 확장 로직(Doubling) 및 복사 비용 분석.
  • Tools: sizeof(), 캐시 미스 측정 툴(Valgrind Cachegrind).
  • Trade-offs: 배열 중간 삽입/삭제 시 발생하는 $O(N)$ 바이트 시프트(Shifting) 오버헤드 vs 메모리가 일렬로 늘어서 있어 CPU 캐시 라인(64 Byte)을 한 번에 가져와 탐색 속도가 극단적으로 빠른 $O(1)$ 조회 이점.
• How to Learn:
  • 1단계: 크기 고정 배열에 요소를 끼워 넣을 때 뒤의 원소들을 전부 밀어내는(Memmove) 비용이 왜 $O(N)$인지 그림으로 매핑합니다.
  • 2단계: 배열이 가득 차면 두 배 크기 배열을 만들고 모두 복사하는 동적 배열 확장에서, 가장 무거운 연산($O(N)$)이 가끔 일어나더라도 이를 요소 수 $N$으로 나누면 '분할 상환 복잡도(Amortized Complexity)' 기준 요소당 $O(1)$이 됨을 은행 잔고 비유(Accounting Method)로 증명합니다.
• Implement: 배열의 용량(Capacity)과 크기(Size)를 추적하며 꽉 찰 경우 2배로 Realloc하는 동적 배열(Vector) 클래스 구현.

Advanced

Core Topic 04: 포인터 기반 연결 리스트와 성능 트레이드오프 (Linked Lists & Physics)

• Why to Learn: 배열처럼 미리 큰 메모리 덩어리를 잡아두지 않고, 데이터가 필요할 때마다 동적으로 조각조각 메모리를 할당하여 유연한 중간 삽입/삭제를 달성하기 위해서입니다.
• What to Learn:
  • Concepts: 단일(Singly) / 이중(Doubly) / 원형(Circular) 연결 리스트.
  • Skills: 헤드(Head), 테일(Tail) 포인터 관리, 노드 중간 삽입/삭제 시의 링크 단절 방지 및 포인터 재연결(Wiring) 물리 로직.
  • Tools: 메모리 누수 검사기(AddressSanitizer, Valgrind).
  • Trade-offs: 특정 노드 주소를 이미 알 때 삽입/삭제 속도가 $O(1)$인 극강의 유연성 vs 해당 노드까지 찾아가기 위해 포인터를 타고 $O(N)$을 순차 탐색해야 하며, 캐시 지역성이 파괴되어 배열 대비 실제 조회 속도가 치명적으로 느린 약점.
• How to Learn:
  • 1단계: 연결 리스트 노드를 메모리 상 임의의 주소에 흩뿌리고(Heap 동적 할당), 각 노드가 다음 노드 주소를 들고 있는 다이어그램을 그리며, 왜 인덱스 접근이 불가능한지 파악합니다.
  • 2단계: 이중 연결 리스트에서 노드를 하나 삭제할 때, prev->next와 next->prev 포인터를 어떻게 교차 결합하는지 4단계 C 코드로 시뮬레이션합니다.
• Implement: 데이터 삽입, 삭제, 역순 정렬(Reverse) 메서드를 가지고 메모리 해제 로직까지 완벽한 커스텀 이중 연결 리스트 구조체/클래스 개발.

7. Terminology

8. References

Primary References

• [P1] CS2023 - AL/Basic Analysis — Foundations of complexity.
• [P4] DS-BoK - Data Fundamentals — Data structure mechanics for data science.

Secondary References

• [Introduction to Algorithms (CLRS)] Cormen et al. — The definitive authority on analysis.
• [Algorithms] Robert Sedgewick — Practical focus with visualization.

Industry References

• [Google Style Guide - Performance Section] — Practical complexity considerations.
• [ACM ICPC Training Materials] — Competitive analysis patterns.

9. Final Checklist

Primary Checklist

• 입력값 $N$이 커질 때 $O(log N)$과 $O(N)$의 성능 차이를 물리적 시간 관점에서 그래프로 설명 가능한가? (P1)
• 배열과 연결 리스트 중 특정 상황(빈번한 중간 삽입 vs 빈번한 조회)에 적합한 구조를 복잡도 기반으로 선택 가능한가? (P1, P4)

Secondary Checklist

• 마스터 정리를 사용하여 이진 탐색과 병합 정렬의 시간 복잡도를 명확히 유도할 수 있는가?
• '참조 지역성(Locality of Reference)'이 Big-O 등급이 같은 두 알고리즘의 실제 속도차를 어떻게 만드는지 이해하는가?

Industry Checklist

• 실무 라이브러리(Java ArrayList, Python List)의 확장 정책(Expansion Strategy)이 분할 상환 복잡도에 미치는 영향을 분석 가능한가? (SFIA)
• 대용량 데이터 처리 시 메모리 사용량 계산을 통해 시스템의 Out-of-Memory 상황을 예측할 수 있는가?