상세 컨텐츠

본문 제목

자료구조 및 STL 요약

Programing/C, C++

by CouqueD'asse 2024. 7. 24. 21:30

본문

시간복잡도

시간복잡도는 알고리즘이나 연산이 입력 크기 \(n\)에 따라 수행되는 시간을 표현하는 방식입니다. 주로 빅오 표기법을 사용하여 최악의 경우를 나타냅니다. 예: \(O(1)\), \(O(n)\), \(O(n^2)\), \(O(\log n)\), \(O(n \log n)\).

스택과 큐

  • 스택 (Stack): LIFO (Last In, First Out) 구조. 예: 함수 호출 스택, 웹 브라우저의 뒤로 가기.
  • 큐 (Queue): FIFO (First In, First Out) 구조. 예: 프린터 작업 대기열, BFS 탐색.

벡터와 리스트

  • 벡터 (Vector): 동적 배열로, 요소에 대한 임의 접근이 빠름 (\(O(1)\)). 예: 연속적인 데이터 처리가 필요한 경우.
  • 리스트 (List): 이중 연결 리스트로, 삽입 및 삭제가 빠름 (\(O(1)\)). 예: 빈번한 삽입/삭제가 필요한 경우.

리스트에서 at 구현

template<typename T>
T& List<T>::at(size_t index) {
    if (index >= size) throw std::out_of_range("Index out of range");
    Node* current = head;
    for (size_t i = 0; i < index; ++i) {
        current = current->next;
    }
    return current->data;
}

검색 속도 줄이는 방법

  • 정렬된 상태: 이진 탐색 (\(O(\log n)\)).
  • 정렬되지 않은 상태: 해시 테이블 (\(O(1)\) 평균).

이중 연결 리스트의 삽입, 삭제, 추가 수도코드

class Node {
public:
    int data;
    Node* prev;
    Node* next;
};

void insert(Node* prev_node, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
    new_node->prev = prev_node;
    if (new_node->next != nullptr) new_node->next->prev = new_node;
}

void deleteNode(Node** head_ref, Node* del) {
    if (*head_ref == nullptr || del == nullptr) return;
    if (*head_ref == del) *head_ref = del->next;
    if (del->next != nullptr) del->next->prev = del->prev;
    if (del->prev != nullptr) del->prev->next = del->next;
    delete del;
}

void append(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    Node* last = *head_ref;
    new_node->data = new_data;
    new_node->next = nullptr;
    if (*head_ref == nullptr) {
        new_node->prev = nullptr;
        *head_ref = new_node;
        return;
    }
    while (last->next != nullptr) last = last->next;
    last->next = new_node;
    new_node->prev = last;
}

2진 트리

이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리 구조입니다.

순회 방법과 상황

  • 전위 순회 (Preorder): 루트-왼쪽-오른쪽. 예: 복사본 생성.
  • 중위 순회 (Inorder): 왼쪽-루트-오른쪽. 예: 정렬된 출력.
  • 후위 순회 (Postorder): 왼쪽-오른쪽-루트. 예: 삭제 작업.

2진 탐색 / 2진 탐색 트리

  • 이진 탐색: \(O(\log n)\).
  • 이진 탐색 트리 (BST): 최악의 경우 \(O(n)\), 평균 \(O(\log n)\).

힙

  • 정의: 완전 이진 트리, 최대 또는 최소 힙.
  • 추가: 새로운 노드를 힙의 끝에 추가 후, 상향 이동.
  • 삭제: 루트를 삭제하고 마지막 노드를 루트에 배치 후, 하향 이동.

Map과 Unordered Map, Multi Map의 차이

Map

  • 정렬된 키-값 쌍을 저장합니다.
  • 내부적으로 **이진 탐색 트리 (예: 레드-블랙 트리)**를 사용하여 구현됩니다.
  • 삽입, 삭제, 검색이 \(O(\log n)\)의 시간복잡도를 가집니다.

Unordered Map

  • 해시 테이블을 사용하여 키-값 쌍을 저장합니다.
  • 키의 순서가 보장되지 않습니다.
  • 삽입, 삭제, 검색이 평균적으로 \(O(1)\)의 시간복잡도를 가집니다.

