알고리즘 유형 분석 - 자료구조

✅ 자료구조

▶️ 배열 Array

• 삽입/삭제 : $O(N)$ → 삽입 및 삭제를 위해 N개의 인덱스 요소를 뒤로 or 앞으로 옮겨주는 과정 필요
  • 삽입/삭제 위치에 따라 뒤쪽일수록 시간 복잡도가 적게 소요될 수 있으나, Big-O 산정 기준 : Worst Case
• 탐색 : $O(1)$ → 배열에는 index가 존재하므로 임의 접근(random access) 가능
• C++에서는 size 변경 불가

// C++
int arr[4] = {10, 11, 12, 13};
arr[2] = 5;

• Python : 리스트 사용

arr = [1, 2, 3, 4]
arr[2] = 7

▶️ 벡터 Vector

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

// C++
vector<pair<int, int>> v;
v.push_back(make_pair(123, 456));
v.emplace_back(789, 987);
printf("size: %d\n", v.size());
for (auto p : v)
    printf("%d, %d\n", p.first, p.second);

# Python
v = [] # list
v.append((123, 456))
v.append((789, 987))
print("size : ", len(v)) # size : 2 → (123, 456), (789, 987) 쌍으로 이루어짐
for p in v:
    print(p)

▶️ 연결 리스트 Linked List

• 삽입/삭제 : $O(1)$ → Link를 변경해주고 해당 노드를 삽입/삭제하면 끝
• 탐색 : $O(N)$
  → index 개념이 존재하지 않으며, 각 노드는 [data, link] 형태이므로 N번째 노드를 찾기 위해서는 N개의 노드 방문 필요
• PS에서는 자주 사용되지 않지만 다른 자료구조들을 구현할 때 많이 쓰임

▶️ 스택 Stack

• 후입선출 (LIFO : Last Input First Out)
  • 선입후출 (FILO : First Input List Out)
• 삽입/삭제 : $O(1)$

// C++
stack<int> s;
s.push(123);
s.push(456);
s.push(789);
printf("size: %d\n", s.size());
while(!s.empty()) {
    printf("%d\n", s.top());
    s.pop();
}

• Python : 그냥 리스트

# python
s = []
s.append(123)
s.append(456)
s.append(789)
print("size: ", len(s))
while len(s) > 0:
    print(s[-1])
    s.pop(-1)

▶️ 큐 queue

• 선입선출 (FIFO : First Input First Out)
• 삽입/삭제 : $O(1)$

// C++
queue<int> q;
q.push(123);
q.push(456);
q.push(789);
printf("size: %d\n", q.size());
while(!q.empty()) {
    printf("%d\n", q.front());
    q.pop();
}

# Python 1
from collections import deque # collections의 deque를 사용해 queue를 구현 (Queue에 비해 시간비용 ↓)
q = deque()
q.append(123) # 값 추가
q.append(456)
q.append(789)
# q.appendleft() : 왼쪽, 앞에 값을 넣게 됨
print("size: ", len(q))
while len(q) > 0:
    print(q.popleft()) # q.poplift() : 왼쪽, 앞부터 값을 빼게 됨
# q.pop() : 오른쪽, 뒤에서 값을 빼게 됨

# Python 2
from queue import Queue 
# thread-safe한 기능을 포함하기에 시간 초과 확률 ↑ 
# 멀티스레드에서의 안정성이 필요하지 않은 알고리즘 문제에서는 사용을 지양할 것 

q = Queue()
q.put(123)
q.put(456)
q.put(789)
while q:
    print(q.get())

▶️ 우선순위 큐 Priority Queue (Heap)

• root node에 가장 큰 값이 들어있는 경우 : max-heap (C++ 기본 제공)
• root node에 가장 작은 값이 들어있는 경우 : min-heap (Python 기본 제공)
• 삽입/삭제 : $O(logN)$
  • 이진트리의 경우 시간복잡도를 $log$의 형태로 가지는 경우가 많음

// C++ : max-heap
priority_queue<int> pq;
pq.push(456);
pq.push(123);
pq.push(789);
printf("size: %d\n", pq.size());
while (!pq.empty()) {
    printf("%d\n", pq.top());
    // 789 456 123
    pq.pop(); // 값을 빼내기만 할 뿐, 반환되는 값은 없음
}

# Python sol 1
# Python : min-heap
import heapq

pq = []
heapq.heappush(pq, 456)
heapq.heappush(pq, 123)
heapq.heappush(pq, 789)
print("size: ", len(pq))
while len(pq) > 0:
    print(heapq.heappop(pq)) # 123 456 789

# Python sol 2
from queue import PriorityQueue
# PriorityQueue는 thread-safe한 성격을 가지고 있기에 시간 소요 ↑
# 따라서 heapq를 사용하는 것을 지향

pq = PriorityQueue()
pq.put(6)
pq.put(10)
pq.put(-5)
pq.put(0)
pq.put(8)
while not pq.empty():
    print(pq.get()) # C++의 pop과 같은 역할이나 빼온 값을 반환해 출력해줌
    # -5 0 6 8 10

▶️ 맵 Map (Dictionary)

• Key와 Value를 가짐
  - Key : 중복 허용 X
  - Value : 중복 허용 O
  
  

• C++ : Map - 삽입/삭제 : $O(logN)$

  • red-black tree로 이루어짐

// C++
map<string, int> m;
m["jaewon"] = 54;
m["hyejin"] = 49;
m["jimin"] = 24;
m["hayeon"] = 20;
m["bambi"] = 7;
printf("size: %d\n", m.size());
for (auto p : m)
    printf("%d, %d\n", p.first(), p.second());

• Python : Dictionary - 삽입/삭제 : $O(1)$
  • hash로 이루어짐

# Python
m = {}
m["jaewon"] = 54
m["hyejin"] = 49
m["jimin"] = 24
m["hayeon"] = 20
m["bambi"] = 7
print("size: ", len(m))
for k in m:
    print(k, m[k])

▶️ 집합 Set

• 중복 허용 X
• C++ 삽입/삭제 : $O(logN)$

// C++
set<int> s;
s.insert(456);
s.insert(12);
s.insert(456);
s.insert(7890);
s.insert(7890);
s.insert(456);
printf("size: %d\n", s.size());
for (auto i : s)
    printf("%d\n", i);
// 3
// 456 12 7890

• Python 삽입/삭제 : $O(1)$

# Python
s = set()
s.add(456)
s.add(12)
s.add(456)
s.add(7890)
s.add(7890)
s.add(456)
print("size: ", len(s))
# s.pop() → 임의의 값을 삭제 (자주 사용하지 않음)
# s.remove(12) → 인자로 전달받은 값을 삭제
for i in s :
    print(i)
# 3
# 456 12 7890