신입 개발자 기술면접 C++ 손코딩 : Array, Vector, List, Stack, Queue, Tree, Heap, Hash 모듈 없이 구현

https://www.hackerearth.com/practice/notes/big-o-cheatsheet-series-data-structures-and-algorithms-with-thier-complexities-1/

C++ Data Structure's RunTime CheatSheet

 

 

1. Vector, List, Map 에 대해서 설명해 보세요.

stl에 등록되어 있는 자료구조들로서 vector는 동적배열로 이루어져 있으며, List는 더블링크드 리스트로 이루어져있습니다. Map을 Key와 Value를 쌍으로 이루며 레드블랙트리 알고리즘으로 이루어져 있어서 빠른 탐색속도를 자랑합니다.

 

2. Vector, List 의 차이에 대해서 설명하세요.

vector는 동적배열의 클래스 탬플릿이라고 할 수 있습니다.

vector객체는 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경합니다.

 

list는 이중연결리스트의 클래스 탬플릿이라고 할 수 있습니다. 

이 컨테이너는 모든 요소에서 양방향 접근, 빠른 삽입과 삭제를 할 수 있지만, 임의 접근은 불가합니다.

또한 리스트를 구성하는 링크(link)는 포인터이므로, 다음과 같은 특정 작업을 링크만 재배치하는 것으로 아주 빠르게 수행할 수 있습니다.

 

3. Tree 에 대해서 아는대로 말하시오.

트리는 탐색에서의 뛰어난 성능을 가진 컨테이너로서 계층적인 데이터 검색에 압도적인 성능을 보입니다.

이진트리 레드블랙트리, 세그먼트 트리, AVL트리 등 여러 종류의 트리가 있고, 

이진트리는 각각의 노드가 최대 두개의 자식노드를 가지는 트리 구조로서

노드당 두개의 자식노드를 가지고 있는 완전이진트리로 구성이 된다면 아주 좋은 트리가 되지만, 그렇지 않은 경우에는 트리를 쓰느니만 못한 결과를 초래 할 수도 있습니다.

이러한 단점을 해결하기 위해서 발전된 형태가 레드블랙트리가 있는것으로 알고 있습니다.

---

Array

C++에서 고정 크기의 배열은 기본적으로 지원됩니다. 하지만 클래스를 만들어 다루는 것을 원한다면 다음과 같이 간단하게 구현할 수 있습니다. C++에서는 고정 크기 배열이 자동으로 메모리를 관리하기 때문에 별도의 소멸자가 필요하지 않습니다.

template<typename T, size_t S>
class StaticArray {
private:
    T m_Array[S]; // 고정 크기의 배열

public:
    T& operator[](size_t index) {
        return m_Array[index];
    }

    const T& operator[](size_t index) const {
        return m_Array[index];
    }

    size_t Size() const { return S; }
};

 

Vector

std::vector와 같은 동적 배열을 간단하게 구현하는 것은 조금 더 복잡하지만, 다음은 그 기본적인 형태입니다.

template<typename T>
class Vector {
private:
    T* data;
    size_t capacity;
    size_t size;

    void reallocate(size_t newCapacity) {
        T* newData = new T[newCapacity];
        size_t newSize = size > newCapacity ? newCapacity : size;
        for (size_t i = 0; i < newSize; ++i) {
            newData[i] = std::move(data[i]);
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
        size = newSize;
    }

public:
    Vector() : data(nullptr), capacity(0), size(0) {}

    void push_back(const T& value) {
        if (size >= capacity) {
            size_t newCapacity = capacity == 0 ? 1 : capacity * 2;
            reallocate(newCapacity);
        }
        data[size++] = value;
    }

    ~Vector() {
        delete[] data;
    }
};

 

List

연결 리스트는 노드들이 포인터를 통해 연결되어 있는 구조입니다. 다음은 단순 연결 리스트(Singly Linked List)의 기본적인 구현입니다.

template<typename T>
class List {
private:
    struct Node {
        T value;
        Node* next;
        Node(const T& val) : value(val), next(nullptr) {}
    };

    Node* head;

public:
    List() : head(nullptr) {}

    void push_front(const T& value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    ~List() {
        Node* current = head;
        while (current != nullptr) {
            Node* temp = current;
            current = current->next;
            delete temp;
        }
    }
};

 

Stack

Stack은 LIFO(Last In, First Out) 정책을 따르는 자료구조로, 가장 마지막에 들어온 요소가 가장 먼저 나갑니다. 배열을 사용하여 구현할 수 있습니다.

template<typename T>
class Stack {
private:
    struct Node {
        T value;
        Node* next;
        Node(const T& val) : value(val), next(nullptr) {}
    };

