[알고리즘/자료구조] 힙(Heap)
·
Algorithm/이론
📒 힙(heap)완전 이진 트리(Complete Binary Tree)최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙 (루트가 가장 작음)최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 (루트가 가장 큼) 📒 힙 자료구조 구현heapq 모듈 이용heapq.heappush(heap, item): item을 heap에 추가heapq.heappop(heap): heap에서 가장 작은 원소를 popreturn 하지 않고 접근만 하려면 인덱스로 접근heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환함 ✏️ heapq 모듈을 이용하여 최소 힙 구현heapq 모듈은 기본적으로 최소 힙으로 구현되어 있음import heapqheap = []heapq.h..
[Python] 백준/BOJ 1715번: 카드 정렬하기 (Gold 4)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + ..
[Python] 백준/BOJ 1655번: 가운데를 말해요 (Gold 2)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠 때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 💡 Approach백준이가 숫자를 하나씩 말할 때마다 지금까지 나온 수들 중에 중간값을 말해야 한다.지금까지 나온 숫자의 개수가 홀수면 가운데 값, 짝수면 ..
[Python] 백준/BOJ 23757번: 아이들과 선물 상자 (Silver 2)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 상훈이는 N개의 선물 상자를 가지고 있다. 선물 상자에는 현재 담겨있는 선물의 개수가 적혀있다.선물을 받을 아이들이 M명 있다. 아이들은 각자 1에서 M까지의 서로 다른 번호를 하나씩 부여받았다. 1번 아이부터 M번 아이까지 한 번에 한 명씩, 현재 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물을 가져간다. 이때, 앞서 누군가 선물을 가져갔던 선물 상자에서 또다시 가져가도 상관없다.하지만 상자에 자신이 원하는 것보다 적은 개수의 선물이 들어있다면, 선물을 가져가지 못해 실망한다.상훈이는 한 명이라도 실망하지 않고 모두가 선물을 가져갈 수 있는지 궁금하다. 💡 Approachheapq 모듈을 활용하여 최대 힙을 구현했다.최대 힙의 경우 최소 힙과 동일하게 구..
[Python] 백준/BOJ 1927번: 최소 힙 (Silver 2)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다. 💡 Approachheapq 모듈 활용하여 최소 힙을 구현했다. ✏️ Solutionimport sysimport heapqinput = sys.stdin.readlinen = int(input())heap = []for _ in range(n): x = int(input()) if x == 0: print(heapq.heappop(heap) if heap else 0) else: ..