알고리즘 유형 1. 자료구조 (파이썬)

 

1. 배열 Array

 

기본 자료형인 리스트를 배열처럼 사용합니다.

 

	시간 복잡도
임의 접근	O(1)
삽입 / 삭제	O(N)

 

 

 

 

2. 스택 Stack

 

기본 자료형인 리스트를 스택처럼 사용합니다.

stk = []

stk.append(x) #리스트의 맨 뒤에 요소를 삽입합니다.
stk.pop() #리스트의 맨 뒤 요소를 반환하고 삭제합니다. (괄호 안을 비워뒀을 경우)

스택은 한 쪽에서만 데이터를 넣고 뺄 수 있는 자료구조입니다.

이러한 스택의 특징을 FILO(First-In-Last-Out) 또는 LIFO(Last-In-First-Out)라고 부릅니다.

 

	시간 복잡도
삽입 / 삭제	O(1)

 

 

 

 

3. 덱 Deque

 

덱을 import해서 사용합니다.

from collections import deque

dq = deque()

dq.append(x) #덱의 오른쪽 끝에 요소를 추가
dq.pop() #덱의 오른쪽 끝에 있는 요소를 반환하고 삭제

dq.appendleft(x) #덱의 왼쪽 끝에 요소를 추가
dq.popleft() #덱의 왼쪽 끝에 있는 요소를 반환하고 삭제

덱은 양 쪽 모두에서 데이터를 넣고 뺄 수 있는 자료구조입니다.

 

	시간 복잡도
삽입 / 삭제	O(1)

 

 

※ 큐 Queue

 

큐는 한 쪽에서는 데이터를 넣을수만 있고, 다른 한 쪽은 데이터를 뺄 수만 있는 자료구조입니다.

이러한 큐의 특징을 FIFO(First-In-First-Out) 또는 LILO(Last-In-Last-Out)라고 부릅니다.

 

큐 모듈은 멀티스레딩 환경까지 고려해서 동작하기 때문에 속도가 느립니다.

따라서 알고리즘 문제를 풀 때는 큐 대신 덱을 사용하길 권장합니다.

큐가 할 수 있는 일은 모두 덱이 할 수 있습니다.

 

 

 

 

 

4. 우선순위 큐 Priority Queue

 

힙을 import해서 사용합니다.

import heapq

h = []

heapq.heappush(h, x) #힙에 요소 추가
heapq.heappop(h) #힙의 루트 노드에 있는 요소 삭제

우선순위 큐는 내부적으로 힙(heap)이라는 완전이진트리로 구성되어 있습니다. 힙의 루트 노드에는 '언제나' 데이터들 중 최댓값 또는 최솟값이 담겨 있습니다.

 

힙의 루트 노드에 언제나 최댓값이 담겨 있는 힙을 최대힙(max-heap)이라고 부르며,

힙의 루트 노드에 언제나 최솟값이 담겨 있는 힙을 최소힙(min-heap)이라고 부릅니다.

 

파이썬에서 기본적으로 heapq는 최소힙입니다.

최대힙을 사용하고 싶다면 heapq에 데이터를 넣기 전에 전부 부호를 반대로 바꿔서 넣으면 순서가 뒤집혀 저장되므로 최대힙처럼 사용할 수 있게 됩니다. pop 한 값은 다시 부호를 바꾸면 원래의 값을 얻을 수 있습니다.

 

	시간 복잡도
삽입 / 삭제	O(log N)

 

 

 

 

5. 맵 Map

 

기본 자료형인 딕셔너리를 맵처럼 사용합니다.

 

	시간 복잡도
삽입 / 삭제	O(1)

 

 

 

 

 

6. 집합 Set

 

기본 자료형인 집합을 사용합니다.

 

	시간 복잡도
삽입 / 삭제	O(1)

 

 

 

 

7. 그래프 Graph

 

그래프는 아래 포스팅을 참고해주세요.

 

(파이썬) 알고리즘 유형 4. 그래프