힙 (5) 썸네일형 리스트형 [백준] 1916번 최소비용 구하기 [Python] - 그래프 이론 도시의 수: N, 버스의 수: M와 정보: $($A -> B, 버스 비용$)$, 출발 도시: S, 도착 도시: E에 대한 정보가 주어질 때, 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 문제 더보기 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N$(1 ≤ N ≤ 1,000)$이 주어지고 둘째 줄에는 버스의 개수 M$(1 ≤ M ≤ 100,000)$이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주.. [백준] 7662번 이중 우선순위 큐[Python] - 자료구조 k개의 명령어와 정수가 주어진다. I는 삽입, D는 삭제를 의미하는 연산 I n: n을 큐에 삽입 D 1: 최댓값 삭제 D -1: 최솟값 삭제 모든 연산 후 큐에 남아있는 최댓값과 최솟값을 출력, 큐가 비어있으면 'EMPTY'를 출력하는 문제 큐가 비어있을 때, 명령어 D는 무시하면 됨 더보기 문제 이중 우선순위 큐$($dual priority queue$)$는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산$($operation$)$ 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데.. [백준] 11286번 절댓값 힙 [Python] - 자료구조, 힙 0이 아닌 숫자를 배열에 저장 0일 경우 배열 내 절대값이 가장 작은 값 출력 및 제거 절대값이 같은 숫자가 여러 개일 경우 최소값에 대해서 진 위 연산을 구현하는 문제 더보기 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x.. [백준] 11279번 최대 힙 [Python] - 자료구조, 힙 0이 아닌 숫자를 배열에 저장 0일 경우 배열 내 최댓값 출력 및 제거 위 연산을 구현하는 문제 더보기 문제 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다. 출력 입력.. [백준] 1927번 최소 힙 [Python] - 자료구조, 힙 0이 아닌 숫자를 배열에 저장 0일 경우 배열 내 최솟값 출력 및 제거 위 연산을 구현하는 문제 더보기 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N$(1 ≤ N ≤ 100,000)$이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는$($추가하는$)$ 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또.. 이전 1 다음