Multi Map

  • 중복 키를 허용하는 Map입니다.
  • 내부적으로 이진 탐색 트리를 사용하여 구현됩니다.
  • 삽입, 삭제, 검색이 \(O(\log n)\)의 시간복잡도를 가집니다.
  • 동일한 키에 대해 여러 값을 저장할 수 있습니다.

STL의 set, unordered set과 Pair에 대한 설명

Set

  • 고유한 원소들을 저장하는 정렬된 집합.
  • 내부적으로 이진 탐색 트리를 사용하여 구현됩니다.
  • 삽입, 삭제, 검색이 \(O(\log n)\)의 시간복잡도를 가집니다.

Unordered Set

  • 고유한 원소들을 저장하는 비정렬된 집합.
  • 내부적으로 해시 테이블을 사용하여 구현됩니다.
  • 삽입, 삭제, 검색이 평균적으로 \(O(1)\)의 시간복잡도를 가집니다.

Pair

  • 두 개의 데이터 값을 저장하는 템플릿 클래스.
  • 두 개의 데이터는 서로 다른 타입일 수 있습니다.
  • 예: std::pair<int, std::string>.

균형이진트리에 대한 설명

균형 이진 트리는 각 노드의 왼쪽 및 오른쪽 서브트리의 높이가 크게 차이나지 않는 이진 트리입니다. 이를 통해 삽입, 삭제, 검색이 \(O(\log n)\)의 시간복잡도를 유지할 수 있습니다.

AVL Tree

  • 높이 균형 트리로, 각 노드의 왼쪽 및 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지합니다.
  • 삽입과 삭제 시 재균형 작업이 필요합니다.

Red-Black Tree

  • 각 노드가 빨강 또는 검정 색을 가지며, 균형을 유지하는 이진 탐색 트리입니다.
  • 다음 규칙을 만족합니다:
    • 루트는 검정.
    • 모든 리프는 검정.
    • 빨강 노드의 자식은 검정.
    • 임의의 노드에서 리프까지의 모든 경로에는 같은 수의 검정 노드가 있습니다.

Unordered Map의 해시에 대해 설명

해시 함수를 사용하여 키를 해시 값으로 변환하고, 이 해시 값을 통해 값을 저장할 위치를 결정합니다. 이로 인해 평균적으로 \(O(1)\)의 검색 시간을 갖게 됩니다. 충돌이 발생할 경우 체이닝 또는 오픈 어드레싱 기법을 사용하여 해결합니다.

당신의 프로젝트에 해싱을 사용한다면 어느 부분에서?

해싱은 빠른 검색, 삽입, 삭제가 필요한 상황에서 유용합니다. 예를 들어, 캐시 구현, 데이터베이스 인덱싱, 중복 검사 등에 사용될 수 있습니다.

그래프

최소비용 신장트리(MST)란 무엇이며 신장트리를 구성하기 위한 알고리즘

MST는 주어진 그래프에서 모든 정점을 연결하면서 그 가중치의 합이 최소가 되는 트리를 말합니다. MST를 구성하기 위한 대표적인 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

탐색방법 2가지

  • 너비 우선 탐색 (BFS): 큐를 사용하여 레벨별로 탐색합니다.
  • 깊이 우선 탐색 (DFS): 스택 또는 재귀를 사용하여 깊이 우선으로 탐색합니다.

다익스트라 알고리즘

다익스트라 알고리즘은 단일 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 가중치가 있는 그래프에서 동작하며, 우선순위 큐를 사용하여 최단 거리를 반복적으로 갱신합니다.

A* 알고리즘

A* 알고리즘은 다익스트라 알고리즘의 확장판으로, 휴리스틱 함수를 사용하여 경로 탐색의 효율성을 높입니다. 휴리스틱 함수는 현재 정점에서 목표 정점까지의 예상 비용을 추정하는 함수입니다.

길찾기 방법 중 A*와 네비게이션 메시의 차이점

  • A: 일반적인 경로 탐색 알고리즘으로, 다양한 환경에서 최단 경로를 찾을 수 있습니다.
  • 네비게이션 메시: 특정한 환경에서 사용되는 경로 탐색 방법으로, 공간을 다각형의 네트워크로 분할하여 효율적인 경로 탐색을 지원합니다.

1,000,000개의 ID와 객체의 주소가 있을 때 어떤 자료구조로 관리하면 유용할까?

해시맵 (HashMap) 또는 unordered_map이 유용합니다. 이는 ID를 키로 사용하여 객체의 주소를 빠르게 검색, 삽입, 삭제할 수 있습니다.

