Python 코딩테스트 대비 자료구조 및 기능 정리

저번에 이어서 코딩 테스트를 할 때 자주 사용하는 기능들을 다음 블로그를 참고하여 정리해보았습니다!

https://covenant.tistory.com/143?category=874690 

🔥 용감하게 시작하는 코딩테스트 3편

 

1.  조합

순열은 다음과 같은 방식으로 구할 수 있습니다. 우선 import를 해주시고

combinations 앞에 리스트를 먼저 두고, 뒤에 뽑을 개수를 지정하는 식으로 사용합니다.

from itertools import combinations  

print(list(combinations([1, 2, 3, 4], 3)))
# [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

 

2.  순열

순열도 조합과 비슷합니다.

combinations 앞에 리스트를 먼저 두고, 뒤에 뽑을 개수를 지정하는 식으로 사용합니다.

from itertools import permutations  

print(list(permutations([1, 2, 3], 2)))
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

 

3.  힙

(1) 최소 힙

최소 힙은 루트가 가장 작은 값으로 이루어진 힙입니다.

파이썬의 heapq는 최소 힙으로 구현되어 있습니다.

heapq를 import 한 후, heappush로 추가할 수 있고, heappop으로 삭제할 수 있습니다.

여기서 삭제되는 값은 루트 값입니다.

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 8)
heapq.heappush(heap, 6)

print(heap)
# [1, 3, 6, 5, 8, 10]

heapq.heappop(heap)
print(heap)
# [3, 6, 5, 8, 10]

(2) 최대 힙

최대 힙은 루트가 가장 큰 값으로 이루어진 힙입니다.

heapq가 최소 힙으로 구현되어 있다는 점을 이용하여

입력할 때 -1을 곱해서 heap에 넣고 출력할 때 -1을 곱해서 출력하는 식으로 구현할 수 있습니다.

# 예시입니다.

import heapq

heap = []
heapq.heappush(heap, -3)
heapq.heappush(heap, -1)
heapq.heappush(heap, -10)
heapq.heappush(heap, -5)
heapq.heappush(heap, -8)
heapq.heappush(heap, -6)

print(heap)
# [-10, -8, -6, -1, -5, -3] 

print(heapq.heappop(heap) * -1)
# 10

 

4.  덱

저는 파이썬에서 큐를 사용할 때 덱을 사용하는데요, 스택을 사용할때도 덱이 쓰인다고 합니다.

덱은 양방향에서 데이터를 처리할 수 있습니다.

from collections import deque 
deq = deque()

덱에 데이터를 추가하는 방법은 두가지 입니다.

deq.append(10) # 덱의 오른쪽에 데이터를 삽입
deq.appendleft(10) # 덱의 왼쪽에 데이터를 삽입

 

데이터를 삭제하는 방법도 두 가지입니다.

deq.pop(10) # 덱의 오른쪽의 데이터를 삭제
deq.popleft(10) # 덱의 왼쪽의 데이터를 삭제

 

 

5.  빈도 계산

Counter를 통해서 빈도를 계산할 수 있습니다.

배열 안에는 튜플로 있고, 0번째 인덱스에는 arr의 숫자, 1번째 인덱스에는 arr에 등장 빈도수가 들어가 있습니다.

from collections import Counter 

arr = [1, 1, 1, 2, 2, 3, 4, 5]
val = Counter(arr).most_common() 
print(val)
# [(1, 3), (2, 2), (3, 1), (4, 1), (5, 1)]