기록방

👉 문제링크 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🔸 문제 분석 🔸 기본 문자열과 폭발 문자열이 입력된다. 기본 문자열에서 폭발 문자열 부분이 폭발하며 지워지고, 남은 문자열은 다시 이어 붙는다. 더 폭발할 문자열이 남지 않았을 상태의 문자열을 출력한다. 남은 문자가 없으면 "FRULA"를 출력한다. 🔸 문제 풀이 🔸 문자열의 길이가 100만이기 때문에 O(n^2) 미만의 알고리즘을 사용해야 한다. 반복문 한 번에 계산할 수 있도록 한다. 새로운 문자열이 생기면 메모리 문제가 생길 수..

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

👉 문제링크 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칸씩 이동할 수 있으므로, 정렬 후 바뀐 인덱스의 크기를 모두 더하면 된다. 병합 정렬에서 기존 인덱스보다 앞 인덱스로 옮길 때, 그 크기를 누적해서 출력한다...

👉 문제링크 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 🔸 문제 분석 🔸 배열에 자연수를 넣거나, 배열의 최대값을 꺼내출력하는 연산이 100,000번까지 주어진다. 최대값을 빠르게 구하기 위해, 매번 정렬하는 것이 아니라 최대힙을 구현해야 한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; impo..

👉 문제링크 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 🔸 문제 분석 🔸 0부터 n까지 원소가 1개씩 들어있는 n+1개의 집합에서 입력 연산의 결과를 출력한다. 0은 두 집합의 합집합 연산을 수행한다. 1은 두 집합이 같은 집합인지 확인해, 같으면 "YES" 혹은 "yes", 다르면 "NO" 혹은 "no"를 출력한다. 전형적인 union-find 알고리즘 문제이다. 합집합 연산은 union을 사용한다. 두 집합이 같은 집합인지 확인은 find를 사용해 반환값을 비교한..