Root(√), 이용훈

Root(√), 이용훈

C++, Java, Python, Software Engineer

3 minute read

실무에서는 거의 사용되지 않음.. 인터뷰 준비하는 생각으로 공부하자.

list

  • insertion과 removal에서 O(1)의 시간 복잡도
  • 하지만 fast random access는 지원하지 않음

기본적인 사용법

#include <list>

int main(int argc, char const *argv[])
{
    std::list<int> nums{1,2,3,4,5};
    for (auto num:nums) {
        std::cout << num << " ";
    }
    std::cout << std::end;
    }
    
    return 0;
}
  • 위의 코드에서 nums 변수는 stack 공간에 size, 포인터 두 개(first, last)의 정보를 가지고 있음. 그리고 힙 공간에 int 5개 공간을 확보하고 first와 last를 가리킴.
  • 또한, 원소 1은 2를 가리키고 , 2는 3을 가리킴
  • 그리고, 3은 2를 가리키고, 2는 1을 가리킴.
  • 즉, doubly linked list임

emplace, find 등의 시간 복잡도

#include <list>

int main(int argc, char const *argv[])
{
    std::list<int> nums{1,2,3,4,5};
    
    nums.emplace_back(6);
    nums.emplace_front(0); // 이렇게 앞 뒤로 집어넣는 것도 가능
    
    auto it = std::find(nums.begin(), nums.end(),3); // 처음부터 끝까지 돌면서 3이라는 원소의 위치를 반환
    if (it != nums.end())
    {
        nums.emplace(it,100);
    }
    // emplace, emplace_back, emplace_front는 모두 O(1)의 시간 복잡도를 가짐
    
    
    for (auto num:nums) {
        std::cout << num << " ";
    }
    std::cout << std::end;
    }
    
    return 0;
}
  • emplace, emplace_back, emplace_front는 모두 O(1)의 시간 복잡도를 가짐
  • 하지만 find는 O(n)의 시간 복잡도를 가진다.

forward_list

  • C++ 11부터 도입
  • insertion, removal이 O(1)의 시간 복잡도
  • singly-linked list로 구성되어있음
  • fast random access는 지원하지 않는다
  • space는 list에 비해서 적게 차지한다.

기본적인 사용법

#include <algorithm>
#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> nums{1,2,3,4,5};
    
    num.emplace_front(0); // 리스트와 다르게 emplace_back은 사용 불가
    
    
    for (auto num:nums) {
        std::cout << num << " ";
    }
    std::cout << std::end;
    }
    
    return 0;
}

vector vs list

  random access I/D I/D@back find
vector O(1) O(n) O(1) O(n)
list O(n) O(1) O(1) O(n)
  • 표를 보면 어떤 경우에는 상황에 따라 list를 써도 될 것 같고, vector를 써도 될 것 같다.
  • 하지만, 실무에서는 99% vector를 사용할 것임
  • 하지만 vector의 find가 list보다 훨씬 빠르다. 메모리 공간은 실제로 격자 구조인데, vector의 경우 연속되어있고, list는 3개씩(data, pointer 두 개) 이곳저곳에 저장되어있다. vector는 순차적으로 access하면 되고, 그 뒤에 딸려오는 공간이 모두 메모리의 cache 안에 들어가게 된다. 그렇다면 한 벅의 clock 안에 memory access가 가능하다는 뜻이다. 그렇기 때문에 똑같이 O(n)의 시간 복잡도를 가져도 find가 더 빠르다.
  • 또한 병렬 프로그래밍으로 list를 구현하기도 어렵다. 병렬 계산을 할 때 코어 별로 메모리 할당하기가 어렵기 때문이다. 이곳저곳 산재해있기 때문에.. 반면에 vector는 연속적인 자료형이기 때문에 분할하기가 쉽다.

stack

  • first-in, last-out, 택배 상하차 같다랄까..
  • 입구와 출구가 하나 밖에 없다.

기본적인 사용법

#include <iostream>
#include <stack>

using namespace std;

int main(void) {
    stack<int> s;
    s.push(7);
    s.push(5);
    s.pop(); //pop은 return 값이 없이 그냥 삭제만. 
    s.push(6);
    s.push(1);
    s.pop();
    while(!s.empty()) {
        cout << s.top() << ' ';
        s.pop();      
    }
    return 0;
}

queue

  • firist-in, last-out, 은행 창구 같다랄까.. 중간에 새치기 불가

기본적인 사용법

#include <iostream>
#include <queue>

using namespace std;
int main() {
    queue<int> q;
    q.push(7);
    q.push(5);
    q.push(4);
    q.pop();
    q.push(6);
    q.pop();
    
    while (!q.empty() {
        cout << q.front() << ' ';
        q.pop();
    }
    return 0;
}

priority queue (우선순위 큐)

  • 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
  • 데이터를 우선순위에 따라 처리하고 싶을 때 사용
자료구조 추출되는 데이터
스택(stack) 가장 나중에 삽입된 데이터
큐(queue) 가장 먼저 삽입된 데이터
우선순위 큐(priority queue) 가장 우선순위가 높은 데이터

우선순위 큐를 구현하는 방법

  • 우선순위 큐를 구현하는 방법은 다양하다.
    1. 단순히 리스트(list)를 이용하여 구현
    2. 힙(heap)을 이용하여 구현
      1. 데이터의 개수가 N일 때, 구현 방식에 따라서 시간 복잡도가 달라진다.
우선순위 큐 구현 방식 삽입 시간 삭제 시간
리스트 O(1) O(N)
힙 O(logN) O(logN)
  • 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙 정렬)
    • 이 경우 시간 복잡도는 O(NlogN)

힙(heap)의 특징

  • 완전 이진 트리 자료구조의 일종
    • 완전 이진트리란 루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오르녹 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미
  • 힙에서는 항상 루트 노드(root node)를 제거. 우선순위가 root node임
  • 최소 힙(min heap)
    • 루트 노드가 가장 작은 값을 가짐
    • 따라서 값이 작은 데이터가 우선적으로 제거
  • 최대 힙(max heap)
    • 루트 노드가 가장 큰 값을 가짐
    • 따라서 값이 큰 데이터가 우선적으로 제거

우선순위 큐 라이브러리를 이용한 힙 정렬 구현 예제

#include <bits/stdc++.h>

using namespace std;

void heapSort(vector<int>& arr) {
    priority_queue<int> h;
    // 모든 원소를 차례대로 힙에 삽입
    // c++에서는 큰 수에 우선순위로 하기 때문에 오름차순 정렬을 할 때 데이터를 넣을 때와 뺄 때 -를 붙여서 정렬을 수행
    for (int i=0; i<arr.size(); i++) {
        h.push(-arr[i]);
    }
    // 힙에 삽입된 모든 원소를 차례대로 꺼내어 출력
    while (!h.empty()) {
        printf("#d\n", -h.top());
        h.pop();
    }
}
int n;
vector<int> arr;

int main() {
    cin  >> n;
    for (int i=0; i<n; i++) {
        int x;
        scanf("%d", &x);
        arr.push_back(x);
    }
    heapSort(arr);
}

참고자료 : 코드없는프로그래밍, 동빈나

You may also enjoy