    Node* topNode;

public:
    Stack() : topNode(nullptr) {}

    void push(const T& value) {
        Node* newNode = new Node(value);
        newNode->next = topNode;
        topNode = newNode;
    }

    ~Stack() {
        while (topNode != nullptr) {
            Node* temp = topNode;
            topNode = topNode->next;
            delete temp;
        }
    }
};

Queue

Queue는 FIFO(First In, First Out) 정책을 따르는 자료구조로, 가장 먼저 들어온 요소가 가장 먼저 나갑니다. 연결 리스트를 사용하여 구현할 수 있습니다.

template<typename T>
class Queue {
private:
    struct Node {
        T value;
        Node* next;
        Node(const T& val) : value(val), next(nullptr) {}
    };

    Node* frontNode;
    Node* backNode;

public:
    Queue() : frontNode(nullptr), backNode(nullptr) {}

    void enqueue(const T& value) {
        Node* newNode = new Node(value);
        if (backNode) {
            backNode->next = newNode;
        }
        backNode = newNode;
        if (!frontNode) {
            frontNode = backNode;
        }
    }

    ~Queue() {
        while (frontNode != nullptr) {
            Node* temp = frontNode;
            frontNode = frontNode->next;
            delete temp;
        }
    }
};

Binary Tree

template<typename T>
class BinaryTree {
private:
    struct Node {
        T value;
        Node *left, *right;

        Node(T val) : value(val), left(nullptr), right(nullptr) {}
    };

    Node* root;

    void Clear(Node* node) {
        if (node != nullptr) {
            Clear(node->left);
            Clear(node->right);
            delete node;
        }
    }

public:
    BinaryTree() : root(nullptr) {}

    // 이진 트리에 요소를 삽입하고 삭제하는 등의 메서드 구현 필요

    ~BinaryTree() {
        Clear(root);
    }
};

Binary Heap

이진 힙은 배열을 기반으로 하는 완전 이진 트리입니다. 여기서는 최대 힙(Max Heap)의 간단한 구현을 보여드립니다.

template<typename T>
class BinaryHeap {
private:
    std::vector<T> heap;

    void HeapifyDown(int index) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;

        if (left < heap.size() && heap[left] > heap[largest])
            largest = left;
        if (right < heap.size() && heap[right] > heap[largest])
            largest = right;

        if (largest != index) {
            std::swap(heap[index], heap[largest]);
            HeapifyDown(largest);
        }
    }

    void HeapifyUp(int index) {
        while (index != 0 && heap[(index - 1) / 2] < heap[index]) {
            std::swap(heap[(index - 1) / 2], heap[index]);
            index = (index - 1) / 2;
        }
    }

public:
    void Insert(T element) {
        heap.push_back(element);
        HeapifyUp(heap.size() - 1);
    }

    T ExtractMax() {
        if (heap.size() == 0)
            throw std::out_of_range("Heap is empty");

        T root_value = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        HeapifyDown(0);
        return root_value;
    }

    bool IsEmpty() const {
        return heap.empty();
    }
};

Binary Search Tree

이진 탐색 트리

template<typename T>
class BinarySearchTree {
private:
    struct Node {
        T value;
        Node *left, *right;

        Node(const T& val) : value(val), left(nullptr), right(nullptr) {}
    };

    Node* root;

    void clear(Node* node) {
        if (node) {
            clear(node->left);
            clear(node->right);
            delete node;
        }
    }

public:
    BinarySearchTree() : root(nullptr) {}

    ~BinarySearchTree() {
        clear(root);
    }
};

Priority Queue - Max Heap

MaxPriorityQueue 클래스는 요소를 내림차순으로 정렬하여, 가장 큰 요소가 항상 맨 앞에 오도록 합니다.

heapifyUp과 heapifyDown 메서드는 힙 속성을 유지하기 위해 요소를 적절한 위치로 이동시킵니다. push 메서드는 새로운 요소를 힙에 추가하고, pop 메서드는 힙에서 최댓값 또는 최솟값을 제거하고 반환합니다. top 메서드는 힙의 최댓값 또는 최솟값을 조회하지만 제거하지는 않습니다. empty와 size 메서드는 힙이 비어 있는지 여부를 반환하고, 힙의 크기를 반환합니다.

#include <vector>
#include <algorithm> // For std::swap
#include <stdexcept> // For std::out_of_range

template<typename T>
class MaxPriorityQueue {
private:
    std::vector<T> heap;

