크래프톤정글 2주차; TIL 3 - 힙, 힙 정렬, 우선순위 큐, 파이썬 deque, 파이썬 print 함수 옵션

2022-11-07

힙 & 힙 정렬 & 우선순위 큐의 개념

출처:https://www.boostcourse.org/cs113/lecture/540275
https://www.edwith.org/intro-data-and-algo-2-2018/lecture/21489?isDesc=false
https://www.edwith.org/intro-data-and-algo-2-2018/lecture/21491/?isDesc=false
https://jackpot53.tistory.com/6

무엇?

heap 구조는 배열이면서 완전 이진 트리(complete binary tree)로 시각화가 가능하고,
왼쪽부터 다음 인덱스의 노드를 채워 간다.
이러한 힙 구조를 유지하면서 부모 노드가 자식 노드보다 항상 큰 값을 가진다면 최대 힙, 반대로 항상 작은 값을 가진다면 최소 힙!
heap은 컴퓨터 사이언스 강의 들으면서 메모리의 구조에 대해 공부할 때, 스택 영역, 힙 영역 하면서 같이 나왔던 용어인데 그거랑은 다른 개념인가보다!

왜?

힙 구조는 정렬과 우선순위 큐 자료구조를 구현하는데 효율적
시간 복잡도 면에서 장점이 있음.

어떻게?

실생활에서 우선순위 큐를 사용하는 예

출처: https://stackoverflow.com/questions/18049847/when-would-i-use-a-priority-queue
https://jackpot53.tistory.com/6

무엇?

응급실에서 환자의 우선순위를 매겨 진료할 때, VVIP 고객을 대응할 때

왜?

어떻게?

백준 18258번 큐2에서 파이썬 deque 사용하기

출처: https://velog.io/@kjhxxxx/백준-18258번-큐2-Python

무엇?

collections라는 파이썬 빌트인 모듈이 있는데, list, tuple, dict에 대해 확장 자료구조를 제공함.
그 중 deque는 스택과 큐를 모두 지원함(신기하다)
'덱’이라고 읽는다.

왜?

큐1 문제도 있는데, 여기서는 파이썬의 기존 리스트를 이용해도 문제가 없었다.
큐2 에서는 시간초과가 발생했다.
deque는 파이썬의 기존 리스트보다 효율적인 메모리 구조로 자료 저장면에서 더 빠르다고 함(연결 리스트 방식)

어떻게?

from collections import deque
조심할 것은 일반 리스트처럼 deque.pop(0)을 하면 Type Error을 띄움.
이유는 deque에는 deque.pop()과 deque.popleft() 의 두 가지 pop 메소드가 있고 둘 다 인자를 받지 않음.
전자는 stack의 pop이고 후자가 queue의 pop임!

파이썬 출력 함수 print의 옵션 sep, end

출처:https://gilu-world.tistory.com/40

무엇?

sep은 출력 값들 사이에 넣을 내용을 표시하고,
end는 출력 값의 마지막에 넣을 내용을 표시함(기본적으로 "\n"라는 개행 문자가 들어가 있음)

왜?

요세푸스 문제의 출력이 <1, 2, 3, 4, 5>와 같은 식이었는데,
일반 리스트 출력 형식([1, 2, 3, 4, 5])으로 하면 틀림!
이런 출력 형식을 맞춰주기 위해 필요하다.

어떻게?

개행하지 않고 연달아 표시하기 위해서 end="" 옵션을 사용함
조금 복잡해보이지만

print("<", end="")
for i in range(len(josephus)-1):
    print(f"{josephus[i]}, ", end="")
print(josephus[-1], end="")
print(">", end="")