정렬 알고리즘

시간복잡도 O(n^2)에 해당하는 정렬 알고리즘

  • 버블 정렬 (Bubble Sort): 인접한 두 요소를 비교하여 정렬합니다.
  • 삽입 정렬 (Insertion Sort): 이미 정렬된 부분에 새로운 요소를 적절한 위치에 삽입합니다.
  • 선택 정렬 (Selection Sort): 가장 작은 요소를 선택하여 정렬된 부분 뒤에 배치합니다.

시간복잡도 O(nlogn)에 해당하는 정렬 알고리즘

  • 합병 정렬 (Merge Sort): 리스트를 반으로 나누어 정렬 후 병합합니다.
  • 힙 정렬 (Heap Sort): 힙 자료구조를 사용하여 정렬합니다.
  • 퀵 정렬 (Quick Sort): 피벗을 기준으로 리스트를 분할하여 정렬합니다.

시간복잡도 O(n)에 해당하는 정렬 알고리즘

  • 계수 정렬 (Counting Sort): 입력 값의 범위를 기준으로 계수를 사용하여 정렬합니다.
  • 기수 정렬 (Radix Sort): 자리수를 기준으로 순차적으로 정렬합니다.
  • 버킷 정렬 (Bucket Sort): 범위를 여러 버킷으로 나누어 정렬합니다.

STL의 algorithm에서 사용되는 정렬 알고리즘

STL의 std::sort는 내부적으로 퀵 정렬, 힙 정렬, 삽입 정렬을 혼합하여 사용합니다.

퀵 소트에 대해 설명하세요

퀵 소트는 피벗을 기준으로 리스트를 두 부분으로 나눈 후 각각을 재귀적으로 정렬하는 알고리즘입니다. 평균 시간복잡도는 \(O(n \log n)\)입니다.

퀵 소트에서 시간 복잡도 O(n^2)의 효율을 보일 때가 있음. 어느 경우?

퀵 소트는 이미 정렬된 배열이나 모든 요소가 동일한 배열에서 최악의 경우를 보이며, 이 경우 시간복잡도는 \(O(n^2)\)입니다.

알고리즘

분할 정복 알고리즘 적용이 가능한 상황은?

문제를 작은 하위 문제로 나눌 수 있고, 각 하위 문제의 결과를 합쳐서 전체 문제를 해결할 수 있는 경우. 예: 합병 정렬, 퀵 정렬.

메모이제이션을 활용하여 Dynamic Programming을 사용해야 하는 상황?

동일한 하위 문제가 여러 번 재계산되는 경우, 이를 메모이제이션으로 최적화할 수 있습니다. 예: 피보나치 수열, 배낭 문제.

백트래킹에 대해 설명하세요

백트래킹은 해를 찾기 위해 모든 가능한 후보를 탐색하는 알고리즘입니다. 유망하지 않은 경로는 중간에 포기함으로써 효율성을 높입니다. 예: N-퀸 문제, 미로 찾기.

탐욕 알고리즘의 특징에 대하여

매 단계에서 현재 최적의 선택을 함으로써 전체 문제의 최적해를 구하는 알고리즘입니다. 예: 거스름돈 문제, 최소 신장 트리.

해싱 테이블에 대한 설명

해싱 테이블은 데이터의 빠른 접근을 위해 사용하는 자료구조입니다. 키-값 쌍을 저장하며, 키를 해시 함수로 변환하여 저장 위치를 결정합니다. 이는 평균적으로 \(O(1)\)의 시간복잡도로 검색, 삽입, 삭제를 가능하게 합니다.

해시 함수

해시 함수는 키를 입력받아 고정된 크기의 해시 값(인덱스)을 반환합니다. 좋은 해시 함수는 충돌을 최소화하면서 해시 값을 고르게 분포시킵니다.

충돌 해결 방법

