1. heapq
binary tree 기반의 min heap 자료구조를 제공한다.
- import 방법
import heapq
- 특징
heap을 만들어주는 것이 아니라, list 내부의 값들을 min-heap의 성질대로 배치 해준다!
아래와 같이 먼저 heap으로 사용할 list를 만들어 주거나, 이미 만들어진 list를 힙의 성질대로 재배치할 수 있다.
#새로 heap을 위한 리스트를 만들거나
heap = []
#또는 힙으로 사용할 기존에 사용하던 리스트가 있어야함
heap = [ 1, 2, 3, 4, 5 ]
- 힙 원소 추가
heapq.heappush( 리스트, 추가할 원소 )
heap = []
heapq.heappush(heap, 14)
heapq.heappush(heap, 11)
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
print(heap)
[1, 5, 11, 14]
가장 작은 원소인 1이 가장 앞으로 왔습니다. 해당 인덱스를 기준으로 이진트리를 그리면 다음과 같은 모습입니다.
- 힙에서 노드 삭제(pop)
힙의 특징 처럼 가장 작은 head 노드가 삭제되며 리턴되고, 다시 힙의 성질에 맞게 재정비 됩니다.
heapq.heappop( )
node = heapq.heappop(heap)
print(node)
print(heap)
1 #print(node)
[5, 14, 11] #print(heap)
만약 삭제하지 않고 최솟값만 얻고 싶다면 그냥 heap list의 0번째 인덱스를 인덱싱 해오면 됩니다 => heap[0]
- 기존 리스트를 힙으로 변환하기
heapq.heapify( 변환할 리스트 )
heap1 = [4,5,1,2]
heapq.heapify(heap1)
print(heap1)
[1, 2, 4, 5] #print(heap1)
신기한 것이, 라이브러리가 무척 똑똑하여 이중 리스트나 튜플도 앞의 요소를 기준으로 힙을 만들어 준다.
heap2 = [[5,2],[3,1],[1,1],[2,6],[0,4]]
heapq.heapify(heap2)
print(heap2)
[[0, 4], [2, 6], [1, 1], [5, 2], [3, 1]] #print(heap2)
- max-heap 만드는 법
위에서 설명한 것 처럼 리스트나 튜플을 삽입하더라도 0번째 요소로 힙을 만들어준다.
즉, 0번째 요소로 마이너스 값을 넣으면 min-heap으로 max-heap을 만들수 있다.
import heapq
heap = [4, 5, 1, 2, 12, 9]
max_heap = [(-num, num) for num in heap]
print(max_heap)
heapq.heapify(max_heap)
print(max_heap)
# 첫번째 출력 결과
[(-4, 4), (-5, 5), (-1, 1), (-2, 2), (-12, 12), (-9, 9)]
# 힙 적용 후 출력 결과, 가장 큰 12가 가장 앞에 오는 것을 볼 수 있다
[(-12, 12), (-5, 5), (-9, 9), (-2, 2), (-4, 4), (-1, 1)]
대신 pop() 할 때, 마이너스가 안 붙은 노드[1] 값을 쓰도록 주의하자!
힙정렬, 다익스트라 등등 사용도가 많기 때문에 꼭 암기해놓자!
2. defaultdict
- import 방법
from collections import defaultdict
- 특징
Dictionary 를 만들 때, 그런 경험 있을 것이다. 이미 key 값이 존재하면 1을 더해주고 존재하지 않으면 1을 넣어줘!
defaultdict 를 이용하면 위 로직을 코딩해줄 필요 없이 자동으로 가능하다.
존재하지 않으면 뭐를 넣어줄 지는 처음 defaultdict instance 를 선언할 때 결정된다.
from collections import defaultdict
int_dict = defaultdict(int)
list_dict = defaultdict(list)
set_dict = defaultdict(set)
print(int_dict)
print(list_dict)
print(set_dict)
# 출력 결과
defaultdict(<class 'int'>, {})
defaultdict(<class 'list'>, {})
defaultdict(<class 'set'>, {})
각각 아무 값도 존재하지 않을 경우 int, list, set을 넣어주겠다는 뜻!
int의 경우 0, list는 [], set은 set() 을 default 값으로 시작한다.
대표적인 예제들을 보면 바로 이해가 갈 것이다.
- defaultdict(int) 사용 예제
from collections import defaultdict
int_dict = defaultdict(int)
name = "woongstudioinsydney"
for i in name:
int_dict[i] += 1
print(int_dict)
# 출력 결과
defaultdict(<class 'int'>, {'w': 1, 'o': 3, 'n': 3, 'g': 1, 's': 2, 't': 1, 'u': 1, 'd': 2, 'i': 2, 'y': 2, 'e': 1})
- defaultdict(list) 사용 예제
from collections import defaultdict
list_dict = defaultdict(list)
names = [('kim', 'woongs'), ('kim', 'jamin'), ('kim', 'jamin'), ('hwang', 'chulsoon'), ('park', 'jongwoo'), ('hwang', 'woojins')]
for family, last in names:
list_dict[family].append(last)
print(list_dict)
# 출력 결과
defaultdict(<class 'list'>, {'kim': ['woongs', 'jamin', 'jamin'], 'hwang': ['chulsoon', 'woojins'], 'park': ['jongwoo']})
위 예제는 중복된 이름 'jamin' 이 모두 추가 되는 것을 볼 수 있다. 이를 처리하고 싶으면 set을 이용한다.
- defaultdict(set) 사용 예제
from collections import defaultdict
set_dict = defaultdict(set)
names = [('kim', 'woongs'), ('kim', 'jamin'), ('kim', 'jamin'), ('hwang', 'chulsoon'), ('park', 'jongwoo'), ('hwang', 'woojins')]
for family, last in names:
set_dict[family].add(last)
print(set_dict)
# 출력 결과
defaultdict(<class 'set'>, {'kim': {'woongs', 'jamin'}, 'hwang': {'woojins', 'chulsoon'}, 'park': {'jongwoo'}})
이처럼 defaultdict 의 int 는 숫자를 count 할 때, list 와 set은 실제 어떤 값이 들어가는 지 저장해야 할 때 (그 중에서도 set은 중복을 무시할 때) 유용하게 사용된다.
3. deque
- import 방법
from collections import deque
- 특징
파이썬에서 list 는 문자열과 같은 sequence 자료형이다. element가 저장되는 위치마다 index 값이 존재한다. 문제는! 값을 추가하거나 빼게 되면 index 값이 모두 재 조정되야 한다는 점이다.
예를 들어서 0 => a , 1=> b, 2=> c 로 리스트가 저장되어 있는데, a를 빼면 0=>b, 1=> c 로 재조정 되야할 것이다. 특히 맨 앞과 맨뒤에서의 값 추가 삭제가 비효율적인 편! 이를 개선하기 위해 Double Linked List 방식으로 양끝에 값을 추가하고 제외하는 것을 O(1) 시간으로 가능하도록 해주는 것이 deque() 이다!
주로 리스트를 이용하여 queue 나 stack 을 구현하기 위해 사용된다.
- deque 정의 방법
deq = deque()
# or 이미 존재하는 리스트를 넣어도 된다.
deq = deque([1, 2, 3, 4, 5, 6])
- deque 메소드
- deque.append(item): item을 데크의 오른쪽 끝에 삽입.
- deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입.
- deque.pop(): 데크의 오른쪽 끝 값을 제외하고 그 값을 Return 한다.
- deque.popleft(): 데크의 왼쪽 끝 값을 제외하고 그 값을 Return 한다.
- deque.extend(array): 주어진 배열을 순서대로 데크의 오른쪽에 추가한다.
- deque.extendleft(array): 주어진 배열을 순서대로 데크의 왼쪽에 추가한다.
- deque.remove(item): item을 데크에서 찾아 삭제한다.
- deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽). 맨 끝 값을 오른쪽으로 회전시키면 맨 앞으로 오겠지!?
4. sort 와 sorted
- 특징
파이썬에서 list 의 정렬은 위 두가지 방법이 존재한다. 문법이 조금 다르지만 같은 메소드이다.
(추가예정)
5. list의 shallow copy와 deep copy, list comprehension
- 특징
(추가예정)
6. lambda 함수
(추가예정)
7. iterable 함수 ( map(), zip(), fliter() )
(추가예정)
8. Permutation, Combination
(추가예정)
참고블로그
https://www.daleseo.com/python-heapq/
https://leonkong.cc/posts/python-deque.html
'알고리즘' 카테고리의 다른 글
[웅's 프로그래머스] 기능개발 - 파이썬(python) 풀이 (0) | 2021.09.25 |
---|---|
[웅's 프로그래머스] 등굣길 - 파이썬(python) 풀이 (0) | 2021.09.22 |
[웅's 프로그래머스] 정수 삼각형 - 파이썬(python) 풀이 (0) | 2021.09.22 |
[웅's 프로그래머스] N으로 표현 - 파이썬(python) 풀이 (0) | 2021.09.22 |
[웅's 프로그래머스] 체육복 - 파이썬(python) 풀이 (0) | 2021.09.22 |