코딩 테스트를 위해 꼭 알아야 할, Python 문법 정리

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/

[파이썬] heapq 모듈 사용법

https://leonkong.cc/posts/python-deque.html

Python - 데크(deque) 언제, 왜 사용해야 하는가?