후회가 없도록

문제 출처: https://www.acmicpc.net/problem/1655 1. 결과 메모리 35032KB, 시간 272ms 2. 풀이 이 문제는 N개의 숫자가 각각 입력될 때마다, 입력된 숫자들 중에서 중간값을 출력해야 한다. 평균값이나 누적 합이 아니기 때문에 각각의 값이 살아서 존재해야 하고, 값이 새로 입력될 때마다 정렬이 수행되어야 중간값을 구할 수 있다. 하지만 값이 추가될 때마다 정렬(sort)이 발생하고, 이런 과정이 N번 반복된다면 시간 복잡도는 커질 수밖에 없다. 이를 더 효율적인 방법으로 풀기 위해서는 최대 힙과 최소 힙을 함께 응용하는 방법이 있다. 우선, 최대 힙과 최소 힙이 의미하는 바를 이해해야 하는데, 최대 힙은 [0] 번째 원소부터 내림차순으로 저장 혹은 출력되는 자료구..

문제 출처: https://www.acmicpc.net/problem/11279 1. 결과 메모리 35124KB, 시간 152ms 2. 풀이 이 문제는 우선순위 큐를 이용해서 풀 수 있는 문제다. 먼저, 우선순위 큐란 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형을 이야기하는데, 쉽게 보면 자료형에 자료를 저장할 때, 스스로 각 자료에 우선순위를 부여하며 저장하는 것이다. 그리고 자료를 다시 하나씩 출력할 때, 그 우선순위가 높은 것을 먼저 순서대로 출력하는 것인데, 자세한 내용은 아래 링크의 글을 통해 확인할 수 있다. https://chanhuiseok.github.io/posts/ds-4/ 자료구조 - 우선순위 큐(Priority Queue)와 힙(heap) 컴퓨터/IT/알고리즘 정리 블로그 ..

우선순위 큐란, 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형을 의미한다. 비선형 구조를 갖는 자료구조인데, 배열이나 연결 리스트로도 구현할 수 있지만 출력과 원소를 찾고 삭제하는 과정 등이 비효율적이기 때문에, 보통은 힙(Heap)을 통해 구현한다. 그리고 파이썬에서는 heapq 라이브러리를 이용해서 힙의 연산을 이용할 수 있다. 1. 힙(Heap) 우선, 힙이란 완전 이진 트리(Complete Binary Tree)이고, 모든 노드에 저장된 값들은 자식 노드들의 값보다 작거나 같다. 여기서 값의 크기가 작을수록 큰 우선순위를 부여하는 것이라고 생각하면 된다. 즉, 배열을 정렬했을 때 기본적으로 오름차순 정렬되는 것처럼 일반적인 힙에서는 루트 노드(우선순위가 가장 높은 노드)가 값이 가장 작다. ..