기록방

👉 문제링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 🔸 문제 분석 🔸 카드 묶음들을 합칠때 최소 비교 횟수를 출력한다. 🔸 문제 풀이 🔸 작은 묶음부터 합쳐야 최소값이 나오는걸 문제에서 확인할 수 있으므로, 그리디 알고리즘으로 접근해 우선순위 큐를 이용하여 풀이한다. 두 최소값 원소를 뽑아 그 합을 정답에 누적하고, 다시 그 합을 우선순위 큐에 넣는다. 우선순위 큐의 원소가 1개가 남을 때 까지 반복한다. 합으로 만들어진 새 묶음이 기존 묶음보다 클 수 있음에 유의한다. 🔸 코드 🔸 i..

👉 문제링크 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 🔸 문제 분석 🔸 N x N 인 배열 A가 있고, A[i][j] = ixj 이다. 일차원 배열 B에 A를 넣고 오름차순 정렬했을 때, B[k]를 구한다. 배열 인덱스는 1부터 시작한다. 🔸 문제 풀이 🔸 배열 A의 원소들 중 중앙값 보다 작은 수들의 개수를 세며 이진 탐색을 통해 풀이한다. 중앙값 보다 작은 수들이 K보다 작다면, 시작 인덱스를 중앙값 +1 로 변경한다. 중앙값보다 작은 수들이 K이상이라면, 마지막 인덱..

👉 문제링크 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 🔸 문제 분석 🔸 N개의 영상을 M개의 블루레이에 나눠 저장하려고 한다. 하나의 블루레이 크기의 최소값을 구한다. 🔸 문제 풀이 🔸 블루레이 크기를 이진 탐색으로 찾는다. 최소 크기는 N개의 영상 중 최대값 최대 크기는 N개의 영상의 총합 중앙값을 시작으로 M개의 블루레이에 모두 저장할 수 있으면 크기를 줄여보고, 모두 저장할 수 없으면 저장 크기를 늘려보는 식으로 탐색한다. 🔸 코드 🔸 import java.io.*; import java.util.Str..

👉 문제링크 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 🔸 문제 분석 🔸 플로이드-워셜 알고리즘의 기초 문제이다. 🔸 문제 풀이 🔸 단방향 가중치 연결 그래프에서 모든 경로에 대한 최단 거리를 구한다. 🔸 코드 🔸 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..

👉 문제링크 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 🔸 문제 분석 🔸 N개의 수로 이루어진 수열을 버블 소트로 정렬했을 때, swap이 총 몇 번 발생하는지 출력한다. 🔸 문제 풀이 🔸 N이 50만까지 가므로 O(nlogn)의 알고리즘을 사용해야 한다. 여기서는 병합 정렬(Merge Sort)을 사용한다. 버블 소트는 1칸씩 이동할 수 있으므로, 정렬 후 바뀐 인덱스의 크기를 모두 더하면 된다. 병합 정렬에서 기존 인덱스보다 앞 인덱스로 옮길 때, 그 크기를 누적해서 출력한다...