기록방

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

👉 문제링크 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 🔸 문제 분석 🔸 n x n 크기의 영상 정보에서 0 또는 1로 압축된 결과를 출력한다. 정사각형이 하나의 수로만 이루어져 있으면 그 수로 압축가능하다. 해당 수를 출력한다. 다른 수가 섞여있으면, 정사각형을 4등분해서 다시 압축한다. 4등분 했을때 결과값은 () 괄호로 묶어 출력한다. 재귀를 이용해서 정사각형이 하나의 수로 이루어져있지 않으면 4등분 값을 다시 검사하는 방식으로 해결한다. 🔸 코드 🔸 import java.io.Buff..

👉 문제링크 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 N x N 크기의 정사각형 종이를 같은 색으로만 이루어진 정사각형으로 자를 때 최소 개수를 출력한다. 종이를 자르는 방법은 한 변의 길이를 절 반으로 하는 정사각형 4개를 만드는 것이다. 한 정사각형 범위가 모두 같은 색인지 체크하고, 같지 않다면 4등분으로 잘라 다시 색을 체크하는 재귀 메서드를 사용한다. 재귀 메서드의 입력 값은 한 변의 길이와 좌상단의 좌표이다. 🔸 코드 🔸 import java.ut..