꾸준히 개발하기

여러 곳에서 두루두루 쓰이는 파이썬의 자료구조에 대해서 정리해보자.

1. 해시

key-value 로 이루어진 데이터를 저장하는 자료구조. 조회가 매우 빠르다!

파이썬에서는 dict() 자료구조로 구현 가능하다.

딕셔너리는 다음과 같은 구조다. { key1: value1, key2:value2, ... }

빈 딕셔너리를 만들 때 {} 기호로 만들어주면 된다.

딕셔너리의 value에 접근하는 방법은 인덱스에 키 값을 적어주면 된다. 새로운 데이터를 추가할 때도 동일하다.

dictionary = {"name":"jibok"}
print(dictionary[name])
dictionary["age"] = 3

딕셔너리의 요소를 삭제할 때는 del 함수를 사용해주면 된다.

del dictionary["age"]

주의할 점은 key는 고유한 값이므로 중복되는 key값이 들어가게 되면 하나를 제외한 나머지 것들은 모두 무시된다. 고유한 key를 조회함으로써 value를 빠르게 가져오는 장점이 사라지는 행위이므로 하지 말자!

또한 key에 들어갈 수 있는 자료구조는 immutable한 요소만 가능하다. 가령 수정이 가능한 리스트는 안되고 수정이 안되는 튜플은 key로 쓸 수 있다. 

딕셔너리에서 제공하는 유용한 함수들은 다음과 같다.

• keys() : 모든 key를 리턴해준다. * dict_keys() 객체 자체를 돌려주는데 for문 등은 사용 가능하다. 만약 리스트로 값을 써야한다면 list(tmpDict.keys()) 로 변환해주자.
• values() : 모든 value를 리턴해준다.
• items() : key-value 쌍을 튜플로 묶은 값을 리턴해준다. 
• clear() : 안의 데이터 모두 지우기 (key, value 모두)
• get(key) : key에 대응되는 value값을 리턴해준다. 인덱스로 접근하는 것과 동일한 기능인데, 차이가 존재한다. 만약 없는 키값으로 접근했을 때 get 함수는 None을 리턴해주고, 인덱스는 에러를 발생시킨다.
• key in _ : 해당 딕셔너리 안에 key가 있는지 True/False값을 리턴해준다.

2. 스택

후입선출(Last In First Out)의 자료구조이다. 파이썬에서 기본적으로 제공해주는 list() 자료구조를 사용하면 된다.

자료구조의 가장 끝에서만 삽입, 삭제가 이루어진다.

• append() : 리스트의 맨 뒤에 삽입
• pop() : 리스트 맨 뒤의 요소를 꺼내어 리턴

* 맨 앞의 요소에 접근해서 빼려는 시도를 하면 O(N)의 시간복잡도를 가진다. 이런 경우 뒤에서 소개하는 deque 자료구조를 써야 시간 효율적이다.

3. 큐

선입선출(First In First Out)의 자료구조이다. 다양하게 구현하나 코딩테스트를 볼 땐 주로 collections 모듈의 deque를 사용하는 편이다.

from collections import deque
queue= deque()

위와 같이 선언하여 사용한다.

4. 덱

맨앞, 맨뒤에서 모두 자료의 삽입,삭제가 이루어질 수 있는 큐이다. collections 모듈의 deque를 사용한다. 하단의 메소드는 모두 O(1)의 시간복잡도를 가진다. 

• append() : 오른쪽 끝에 삽입
• appendleft() : 왼쪽 끝에 삽입
• pop() : 오른쪽 끝 요소를 꺼내어 리턴
• popleft() : 왼쪽 끝 요소를 꺼내어 리턴

from collections import deque

dq= deque()

dq.append(3)
dq.appendleft(2)
dq.pop()
dq.popleft()

5. 힙

최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료구조로 완전 이진트리이다.

자식 노드의 key 값 < 부모 노드의 key 값 : 최대 힙

자식 노드의 key 값 > 부모 노드의 key 값 : 최소 힙

우선순위에 따라 데이터가 정렬되어 있으므로, 가장 우선순위가 높거나/낮은 요소가 루트 노드에 존재한다. heapq 모듈을 사용한다. heapq 모듈은 리스트를 최소 힙처럼 다뤄준다. 따라서 빈 리스트를 선언하여 매번 넘겨줘야 한다.

• heapq.heappush( heap, item ) : heap에 item 삽입
• heapq.heappop( heap ) : heap에서 가장 작은 원소를 꺼내어 리턴

import heapq
hq = []
heapq.heappush(hq, 1)
heapq.heappop(hq)

기본적으로 heapq 모듈은 최소 힙으로 동작한다. 따라서 최대 힙을 구현해줄 때는 item에 '-'를 붙여 간단하게 구현한다.

여기까지 많이 쓰이는 자료구조는 한번 짚고 넘어간다. 문제 딱 보면 무슨 자료구조 써야되는지, 문법은 뭔지 더 이상 헷갈리지는 말자!