    void heapifyDown(int currentIdx) {
        int leftIdx = 2 * currentIdx + 1;
        int rightIdx = 2 * currentIdx + 2;
        int largestIdx = currentIdx;

        if (leftIdx < heap.size() && heap[leftIdx] > heap[largestIdx]) {
            largestIdx = leftIdx;
        }

        if (rightIdx < heap.size() && heap[rightIdx] > heap[largestIdx]) {
            largestIdx = rightIdx;
        }

        if (largestIdx != currentIdx) {
            std::swap(heap[currentIdx], heap[largestIdx]);
            heapifyDown(largestIdx);
        }
    }

    void heapifyUp(int currentIdx) {
        while (currentIdx != 0 && heap[(currentIdx - 1) / 2] < heap[currentIdx]) {
            std::swap(heap[(currentIdx - 1) / 2], heap[currentIdx]);
            currentIdx = (currentIdx - 1) / 2;
        }
    }

public:
    void push(const T& value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    T pop() {
        if (heap.empty()) throw std::out_of_range("PriorityQueue is empty");

        T maxValue = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
        return maxValue;
    }

    const T& top() const {
        if (heap.empty()) throw std::out_of_range("PriorityQueue is empty");
        return heap[0];
    }

    bool empty() const {
        return heap.empty();
    }

    size_t size() const {
        return heap.size();
    }
};

Priority Queue - Min Heap

Priority Queue는 내부적으로 보통 이진 힙(Binary Heap) 구조를 사용합니다. C++에서는 이를 std::vector를 사용하여 구현할 수 있으며, 기본적으로 최대 힙(Max Heap)을 사용합니다.

 

MinPriorityQueue 클래스는 요소를 오름차순으로 정렬하여, 가장 작은 요소가 항상 맨 앞에 오도록 합니다.

heapifyUp과 heapifyDown 메서드는 힙 속성을 유지하기 위해 요소를 적절한 위치로 이동시킵니다. push 메서드는 새로운 요소를 힙에 추가하고, pop 메서드는 힙에서 최댓값 또는 최솟값을 제거하고 반환합니다. top 메서드는 힙의 최댓값 또는 최솟값을 조회하지만 제거하지는 않습니다. empty와 size 메서드는 힙이 비어 있는지 여부를 반환하고, 힙의 크기를 반환합니다.

#include <vector>
#include <algorithm> // For std::swap
#include <stdexcept> // For std::out_of_range

template<typename T>
class MinPriorityQueue {
private:
    std::vector<T> heap;

    void heapifyDown(int currentIdx) {
        int leftIdx = 2 * currentIdx + 1;
        int rightIdx = 2 * currentIdx + 2;
        int smallestIdx = currentIdx;

        if (leftIdx < heap.size() && heap[leftIdx] < heap[smallestIdx]) {
            smallestIdx = leftIdx;
        }

        if (rightIdx < heap.size() && heap[rightIdx] < heap[smallestIdx]) {
            smallestIdx = rightIdx;
        }

        if (smallestIdx != currentIdx) {
            std::swap(heap[currentIdx], heap[smallestIdx]);
            heapifyDown(smallestIdx);
        }
    }

    void heapifyUp(int currentIdx) {
        while (currentIdx != 0 && heap[(currentIdx - 1) / 2] > heap[currentIdx]) {
            std::swap(heap[(currentIdx - 1) / 2], heap[currentIdx]);
            currentIdx = (currentIdx - 1) / 2;
        }
    }

public:
    void push(const T& value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    T pop() {
        if (heap.empty()) throw std::out_of_range("PriorityQueue is empty");

        T minValue = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
        return minValue;
    }

    const T& top() const {
        if (heap.empty()) throw std::out_of_range("PriorityQueue is empty");
        return heap[0];
    }

    bool empty() const {
        return heap.empty();
    }

    size_t size() const {
        return heap.size();
    }
};

 

Unordered Map

template<typename KeyType, typename ValueType>
class UnorderedMap {
private:
    struct Node {
        KeyType key;
        ValueType value;
        Node* next;

        Node(const KeyType& key, const ValueType& value) : key(key), value(value), next(nullptr) {}
    };

