코딩 테스트 대비 개념 정리 - Python

힙(heap)

힙 생성, 원소 추가, 삭제

파이썬 heqpq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

import heapq

# 빈 리스트에 heap 형식으로 추가
heap = []
heapq.heappush(heap, 50) # 빈 heap에 50 추가
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

# 리스트를 heap으로 변환하기
heap2 = [50 ,10, 20]
heapq.heapify(heap2)

# heap에서 원소 삭제
result = heapq.heappop(heap)

 

최대 힙 만들기

문제를 풀다보면 최솟값을 찾는 문제도 있지만 최댓값을 찾는 유형도 꽤 있다.

이때 최대 힙을 만드는 방법을 알고 있다면 수월하게 문제를 풀 수 있다.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)

 

위 결과를 사용하게 될때 (-9, 9) , (-7, 7) ... (-1, 1) 순서대로 뽑아 쓸 수 있기 때문에 1번 index를 추출해주면 최대 힙이 된다.

 

큐(queue)

큐(queue)는 선입선출, FIFO(First In First Out) 기반의 매우 유명한 자료구조이다.

큐를 사용하면 데이터를 추가한 순서대로 제거할 수 있기 때문에 자주 사용한다.

일반 큐는 list를 사용할 때 사용하지만 리스트의 제일 왼쪽을 제거하거나 추가할 때 deque를 사용할 때가 있는데 정말 유용하다.

from collections import deque

queue = deque([4, 5, 6])
queue.append(7)
queue.append(8)

print(queue) # deque([4, 5, 6, 7, 8])

queue.popleft() # 4
queue.popleft() # 5

print(queue) # deque([6, 7, 8])

 

위는 deque.popleft()를 사용해 리스트의 가장 왼쪽에 있는 값, 즉 가장 먼저 들어온 값을 제거하는 방법이다.

 

🎱지금까지 pop은 리스트의 가장 오른쪽 값만 제거해주는 줄 알았지만....!

a = [1,2,3,4]
print(a.pop(1))
print(a) #[1,3,4]

 

위의 예시와 같이 특정 index 값을 제거해줄 수 있었다,,,,! 

이것은 코딩테스트를 준비하다가 새로 알게된 사실이다...

from collections import deque

queue = deque([4, 5, 6])
queue.appendleft(3)
queue.appendleft(2)
print(queue)  # deque([2, 3, 4, 5, 6])

queue.pop()
queue.pop()
print(queue)  # deque([2, 3, 4])

 

위는 deque.appendleft()를 사용하여 리스트의 가장 왼쪽에 값을 추가하는 방법이다.

 

for - else 문

for i in range(5):
    print(i, end=' ')
else:
    print("for문이 끝까지 실행됐습니다!")

# 결과 : 0\n 1\n 2\n 3\n 4\n "for문이 끝까지 실행됐습니다!" 

for i in range(5):
    if i == 2:
        break
    print(i, end=' ')
else:
    print("for문이 끝까지 실행됬습니다!")
# 결과 : 0\n 1\n