키의 해시 값이 동일해지는 경우(충돌)를 해결하기 위한 방법들:

  1. 체이닝 (Chaining): 각 인덱스에 연결 리스트를 사용하여 충돌된 요소들을 저장합니다.
    • 장점: 해시 테이블이 꽉 차더라도 성능 저하가 크지 않습니다.
    • 단점: 포인터를 사용하기 때문에 추가적인 메모리 사용이 필요합니다.
  2. 오픈 어드레싱 (Open Addressing): 충돌 발생 시 해시 테이블 내의 다른 빈 슬롯을 찾아 저장합니다.
    • 선형 탐사법 (Linear Probing): 충돌 발생 시 다음 빈 슬롯을 찾습니다.
    • 이차 탐사법 (Quadratic Probing): 충돌 발생 시 탐사 간격을 제곱수로 증가시킵니다.
    • 이중 해싱 (Double Hashing): 두 번째 해시 함수를 사용하여 충돌 시 탐사 간격을 결정합니다.

당신의 프로젝트에 해싱을 사용한다면 어느 부분에서?

해싱은 빠른 검색, 삽입, 삭제가 필요한 상황에서 유용합니다. 예를 들어, 다음과 같은 상황에서 사용할 수 있습니다:

  • 캐시 구현: 빈번하게 조회되는 데이터를 해시 테이블에 저장하여 빠르게 접근.
  • 데이터베이스 인덱싱: 테이블의 특정 열에 대한 빠른 검색을 위해 해시 인덱스를 사용.
  • 중복 검사: 대규모 데이터셋에서 중복된 항목을 빠르게 찾기 위해 사용.
  • 연관 배열: 키-값 쌍을 효율적으로 관리하여, 예를 들어 사용자 ID와 프로필 정보를 연결.

그래프

