백준 13975https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데,www.acmicpc.net풀이 전 나의 생각파일의 정보가 주어지고, 두개의 파일을 합치고 최종적으로 하나의 파일로합칠 때 나올 수 있는 비용 중 최솟값을 구해야 한다. 조건- K (3 ≤ K ≤ 1,000,000)- 파일의 크기는 10,000을 초과하지 않는다. 과정이 문제에서 중요한 것은 어떻게 파일을 합치면최소 비용을 구할 수 있을 지 알아야 한다. 이를 위해선 최소가 되지 않는 경우를 한 번 살펴보..
알고리즘 및 자료구조/우선순위 큐
백준 11279https://www.acmicpc.net/problem/11279 11279번: 최대 힙첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0www.acmicpc.net풀이 전 나의 생각자료구조 최대 힙을 사용하여 다음과 같은 연산을 지원하는 프로그램을 작성해야 한다.배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.조건- N(1 ≤ N ≤ 100,000) - 자연수는 231보다 작다. 과정N이 10만까지 가능하기 때문에 최대 힙을 사용하여 최대값을 찾아내는자료구조인 우선순위 큐를 사용하여 문..
백준 2075 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 전 나의 생각 N x N의 표가 주어질 때, 모든 수는 자신의 한 칸 위에 있는 수보다 크다. 이때, N번째로 큰 수를 찾아야 한다. 조건 - N(1 ≤ N ≤ 1,500) - 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수 과정 이 문제는 메모리 제한이 12MB기 때문에 N의 정보를 모두 넣어서 풀려고하면 메모리 초과가 발생한다. 이를 인지하고 설명을 보면 모..
백준 1927 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이전 나의 생각 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 이 연산을 최소 힙 자료구조를 사용하여 진행해야 한다. 조건 - N(1 ≤ N ≤ 100,000) - x는 2^31보다 작은 자연수 또는 0 과정 이 문제에서 요구하는 것은 최소 힙을 사용하여 최솟값 구하는 것이다. 그러면 최소 힙을 사용하는 자료구조 중..
백준 1715 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 전 나의 생각 정렬된 묶음의 숫자 카드가 주어질 때 두 묶음 하나로 만드는 A + B 과정을 거쳐서 만들 수 있는 최소 비교 횟수를 구해야 한다. (A + B 번 비교) 조건 - 1 ≤ N ≤ 100,000 - 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수 과정 문제를 빠르게 훑어보고 넘어갔다면 잘못 이해할 수 도 있는 문제다. 문제의 예시를 보면..
백준 11286 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 전 나의 생각 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 이러한 조건을 만족하는 절댓값 힙에 연산 N이 주어졌을 때, 출력되는 결과를 구해야 한다. 조건 - N(1≤N≤100,000) - ..
