Beelog

programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 문제는 위와 같으며, 이 문제는 최소힙을 사용하여 해결할 수 있습니다. 힙(Heap)이란, 최솟값 또는 최댓값을 빠르게 찾기 위한 완전이진트리 형태로 만들어진 자료구조입니다. 완전이진트리는 모든 노드의 차수를 최대 2로 제한한 이진트리에서 1. 마지막 노드를 제외한 모든 노드가 채워져 있어야 하고 2. 모든 노드가 왼쪽부터 채워져 있어야 한다는 조건을 추가로 만족..

www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제는 위와 같으며, 이 문제의 경우 위상 정렬에 대해 알고있다면 쉽게 문제를 해결할 수 있습니다. 위상 정렬(Topology Sort) 란, 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 정해주기 위해 사용하는 알고리즘입니다. 만약 위와 같은 순서대로 일이 진행되어야 한다면, 순서대로 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 이런 순서대로 진행을 하..

www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제는 위와 같으며 크기가 가장 작은 카드 묶음들을 먼저 합쳤을 때, 비교 횟수가 가장 적다는 점을 이용하여 문제를 해결할 수 있습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin import heapq heap = [] n = int(stdin.readline()) for _ in range(n): bundle = int(stdin.readline()) heapq.h..

www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net 문제는 위와 같으며 최소 힙을 구현할 수 있으면 쉽게 풀 수 있는 문제입니다. 또한 파이썬에서는 heapq 라이브러리를 통해 문제를 보다 쉽게 실수 없이 해결할 수 있습니다. 먼저 파이썬에서 heapq 를 사용한 코드를 살펴보면 다음과 같습니다. from sys import stdin import heapq n = int(stdin.readline()) heap = [] for _ in range..