[코테] 알고리즘 공부 Cheat sheet - 0 (자료구조)

Cheat sheet 1 부터 쓰기 시작했는데, 기본 자료 구조 정리를 안해서 이번 편은 0 이라고 썼습니다..

파이썬 자료 구조 간단 정리 !

 

 

리스트

파이썬에서 가장 많이 쓰는 동적 배열 자료구조

순서가 있다.

자유로운 추가 append 삭제 remove 검색in my_list, my_list.index(val)

다양한 자료형 및 중복 허용

in 의 용도를 이해하는게 중요하다. 리스트 같은 반복 가능한 객체를 순회하는 용도 (for .. in ..)로도 쓰이지만, 이러한 시퀀스 객체 내 존재하는 요소인지 확인하는 데에도 쓰인다.

존재 여부를 확인할 때에는 .index() 가 아닌 in 연산자를 쓰면 된다

 

# 생성
my_list = [1, 2, 3, 4, 5]

# 추가
my_list.append(6)

# 접근
value = my_list[0]  # 1

# 삭제
my_list.remove(3)  # 값이 3인 요소 삭제

# 개수
size = len(my_list)

# 검색 (index)
index = my_list.index(target_value)

# 검색 (in)
print(7 in my_list)   # False

# 검색 (in + if 조건)
print([value for value in my_list if value < 3])   # [1,2]

 

 

C++ 및 자바에서 봤던 자료구조인 벡터, 스택등을 리스트로 구현해보자

 

 

벡터 - paired 형식을 리스트에 넣으면 됨

v = []
v.append((1,2))
v.append((3,4))
print(len(v))
# 2
for p in v:
	print(p)
#(1,2)
#(3,4)

 

 

스택 - 그냥 리스트로 구현 후,  접근시 my_list[-1],  삭제시 my_list.pop(-1) 으로 빼면 된다.

(python 에서 음수 인덱스는 리스트나 문자열에서 역순으로 접근을 가능하게 하는 방법)

s = []
s.append(1)
s.append(2)
s.append(3)
print(len(s))
# 3
while len(s) > 0 :
	print(s[-1])
    s.pop(-1)
# 3
# 2
# 1

 

큐

큐 - deque 를 쓰자. thread safe 한 Queue 보다 빠름.  앞, 뒤로 넣고 빼고 다 됨

append(값), appendleft(값), pop(), popleft()

from collections import deque 후 deque() 로 선언

 

from collections import deque

q = deque()
q.append(1)
q.appendleft(2)
q.pop()
q.popleft()

 

우선순위 큐를 써야할 땐? - heapq 를 쓰자. 

import heapq

pq = [1,2,8]

heapq.heappush(pq, 6)
while pq:
	print(heapq.heappop(pq))
# 1
# 2
# 6
# 8

위와 같이 파이썬의 heapq 는 기본이 최소 힙(min heap) 이므로, 최대 힙은 아래와 같이 편법으로 사용 가능하다.

from heapq import heappush, heappop
import heapq

nums = [1,2,6,8]

### 방법 1
heap = []

for num in nums:
	heappush(heap, (-num, num)) # (우선순위, 값) pair 값을 넣더라도 앞자리부터 소팅해주는 점을 이용한 것
  
while heap:
	print(heappop(heap)[1])
# 8
# 6 
# 2
# 1

### 방법 2
max_heap = [-num for num in nums]

heapq.heapify(max_heap)

while max_heap:
    print(-heappop(max_heap))
# 8
# 6 
# 2
# 1

 

맵

맵 - 키, 값으로 이루어진 구조

immutable 한 객체면 (int 같은 값. 그리고 tuple 은 됨) 키로 쓸 수 있다

• 선언은 {} 나 dict() 로 가능
• 추가 my_dict["키"] = value, 읽기 my_dict["키"] 으로 가능
• 순서는 보장안된다고 생각하면 됨
• for key in my_dict 하면 키카 튀어나옴
• for val in my_dict.values() 하면 값이 튀어나옴
• for k, v in my_dict.items() 하면 둘 다 튀어나옴
• 'key' in my_dict : 유무 True/False
• 삭제 del my_dict['key']