배열 (Array)

int arr[4] = {1,2,3,4}

• 삽입/삭제 : O(N)
• 탐색 : O(1)
• c++에서는 size 변경 불가

벡터 (Vector)

• 삽입/삭제 : O(N)
• 탐색 : O(1)
• 동적 배열 (size 변경 가능)

연결 리스트 (Linked list)

연결 리스트

• 삽입/삭제 : O(1)
• 탐색 : O(N)
• Problem Solving에서는 별로 안쓰이지만 다른 자료구조들을 구현할 때 많이 쓰인다
• 면접에서 배열과 연결 리스트의 장단점을 많이 물어봄
  • 탐색 많은건 배열, 삽입삭제 많은건 연결리스트

스택 (Stack)

• 삽입/삭제 : O(1)
• 특성 : LIFO(후입선출), FILO(선입후출)

큐 (Queue)

• 삽입/삭제 : O(1)
• 특성 : FIFO(선입선출), LILO(후입후출)

우선순위 큐 (Priority Queue / Heap)

• 이진트리 형태로 되어있음

• 삽입/삭제 : O(logN)

• max/min-heap : 트리에서 가장 큰 값 or 가장 작은 값만 조회할 수 있음 (c++에서 기본 힙은 max-heap)

  • 최대힙

    		priority_queue<int, vector<int>> q;

    int는 큐에 들어갈 데이터의 타입을 말한다.
    vector는 데이터들이 들어갈 컨테이너이다. 실제로는 이곳에 int 데이터들이 저장된다. 하지만 동작을 우선순위 큐 처럼 하게 하기 위해서 priorty_queue 타입으로 감싼 것이라고 보면 된다.

  • 최소힙

    		priority_queue<int, vector<int>, greater<int>> q;

    ⭐️ 다른 방법 : 최대힙에 음수로 바꾸어 넣어주고 뺄 때 다시 음수를 붙여준다 -> 최소힙과 같은 효과
    

• heap sort : 우선순위 큐에 담으면 자동으로 정렬되는 효과를 볼 수 있음

  • 수를 넣으면서 그때그때 최댓값을 반환해야하는 문제라면 배열이나 벡터는 넣을때마다 정렬해야하지만 우선순위 큐는 정렬을 해주지 않아도 되므로 편리하다.

맵 (Map / Dictionary)

• Key(중복 불가능), Value(중복 가능)
• 삽입/삭제 : O(logN)

집합 (Set)

• 중복을 허용하지 않고 자료를 저장
• 삽입/삭제 : O(logN)