백준 11279번, 1927번 - 최대, 최소 힙

2021. 7. 4. 22:16· 백준 문제풀이(파이썬)/우선순위 큐

 

11279번 문제는 최대 힙, 1927번 문제는 최소 힙을 이용하여 각각 최댓값, 최솟값을 구하는 문제이다. 두 문제 모두 등호만 다를 뿐 코드는 같기 때문에, 더 어려울 수 있는 최소 힙을 풀겠다. 그전에 힙에 대해 알아보자.

 

힙이란, 우선순위 큐를 위한 자료구조이자, 다른 알고리즘에 비해 최댓값, 최솟값을 빠르게 구하게 해준다. 또한 힙은 반 정렬 상태이다. 처음에 우선순위 큐와 힙에 대해서 혼동이 왔었다. 내가 알던 큐는 처음에 들어온 것이 제일 먼저 나가는 FIFO형태였는데, 우선순위에 따라 먼저 나간다는 개념이 낯설었다.

 

힙은 우선순위 큐를 구현하기 위한 도구(?)이고, 또한 힙은 반 정렬 상태라는 것을 알고 나니 이해가 됐다. 반 정렬 상태라는 건 트리안의 모든 수가 정렬이 되어있는 것이 아니고 어느 정도만 정렬이 되어있다는 것이다. 밑의 그림은 힙에 값을 삽입하는 과정이다. 배열의 마지막에 붙여준 뒤에 부모 노드로 계속 올라가면서, 본인보다 작으면 서로 교체되는 식으로 진행이 된다. 그러면, 루트에는 언제나 가장 큰 (혹은 작은) 값이 올 것이다. 

 

 

반대로, 삭제하는 과정은 루트 노드를 삭제한 뒤, 배열의 가장 마지막 원소를 루트에 넣어주고, 자식 노드들을 거쳐가면서 갱신해준다. 삽입과 삭제의 과정은 거의 비슷하다고 할 수 있다. 

부모 노드의 인덱스는 자식의 인덱스를 2로 나눈 값이고, 자식 노드의 인덱스는 left child인 경우 부모 노드의 인덱스 * 2, right child인 경우 부모 노드의 인덱스 * 2 + 1 임을 이용하면 쉽게 문제를 풀 수 있다.

 

##함수 선언 부분
import sys
##변수 선언 부분
min_heap = []
cnt = 0
##메인 함수 부분
if __name__ == "__main__":
    N = int(sys.stdin.readline())
    min_heap = [-1] *100010
    for i in range(N):
        command = int(sys.stdin.readline())
        if command == 0:
            if cnt == 0: #들어있는 것이 없으면,
                print(0) #0출력
            else:
                print(min_heap[1])
                min_heap[1] = min_heap[cnt]
                min_heap[cnt] = -1 #pop후 저장
                cnt -= 1
                index = 1
                while index*2 <= cnt:
                    if (index*2+1) > cnt: #left child만 있는 경우에는
                        if min_heap[index] > min_heap[index*2]: #left child값보다 크면,
                            tmp = min_heap[index] #교환
                            min_heap[index] = min_heap[index * 2]
                            min_heap[index * 2] = tmp
                            index *= 2
                        else: 
                            break
                    elif min_heap[index] > min(min_heap[index*2],min_heap[index*2+1]): #자식 노드의 최솟값보다 크면,
                        if min_heap[index*2] < min_heap[index*2+1]: #left child가 더 작으면,
                            tmp = min_heap[index] #교체
                            min_heap[index] = min_heap[index*2]
                            min_heap[index*2] = tmp
                            index *= 2
                        else:
                            tmp = min_heap[index]
                            min_heap[index] = min_heap[index*2+1]
                            min_heap[index*2+1] = tmp
                            index = index * 2 + 1
                    else:
                        break

        else:
            cnt += 1 #원소 개수 증가
            min_heap[cnt] = command 
            index = cnt
            while index > 1: #index부터 1보다 작아질 떄 까지 2로 나누어서 부모 노드로 이동
                if min_heap[index] < min_heap[index//2]: #부모모다 작으면
                    tmp = min_heap[index] #교체
                    min_heap[index] = min_heap[index//2]
                    min_heap[index//2] = tmp
                index //= 2

input()을 사용해서 시간 초과가 떴다. 앞으로 시간 초과가 나오면, sys.stdin.readline()을 먼저 의심해봐야겠다.

저작자표시 (새창열림)

'백준 문제풀이(파이썬) > 우선순위 큐' 카테고리의 다른 글

백준 1655번 - 가운데를 말해요  (0) 2021.07.10
'백준 문제풀이(파이썬)/우선순위 큐' 카테고리의 다른 글
  • 백준 1655번 - 가운데를 말해요
aodtns
aodtns
인생은 새옹지마
맹의 코딩 기록장인생은 새옹지마
aodtns
맹의 코딩 기록장
aodtns
전체
오늘
어제
  • 카테고리 (116)
    • BE (22)
      • JSP (6)
      • Spring Boot (12)
      • Node.js (1)
      • Docker (1)
      • JPA (1)
    • AI (12)
      • 머신 러닝(ML) (11)
      • 딥 러닝(DL) (1)
    • 네트워크 (7)
      • 네트워크 기본 (1)
      • AWS (6)
    • DB (1)
      • SQL (1)
    • FE (11)
      • HTML (4)
      • CSS (5)
      • JS (1)
      • React (1)
    • CS (1)
      • Back End (0)
      • 디자인패턴 & 방법론 (1)
      • 컴퓨터 구조 & 운영체제 (0)
    • VCS (1)
    • 기획(UI, UX) (1)
      • 소프트웨어 마에스트로 (1)
    • 이코테 (13)
      • 그리디 (1)
      • 구현 (1)
      • DFS, BFS (1)
      • 정렬 (7)
      • 이진 탐색 (1)
      • 다이나믹 프로그래밍 (1)
      • 최단 경로 (0)
      • 그래프 이론 (0)
      • 부록 (1)
    • 백준 문제풀이(파이썬) (44)
      • 기본 수학 1 (1)
      • 기본 수학 2 (4)
      • 재귀 (2)
      • 브루트 포스 (2)
      • 정렬 (0)
      • 백트래킹 (5)
      • 동적 계획법 1 (15)
      • 그리디 알고리즘 (3)
      • 정수론 및 조합론 (2)
      • 스택 (1)
      • 큐, 덱 (1)
      • 분할 정복 (4)
      • 이분 탐색 (2)
      • 우선순위 큐 (2)
    • 일상 (3)

블로그 메뉴

  • 💼 깃허브
  • 📄이력서

인기 글

최근 글

hELLO · Designed By 정상우.v4.2.1
aodtns
백준 11279번, 1927번 - 최대, 최소 힙
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.