heapq 3

[백준/python] 1927번 최소 힙 - heapq 기능 정리

1. 문제우선순위 큐, 힙큐를 활용하여 풀어야 하는 문제. 2. 풀이heapq의 기본적인 동작, heappush와 heappop만 활용하면 되는 문제이다. - heapq.heappush(배열 이름, 원소)- heapq.heappop(배열 이름) 이 두 가지만 알면 이 문제를 쉽게 풀 수 있다.단, 평소에 사용하던 기본 리스트나 deque의 사용법과는 좀 달라서 주의가 필요하다. 3. 코드import heapqimport sysinput = sys.stdin.readlinen = int(input())arr = []for i in range(n): x = int(input()) if x == 0: if len(arr): print(heapq.heappop(arr)..

[백준/python] 20665번 독서실 거리두기

1. 문제 독서실에서 원하는 자리를 이용 가능한 시간을 구하는 문제다.1, 2번 규칙에 따라 새로 온 사람이 이용하는 좌석을 파악해 문제를 해결해야 한다. 2. 풀이1. 0900 ~ 2100 이라는 숫자로 나오지만 이걸 분 형태로 바꿔주어야 계산이 편함 (아니면 9시 ~ 10시가 100분이 됨..!)2. 사람들이 선호하는 좌석을 구하는 함수 만들기3. heapq를 사용하여 새로운 사람이 오면 추가하고 visited를 True로 바꾸어주기4. 정답은 720에서 시작해서 자리를 사용할 수 없는 시간 만큼 빼기1. max_dist, best_seat 변수 초기화2. 1부터 n+1까지 돌려서 각각 좌석 번호에 대하여, 이미 방문하지 않은 경우에만 실행3. left_dist, right_dist를 무한대로 초기화..

[백준/python] 16948번 데스 나이트 (bfs vs heapq)

1. 문제 이 문제는 데스 나이트라는 새로운 말이 이동할 수 있는 위치를 정의하여시작 칸에서 도착 칸으로 이동하는 최소 이동 횟수를 구하는 문제다.2. 풀이지난주에 풀었던 7562번 나이트의 이동 문제와 비슷하다.그 때는 bfs를 사용해서 문제를 해결했는데 다른 문제를 풀면서heapq의 빠른 속도를 체감하고 새로운 방법으로 문제를 풀었다. 먼저 나이트가 움직일 수 있는 위치를 dx, dy 배열 안에 넣어준다.move 함수를 만들어 방문 여부를 체크할 수 있는 배열과우선순위 큐 적용을 위한 (cnt, r, c) 튜플을 넣은 배열을 만들어준다.시작하는 위치의 방문여부를 True로 설정하고 다익스트라 알고리즘에 따라 코드를 짰다.만약 도착 지점에 갔다면 cnt를 리턴해준다.나이트가 갈 수 있는 모든 방향에 대..