파이썬 자료구조

아래는 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프)

6, 7, 8, 9강을 요약한 코드입니다.(섹션 3: PART 2. 알고리즘 유형 분석 - 자료구조 개념강의)

 

# 배열, 벡터, 연결리스트
# 1. 배열
# 삽입/삭제 : O(N)
# 탐색 : O(1)
print("\n1. 배열")
arr = [10, 11, 12, 13]
print(arr)
arr[2] = 5
print(arr)

# 2. 벡터 (c++ 동적배열)
# 삽입/삭제 : O(N)
# 탐색 : O(1)
print("\n2. 벡터(동적배열)")
v = []
v.append((123, 456))
v.append((789, 987))
print("size:", len(v))
print(v)
for p in v:
    print(p)

# 3. 연결 리스트
# 삽입/삭제 : O(1)
# 탐색 : O(N)
# 다른 자료구조를 구현할 때 많이 쓰인다. 
print("\n3. 연결 리스트")


# 스택, 큐
# 1. 스택 Stack
# 삽입/삭제 : O(1)
# 선입후출
print("\n1. 스택")
s = []
s.append(123)
s.append(456)
s.append(789)
print("size:", len(s))
print("s : ", s)
while len(s) > 0:
    print("s[-1] : ", s[-1])
    s.pop(-1)

# 2. 큐 Queue    
# 삽입/삭제: O(1)
# 선입선출
from collections import deque

q = deque()
q.append(123)
q.append(456)
q.append(789)
print("\n2. 큐")
print("size:", len(q))
print("q : ", q)
while len(q) > 0:
    print("q.popleft() : ", q.popleft())

q.append(123)
q.append(456)
q.append(789)
while len(q) > 0:
    print("q.pop() : ", q.pop())


# 우선순위 큐
# 1. 우선순위 큐 Priority Queue (Heap)
# C++:max-heap, Python:min-heap
# 삽입/삭제: O(logN)

import heapq

pq = []
heapq.heappush(pq, 456)
heapq.heappush(pq, 123)
heapq.heappush(pq, 789)
print("\n1. 우선순위 큐 Priority Queue ")
print("size:", len(pq))
print("pq : ", pq)
while len(pq) > 0:
    print("heapq.heappop(pq) : ", heapq.heappop(pq))
    
    
# 맵, 집합
# 1. 맵 Map (Dictionary)
# Key, Value
# 삽입/삭제 C++ O(logN), python O(1)

m = {}
m["key1"] = 40
m["key2"] = 100
m["key3"] = 50
print("\n1. 맵 Map (Dictionary) ")
print("m : ", m)
print("size: ", len(m))
for k in m:
    print(k, m[k])
    
    
# 2. 집합 Set
# 중복 X
# 삽입/삭제 c++ O(logN), python O(1)

s = set()
s.add(456)
s.add(12)
s.add(456)
s.add(7890)
s.add(7890)
s.add(456)
print("\n2. 집합 Set ")
print("s : ", s)
print("size : ", len(s))
for i in s:
    print(i)
s.remove(12)
print("after s.remove(12) : ", s)