자료구조(배열, 연결리스트, 스택, 큐, 맵, 집합)

배열

- 배열 탐색 속도 : O(1)

배열은 임의접근(random access)를 통해 빠르게 탐색 가능 => 탐색 속도 O(1)
ex) arr[2]에 접근 위해서는 => arr 배열 시작 주소 + 2(인덱스)*4byte(int 크기) = arr[2]의 메모리 주소값

- 배열 삽입/삭제 속도 : O(N)

삽입/삭제는 O(N)으로 탐색보다 느린데 

왜냐하면 삽입/삭제를 위해서는 나머지 인덱스의 값들을 움직여야 하기 때문에 

최소 0개~최대 N개를 미뤄야 하므로 시간복잡도가  O(N)

 

연결리스트(Linked List)

- 연결리스트 탐색 속도 : O(N)

연결리스트는 배열과 달리 임의접근 불가 

n번째 인덱스에 가기 위해서는 n개의 노드를 거쳐야 하므로 O(N)으로 탐색 속도 느림

- 연결리스트 삽입/삭제 속도 : O(1) 

삽입/삭제는 해당 인덱스의 노드들의 링크만 삭제하거나 이어주면 되기 때문에 O(1) 으로 빠른 편

- 연결 리스트 종류

연결 리스트

이중 연결 리스트

원형 이중 연결 리스트

 

스택(Stack)

- 스택 삽입/삭제 속도 : O(1)

선입후출(FILO), 후입선출(LIFO)

파이썬에서는 리스트로 구현

C++에서의 top() = Python에서의 s[-1]

(collections.deque로도 구현 가능)

큐(Queue)

- 큐 삽입/삭제 속도 : O(1)

선입선출( FIFO), 후입후출(LILO) 

Python에서 Queue모듈은 속도가 느리기 때문에 코딩테스트에서는 deque(double-dended quese) 사용

from collections import deque
 
q = deque()
q.append(20)
q.append(30)
q.append(40)
 
print(q)    # deque([20, 30, 40])
 
while len(q) > 0 :
    print(q.popleft())  # 20\n30\n40
 
print(q)    # deque([])

 

https://docs.python.org/ko/3/library/collections.html#collections.deque

collections — Container datatypes

 

 

 

 

우선순위 큐 Priority Queue(Heap)

- 우선순위 큐 삽입/삭제 속도 : O(log N)

인큐할 때 데이터에 유선순위 부여해 추가, 디큐할 때 우선순위가 가장 높은 데이터 꺼내는 방식

O(log N) : O(N)보다는 빠르고 O(1)보다는 느리지만 충분히 빠른 성능

이진트리 형태

루트노드의 값이 최댓값/최솟값인지에 따라 => C++ : max-heap / Python : min-heap

pop()하면 항상 root node가 pop 됨

pq[0]=  root node

Python에서 Priority Queue모듈 있으나 속도가 느리기 때문에 코딩테스트에서는 heapq 사용

import heapq
 
pq = []
 
heapq.heappush(pq, 2)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
 
print(pq)           # [1, 2, 3]
 
while pq:
    print(pq[0])    # 1\n2\n3\n
    heapq.heappop(pq)
 
print(pq)           # []

 

 

 

 

 

맵 Map(Dictionary)

Key, Value로 구성

key(중복x) value(중복o)

- 맵 삽입/삭제 속도 : C++ O(log N)  / Python O(1)

Python은 구현 방법이 Hash

C++은 구현 방법이 red-black tree - tree형태는 시간복잡도가 O(log N)

m = {}
 
m['A'] = 10
m['B'] = 20
m['C'] = 30
 
print(m)    # {'A': 10, 'B': 20, 'C': 30}
 
for k in m:
    print(k, m[k])
# A 10
# B 20
# C 30

 

 

 

 

 

집합(Set)

중복 x

- 집합 삽입/삭제 속도 : C++ O(log N) / Python O(1)

s = set()
 
s.add(10)
s.add(20)
s.add(30)
 
print(s)    # {10, 20, 30}
 
s.remove(20)
 
print(s)    # {10, 30}