최소비용 신장트리(MST)란 무엇이며 신장트리를 구성하기 위한 알고리즘

  • *최소비용 신장트리(MST)**는 주어진 연결된 가중치 그래프에서 모든 정점을 포함하면서, 그 가중치의 합이 최소가 되는 트리입니다. MST를 구성하기 위한 대표적인 알고리즘은 다음과 같습니다:
  1. 크루스칼 알고리즘 (Kruskal's Algorithm): 간선을 가중치 순으로 정렬한 후, 가장 낮은 가중치부터 간선을 선택하여 사이클이 생기지 않도록 연결합니다.
  2. 프림 알고리즘 (Prim's Algorithm): 한 정점에서 시작하여 연결된 간선 중 가장 낮은 가중치를 선택하면서 신장트리를 확장합니다.

탐색방법 2가지

  1. 너비 우선 탐색 (BFS): 큐를 사용하여 레벨별로 탐색합니다. 모든 정점을 동일 레벨에서 방문 후, 다음 레벨로 이동합니다.
    • 사용 예시: 최단 경로 찾기, 미로 탐색.
  2. 깊이 우선 탐색 (DFS): 스택 또는 재귀를 사용하여 깊이 우선으로 탐색합니다. 한 경로를 끝까지 탐색한 후, 백트래킹하여 다음 경로를 탐색합니다.
    • 사용 예시: 그래프의 연결 요소 찾기, 사이클 검출.

다익스트라 알고리즘

다익스트라 알고리즘은 단일 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 가중치가 있는 그래프에서 동작하며, 우선순위 큐를 사용하여 최단 거리를 반복적으로 갱신합니다. 시간복잡도는 \(O(E + V \log V)\)입니다.

A* 알고리즘

A\* 알고리즘은 다익스트라 알고리즘의 확장판으로, 휴리스틱 함수를 사용하여 경로 탐색의 효율성을 높입니다. 각 노드에서 목표 노드까지의 예상 비용을 추정하는 휴리스틱 함수와 실제 이동 비용을 더하여 우선순위를 결정합니다.

길찾기 방법 중 A*와 네비게이션 메시의 차이점

  • A\: 일반적인 경로 탐색 알고리즘으로, 다양한 환경에서 최단 경로를 찾을 수 있습니다. 휴리스틱 함수를 통해 효율적으로 경로를 찾습니다.
  • 네비게이션 메시: 3D 게임이나 시뮬레이션 환경에서 사용되는 경로 탐색 방법으로, 공간을 다각형의 네트워크로 분할하여 이동할 수 있는 영역을 정의합니다. 이는 경로 계산을 단순화하고, 실시간 경로 탐색에 효율적입니다.

1,000,000개의 ID와 객체의 주소가 있을 때 어떤 자료구조로 관리하면 유용할까?

해시맵 (HashMap) 또는 unordered_map이 유용합니다. 이는 ID를 키로 사용하여 객체의 주소를 빠르게 검색, 삽입, 삭제할 수 있으며, 평균적으로 \(O(1)\)의 시간복잡도를 갖습니다.

정렬 알고리즘

시간복잡도 O(n^2)에 해당하는 정렬 알고리즘

  • 버블 정렬 (Bubble Sort): 인접한 두 요소를 비교하여 정렬합니다.
  • 삽입 정렬 (Insertion Sort): 이미 정렬된 부분에 새로운 요소를 적절한 위치에 삽입합니다.
  • 선택 정렬 (Selection Sort): 가장 작은 요소를 선택하여 정렬된 부분 뒤에 배치합니다.

시간복잡도 O(nlogn)에 해당하는 정렬 알고리즘

  • 합병 정렬 (Merge Sort): 리스트를 반으로 나누어 정렬 후 병합합니다.
  • 힙 정렬 (Heap Sort): 힙 자료구조를 사용하여 정렬합니다.
  • 퀵 정렬 (Quick Sort): 피벗을 기준으로 리스트를 분할하여 정렬합니다.

시간복잡도 O(n)에 해당하는 정렬 알고리즘

  • 계수 정렬 (Counting Sort): 입력 값의 범위를 기준으로 계수를 사용하여 정렬합니다.
  • 기수 정렬 (Radix Sort): 자리수를 기준으로 순차적으로 정렬합니다.
  • 버킷 정렬 (Bucket Sort): 범위를 여러 버킷으로 나누어 정렬합니다.

STL의 algorithm에서 사용되는 정렬 알고리즘

STL의 std::sort는 내부적으로 퀵 정렬, 힙 정렬, 삽입 정렬을 혼합하여 사용합니다.

퀵 소트에 대해 설명하세요

퀵 소트는 피벗을 기준으로 리스트를 두 부분으로 나눈 후 각각을 재귀적으로 정렬하는 알고리즘입니다. 평균 시간복잡도는 \(O(n \log n)\)입니다.

퀵 소트에서 시간 복잡도 O(n^2)의 효율을 보일 때가 있음. 어느 경우?

퀵 소트는 이미 정렬된 배열이나 모든 요소가 동일한 배열에서 최악의 경우를 보이며, 이 경우 시간복잡도는 \(O(n^2)\)입니다.

알고리즘

분할 정복 알고리즘 적용이 가능한 상황은?

문제를 작은 하위 문제로 나눌 수 있고, 각 하위 문제의 결과를 합쳐서 전체 문제를 해결할 수 있는 경우. 예: 합병 정렬, 퀵 정렬.

메모이제이션을 활용하여 Dynamic Programming을 사용해야 하는 상황?

동일한 하위 문제가 여러 번 재계산되는 경우, 이를 메모이제이션으로 최적화할 수 있습니다. 예: 피보나치 수열, 배낭 문제.

백트래킹에 대해 설명하세요

백트래킹은 해를 찾기 위해 모든 가능한 후보를 탐색하는 알고리즘입니다. 유망하지 않은 경로는 중간에 포기함으로써 효율성을 높입니다. 예: N-퀸 문제, 미로 찾기.

탐욕 알고리즘의 특징에 대하여

매 단계에서 현재 최적의 선택을 함으로써 전체 문제의 최적해를 구하는 알고리즘입니다. 예: 거스름돈 문제, 최소 신장 트리.

해싱 테이블에 대한 설명

해싱 테이블은 키를 해시 함수로 변환하여 인덱스를 계산하고, 해당 인덱스에 데이터를 저장합니다. 이는 평균적으로 \(O(1)\)의 시간복잡도로 검색, 삽입, 삭제를 가능하게 합니다. 충돌 해결 방법으로 체이닝 또는 오픈 어드레싱 기법을 사용합니다.

'Programing > C, C++' 카테고리의 다른 글

#자료구조와 함께 배우는 알고리즘 입문 C언어 - 13  (0) 2022.06.08
#자료구조와 함께 배우는 알고리즘 입문 C언어 - 12  (0) 2022.06.03
#자료구조와 함께 배우는 알고리즘 입문 C언어 - 11  (0) 2022.06.02
#자료구조와 함께 배우는 알고리즘 입문 C언어 - 10  (0) 2022.05.30
#자료구조와 함께 배우는 알고리즘 입문 C언어 - 9  (0) 2022.05.26

관련글 더보기

티스토리툴바