[DAY34] Test Recap(6) : Templates and Complexity

[Day 45] Understanding Templates and Complexity
오늘은 C++의 템플릿과 알고리즘의 시간/공간 복잡도에 대해 복습했다. 템플릿이 단순히 코드를 재사용하는 편리한 도구라고만 생각했는데, 컴파일 타임에 코드를 생성하는 원리 때문에 발생하는 장단점을 제대로 모르고 있었다는 걸 깨달았다. 😵 특히 템플릿의 단점을 런타임 성능 저하라고 착각했던 것이 가장 큰 실수였다. 또한 재귀 함수의 시간 복잡도를 계산하는 방법이 아직 익숙하지 않다는 것도 알게 되었다. 기본 개념을 안다고 자만하지 말고, 그 동작 원리와 트레이드오프를 정확히 파악해야겠다.

---

📌 목표

• C++ 템플릿의 진짜 장단점 구분하기
• 템플릿 메타 프로그래밍이 컴파일 타임 기술임을 이해하기
• 재귀 함수의 시간 복잡도 분석 방법 익히기
• 스택 메모리의 주된 사용 예시 파악하기

---

📖 이론

1. C++ 템플릿의 특징

템플릿은 함수나 클래스를 특정 자료형에 얽매이지 않게 만드는 '코드 생성 틀'이다. 컴파일러는 이 틀을 사용해 컴파일 타임에 실제 타입에 맞는 코드(예: int용, double용)를 각각 생성한다.

• 장점:

  • 런타임 성능: 컴파일 시점에 이미 타입이 결정된 코드가 생성되므로, 런타임에 타입을 확인하는 등의 추가 비용(오버헤드)이 없다. 일반 함수/클래스와 성능이 동일하다.
  • 타입 안정성: 컴파일러가 타입 검사를 수행하므로 안전하다.

• 단점:

  • 컴파일 시간 증가: 템플릿을 사용하는 타입의 개수만큼 코드를 생성해야 하므로 컴파일 시간이 길어진다.
  • 코드 크기 증가 (Code Bloat): 생성된 코드들이 실행 파일에 모두 포함되어 파일 크기가 커질 수 있다.

• 템플릿 메타 프로그래밍 (TMP): 템플릿을 이용해 컴파일 타임에 계산을 수행하는 C++의 고급 기법이다. 런타임에 실행되어야 할 연산을 컴파일러가 미리 계산해두는 방식이므로, 런타임 성능을 향상시키는 데 사용된다.

2. 재귀 함수의 시간 복잡도

재귀 함수의 시간 복잡도는 재귀 호출 트리를 그려 전체 연산의 개수를 파악하는 방식으로 분석할 수 있다.

• 패턴 1: func(n-1)을 두 번 호출하는 경우
  • void func(int n) { if(n<=1) return; func(n-1); func(n-1); }
  • 하나의 함수가 자신보다 1 작은 함수 두 개를 호출한다. 트리의 깊이는 n이 되고, 노드의 총개수는 $O(2^n)$이 된다.
• 패턴 2: func(n/2)를 두 번 호출하는 경우
  • void func(int n) { if(n<=1) return; func(n/2); func(n/2); }
  • 하나의 함수가 크기가 절반인 함수 두 개를 호출한다. 트리의 깊이는 log n이 된다. 이 경우 전체 노드의 개수는 약 2n-1개이므로, 시간 복잡도는 $O(n)$이 된다. (분할 정복 알고리즘의 일반적인 패턴)

3. 스택 메모리의 역할

스택 메모리는 함수의 호출과 실행을 위해 사용되는 메모리 영역이다.

• 함수가 호출될 때마다 해당 함수의 매개변수, 지역 변수, 복귀 주소 등이 스택 프레임(Stack Frame)이라는 단위로 쌓인다.
• 함수 실행이 끝나면 해당 스택 프레임은 스택에서 제거된다.
• 따라서 재귀 함수가 매우 깊게 호출되면 스택 프레임이 계속 쌓이다가 할당된 스택 공간을 초과하는 스택 오버플로우(Stack Overflow)가 발생할 수 있다.

---

⚠️ 실수

• 템플릿의 단점을 런타임 성능 저하라고 생각했다.

  • (X) 템플릿은 런타임에 타입을 확인해야 해서 느리다.
  • (O) 템플릿은 컴파일 타임에 타입에 맞는 코드를 생성하므로 런타임 오버헤드가 거의 없다. 진짜 단점은 컴파일 시간 증가와 코드 크기 증가다.

• 재귀 함수의 시간 복잡도를 잘못 계산했다.

  • (X) func(n/2)를 두 번 호출하는 재귀는 분할되니 빠를 것이다.
  • (O) 재귀 트리를 그려서 전체 노드의 개수나 총 연산량을 분석해야 한다. 해당 패턴의 시간 복잡도는 $O(n)$이다.

• 스택 메모리의 대표적인 사용 예시를 헷갈렸다.

  • (X) C++에서 스택 메모리는 주로 정적 배열을 저장하는 데 사용된다.
  • (O) 스택 메모리는 함수 호출과 가장 밀접한 관련이 있다. 재귀 함수 호출이 깊어질 때 스택 오버플로우가 발생하는 것이 대표적인 예시다.

---

✅ 핵심 요약

개념	설명	비고
C++ 템플릿	컴파일 타임에 타입에 특화된 코드를 생성하는 기능.	제네릭 프로그래밍의 핵심. std::vector, std::sort 등
템플릿 메타 프로그래밍	컴파일 타임에 계산을 수행하여 런타임 성능을 최적화하는 기법.	런타임 기술이 아님.
시간 복잡도	입력 크기 n에 따라 연산 횟수가 어떻게 증가하는지를 나타내는 척도.	알고리즘의 효율성 측정.
공간 복잡도	입력 크기 n에 따라 메모리 사용량이 어떻게 증가하는지를 나타내는 척도.	특히 재귀 호출 시 스택 공간을 고려해야 함.
스택 메모리	함수 호출 시 지역 변수, 매개변수 등을 저장하는 메모리 공간.	재귀가 깊어지면 스택 오버플로우 발생 가능.