    std::vector<Node*> buckets;
    size_t bucketCount;

    size_t GetBucketIndex(const KeyType& key) const {
        std::hash<KeyType> hashFn;
        return hashFn(key) % bucketCount;
    }

public:
    UnorderedMap(size_t numBuckets) : bucketCount(numBuckets) {
        buckets.resize(bucketCount, nullptr);
    }

    void insert(const KeyType& key, const ValueType& value) {
        size_t bucketIdx = GetBucketIndex(key);
        Node* newNode = new Node(key, value);
        newNode->next = buckets[bucketIdx];
        buckets[bucketIdx] = newNode;
    }

    // UnorderedMap의 나머지 구현 부분 (검색, 삭제 등)

    ~UnorderedMap() {
        for (Node* head : buckets) {
            while (head != nullptr) {
                Node* temp = head;
                head = head->next;
                delete temp;
            }
        }
    }
};

 

번외) Unordered Map UPGRADE

여기서는 체이닝 방법을 사용하여 충돌을 해결하는 기본적인 unordered_map을 구현하겠습니다. 이 구현은 해시 테이블의 핵심 아이디어를 포함하지만, 실제 프로덕션 환경에서 사용하기에는 더 많은 최적화와 예외 처리가 필요합니다.

 

이 코드는 UnorderedMap을 위한 기본적인 구현을 제공합니다.

• 체이닝(Chaining): 각 버킷은 std::list<KeyValuePair>를 사용하여 키-값 쌍을 저장합니다. 이를 통해 해시 충돌을 해결합니다.
• 해시 함수(Hash Function): 기본 해시 함수로 std::hash<KeyType>를 사용합니다. 이는 사용자 정의 타입에 대해 특수화될 수 있습니다.
• 재해시(Rehashing): 요소의 수가 버킷의 수의 75%를 초과하면, 버킷 배열의 크기를 두 배로 늘립니다.

insert, at, size, contains 등의 기본적인 메서드를 포함합니다. 실제 사용을 위해서는 더 많은 예외 처리, 이터레이터 지원, 복사 및 이동 생성자 및 할당 연산자의 구현 등이 필요할 수 있습니다.

#include <list>
#include <vector>
#include <functional>
#include <stdexcept>

template<typename KeyType, typename ValueType, typename Hash = std::hash<KeyType>>
class UnorderedMap {
private:
    struct KeyValuePair {
        KeyType key;
        ValueType value;
        KeyValuePair(const KeyType& key, const ValueType& value) : key(key), value(value) {}
    };

    std::vector<std::list<KeyValuePair>> buckets;
    Hash hasher;
    size_t numElements;

    size_t getBucketIndex(const KeyType& key) const {
        return hasher(key) % buckets.size();
    }

    void rehash(size_t newBucketCount) {
        std::vector<std::list<KeyValuePair>> newBuckets(newBucketCount);
        for (auto& bucket : buckets) {
            for (auto& kv : bucket) {
                size_t newBucketIndex = hasher(kv.key) % newBucketCount;
                newBuckets[newBucketIndex].push_back(kv);
            }
        }
        buckets = std::move(newBuckets);
    }

public:
    UnorderedMap(size_t bucketCount = 8) : buckets(bucketCount), numElements(0) {}

    void insert(const KeyType& key, const ValueType& value) {
        size_t bucketIndex = getBucketIndex(key);
        for (auto& kv : buckets[bucketIndex]) {
            if (kv.key == key) {
                kv.value = value;
                return;
            }
        }
        buckets[bucketIndex].emplace_back(key, value);
        numElements++;

        if (numElements > buckets.size() * 0.75) { // Load factor of 0.75 for rehashing
            rehash(buckets.size() * 2);
        }
    }

    ValueType& at(const KeyType& key) {
        size_t bucketIndex = getBucketIndex(key);
        for (auto& kv : buckets[bucketIndex]) {
            if (kv.key == key) {
                return kv.value;
            }
        }
        throw std::out_of_range("Key not found");
    }

    size_t size() const {
        return numElements;
    }

    bool contains(const KeyType& key) const {
        size_t bucketIndex = getBucketIndex(key);
        for (const auto& kv : buckets[bucketIndex]) {
            if (kv.key == key) {
                return true;
            }
        }
        return false;
    }

    // 추가적인 메서드 (삭제, 크기 조절 등)를 구현할 수 있습니다.
};