24.09.20 C++, CS

C++

템플릿

• C++ 템플릿(template)은 코드를 일반화하여 여러 데이터 타입에 대해 동작하는 함수를 작성할 수 있게 해주는 강력한 기능이다. 이를 통해 코드 재사용성을 높이고, 동일한 로직을 여러 타입에 대해 사용할 수 있다.
• 템플릿은 주로 함수 템플릿과 클래스 템플릿으로 나뉘며, 이 두 가지를 사용해 다양한 데이터 타입에 대해 유연하게 프로그래밍할 수 있다.

1. 템플릿의 기본 개념

• 템플릿은 코드를 작성할 때 구체적인 데이터 타입을 지정하지 않고, 타입을 매개변수화하여 나중에 구체적인 데이터 타입이 주어졌을 때 그에 맞는 코드를 생성하는 방식이다.

2. 함수 템플릿

• 함수 템플릿은 함수에 대해 데이터 타입을 일반화할 수 있게 한다. 예를 들어, 두 개의 값을 비교하여 더 큰 값을 반환하는 함수를 생각해보자. int, float, double 등 여러 타입의 데이터를 처리할 수 있게 하고 싶을 때, 함수 템플릿을 사용하면 이를 간단하게 구현할 수 있다.
• 함수 템플릿의 장점
  • 동일한 로직을 여러 타입에 대해 사용할 수 있어, 중복 코드를 줄일 수 있다.
  • 타입 안정성을 보장한다. 컴파일러는 템플릿 코드에서 타입 불일치가 발생할 경우 이를 잡아낸다.

3. 클래스 템플릿

• 클래스 템플릿은 클래스에 대해 데이터 타입을 일반화할 수 있게 해준다. 예를 들어, 다양한 데이터 타입을 저장하는 일반화된 자료구조를 구현할 수 있다.
• 클래스 템플릿의 장점
  • 범용 클래스를 설계할 수 있다. 다양한 데이터 타입에 대해 동일한 자료 구조와 로직을 사용할 수 있다.
  • 코드 중복을 최소화하면서 다양한 타입을 처리하는 유연한 클래스를 만들 수 있다.

4. 템플릿 특수화

• 일반 템플릿으로 처리하기 힘든 특정 타입에 대해 별도로 동작하도록 구현할 수 있다. 이를 템플릿 특수화(template specialization)라고 한다. 일반적인 템플릿을 사용하다가 특정 타입에 대해 별도로 구현된 특수화 템플릿이 있다면, 그 특수화 템플릿이 우선 사용된다.

5. 템플릿의 장점

• 타입 안전성
  • 템플릿은 컴파일 타임에 타입을 결정하므로, 잘못된 타입을 사용하는 경우 컴파일러가 오류를 잡아준다.
• 코드 재사용성
  • 함수나 클래스를 여러 타입에 대해 재사용할 수 있다. 동일한 로직을 여러 타입에 대해 반복 작성할 필요가 없다.
• 유연성
  • 템플릿을 사용하면 다양한 타입을 처리할 수 있어 매우 유연한 코드 작성이 가능하다.

6. 템플릿의 단점

• 컴파일 시간 증가
  • 템플릿은 컴파일 타임에 타입을 바탕으로 새로운 코드가 생성되기 때문에, 복잡한 템플릿 사용은 컴파일 시간을 늘릴 수 있다.
• 디버깅 어려움
  • 템플릿은 컴파일 타임에 특정 타입으로 변환되므로, 에러 메시지가 복잡하고 이해하기 어려울 수 있다.
• 코드 크기 증가
  • 템플릿은 여러 타입에 대해 각각 별도의 코드가 생성되므로, 코드 크기가 늘어날 수 있다.

가변 길이 템플릿

1. 가변 길이 템플릿의 기본 문법

가변 길이 템플릿에서는 템플릿 매개변수 패커(parameter pack)를 사용하여 여러 개의 템플릿 인자를 하나의 묶음으로 처리할 수 있다.

문법

cpp
코드 복사
template <typename... Args>
void functionName(Args... args) {
    // 함수 정의
}

• typename... Args: Args는 템플릿 매개변수 패커로, 0개 이상의 템플릿 인자를 담을 수 있다.
• Args... args: 함수 매개변수에서도 가변 인자를 받을 수 있으며, 인자 리스트에서 개별 인자로 처리된다.

2. 가변 길이 클래스 템플릿

• 함수뿐만 아니라, 클래스 템플릿에서도 가변 길이 템플릿을 사용할 수 있다. 이를 통해 다양한 데이터 타입을 가변적으로 처리할 수 있는 클래스를 작성할 수 있다.

3. 가변 길이 템플릿의 내부 처리

• C++ 컴파일러는 가변 길이 템플릿을 컴파일 타임에 재귀적으로 확장하면서 처리한다. 위에서 봤듯이, Args...는 0개 이상의 인자 리스트로 컴파일러가 재귀적으로 각 인자를 하나씩 처리하고, 남은 인자에 대해 다시 템플릿을 호출하는 방식이다.
• 이 과정에서 재귀 호출의 기저 조건(base case)이 필요하며, 일반적으로 인자가 하나도 남지 않는 경우를 기저 조건으로 처리한다.

