본문 바로가기

합병 정렬

[백준 1074] Z (JAVA)

CodingTEST 2023. 12. 13. [백준 1074] Z (JAVA) 백준 1074번 문제 - Z 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 분석 2^(n-1) 크기에 배열에 위에 그림처럼 Z모양 순(왼 위, 왼 아래, 오 위, 오 아래) 으로 방문한다. 이 때 r행 c열은 몇 번째로 방문했는지 출력해라. 해결 포인트 합병 정렬 사용 몇번째 사분면에 존재하는지 판단 해당 사분면 가기 전에 이전 앞서 방문해야 하는 개수 ( size 는 한 변의 길이 → size * size 는 전체 배열 개수 ) - 1사분면 : 0 - 2사분면 : size *size / 4..

[백준 2630] 색종이 만들기 (JAVA)

CodingTEST 2023. 12. 8. [백준 2630] 색종이 만들기 (JAVA) 백준 2630번 문제 - 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 분석 2차원 배열로 흰색 확은 파란색으로 색이 칠해진 종이가 주어진다. (NxN) 종이를 모두 같은 색으로 칠해져 있을 때까지 정사각형으로 자른다. (혹은 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.) N -> N/2 -> N/2/2 -> ... -> 1 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종..

[백준 1517] 버블 소트 (JAVA)

CodingTEST 2023. 7. 29. [백준 1517] 버블 소트 (JAVA) 백준 1517번 문제 - 버블 소트 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 문제 분석 : 오름차순으로 정렬할때 일어나는 swap 개수를 출력해라 해결 키 포인트 오름차순 정렬 병합 정렬 병합 정렬하면서 앞 배열의 값보다 뒷 배열의 값이 더 작을 때 swap 개수 증가 swap 개수 누적 배열 1 [0하고 1] 3[0] 2[1] 1[2] 2 [0하고 2] 2[1] 3[0] 1[2] 3 [1하고 2] 2[1] 1[2] 3[0] 3 1[2] 2[1] 3[0] 증가되는 swap 개수 ..

[백준 2751] 수 정렬하기 2 (JAVA)

CodingTEST 2023. 7. 29. [백준 2751] 수 정렬하기 2 (JAVA) 백준 2751번 문제 - 수 정렬하기 2 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 분석 : 단순 오른차순으로 정렬하기 해결 키 포인트 오름차순 정렬 Arrays.sort() 병합 정렬 병합 정렬 설명 복합 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합치는 알고리즘 최소 단위로 분할 (가장 작은 데이터 집합으로 분할) 두 단위를 병합하면서 정렬 코드 import java.io.*; import java.util.Arrays; public class Main { publi..

이전 1 다음

티스토리툴바