4. 가변 길이 템플릿의 활용

가변 길이 템플릿은 매우 유연하여 다양한 상황에서 활용할 수 있다. 다음은 가변 길이 템플릿의 대표적인 사용 예이다.

5. 가변 길이 템플릿의 장점

• 유연성
  • 가변 개수의 인자를 처리할 수 있으므로, 다양한 상황에서 범용적으로 사용할 수 있다.
• 재사용성
  • 같은 로직을 여러 개의 인자에 대해 재사용할 수 있으며, 코드 중복을 줄일 수 있다.
• 타입 안전성
  • 템플릿 인자는 컴파일 타임에 확정되기 때문에, 타입 오류가 발생하면 컴파일러가 이를 잡아낼 수 있다.

6. 가변 길이 템플릿의 단점

• 복잡성
  • 템플릿 문법이 복잡할 수 있으며, 특히 재귀적인 템플릿 처리 과정에서 디버깅이 어려울 수 있다.
• 컴파일 시간 증가
  • 복잡한 템플릿 코드의 경우 컴파일 타임이 길어질 수 있다.
• 템플릿 인스턴스 증가
  • 가변 길이 템플릿은 인자 개수와 타입에 따라 여러 개의 템플릿 인스턴스가 생성되므로, 코드 크기가 증가할 수 있다.

CS

스택과 큐

• 스택(Stack)과 큐(Queue)는 선형 자료구조로, 데이터의 삽입과 삭제가 특정한 규칙에 의해 이루어진다. 두 자료구조는 매우 간단하면서도 다양한 알고리즘과 프로그램의 핵심적인 부분을 담당한다.

1. 스택(Stack)

• 스택은 LIFO(Last In, First Out) 구조를 따르는 자료구조로, 가장 나중에 삽입된 데이터가 가장 먼저 삭제된다. 스택을 상자에 책을 쌓는 방식으로 비유할 수 있다. 새로운 책을 올릴 때는 맨 위에 쌓고, 책을 꺼낼 때도 맨 위에서부터 꺼낸다.
• 스택의 주요 연산
  • push(x)
    • 스택의 맨 위에 새로운 요소를 추가하는 연산이다.
  • pop()
    • 스택의 맨 위에 있는 요소를 제거하고 반환하는 연산이다.
  • peek() (또는 top())
    • 스택의 맨 위에 있는 요소를 제거하지 않고 반환한다.
  • isEmpty()
    • 스택이 비어 있는지를 확인하는 연산이다.
• 스택의 활용 사례
  • 함수 호출 스택
    • 함수 호출과 반환의 순서를 관리하기 위해 사용된다.
  • 수식 계산 및 괄호 검사
    • 연산자 우선순위에 따른 수식 계산이나 괄호의 짝을 확인하는 문제에서 스택이 사용된다.
  • 탐색 알고리즘(DFS)
    • 깊이 우선 탐색(DFS)에서, 방문할 노드를 추적하기 위해 스택을 활용한다.

2. 큐(Queue)

• 큐는 FIFO(First In, First Out) 구조를 따르는 자료구조로, 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다. 큐는 줄을 서서 대기하는 것과 비슷하게, 먼저 줄에 선 사람부터 먼저 처리된다.
• 큐의 주요 연산
  • enqueue(x)
    • 큐의 맨 뒤에 새로운 요소를 추가하는 연산이다.
  • dequeue()
    • 큐의 맨 앞에 있는 요소를 제거하고 반환하는 연산이다.
  • front()
    • 큐의 맨 앞에 있는 요소를 제거하지 않고 반환하는 연산이다.
  • rear()
    • 큐의 맨 뒤에 있는 요소를 반환한다.
  • isEmpty()
    • 큐가 비어 있는지를 확인하는 연산이다.
• 큐의 활용 사례
  • 프로세스 스케줄링
    • 운영체제에서 프로세스나 작업을 순차적으로 처리하기 위해 큐가 사용된다.
  • 데이터 스트리밍
    • 네트워크 패킷 처리나 데이터 스트리밍에서, 도착한 데이터를 처리 순서대로 큐에 넣고 꺼낸다.
  • 너비 우선 탐색(BFS)
    • 그래프 탐색에서, 방문할 노드를 추적하기 위해 큐를 사용한다.

스택과 큐의 메모리 관리

• 스택과 큐 모두 메모리 관리에 중요한 역할을 한다. 예를 들어, 스택은 프로그램이 함수 호출 시 메모리를 할당하고 해제하는 방식에 직접적으로 관여하며, 재귀 호출이나 중첩 함수에서 사용된다. 반면 큐는 순차적으로 처리해야 하는 작업을 저장하는 데 유용하다.
• 스택은 일반적으로 메모리 상의 고정 크기 영역에서 작동하지만, 큐는 동적 메모리 할당이 이루어지는 경우가 많다.