문제
조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다.
다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다
- 행렬을 2×2 정사각형으로 나눈다.
- 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다.
- 2번 과정에 의해 행렬의 크기가 줄어들게 된다.
종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다.
랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.
입력
첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)
다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다.
출력
마지막에 남은 수를 출력한다.
예제
예제 입력 1
4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4
예제 출력 1
11
예제 입력 2
8
-1 2 14 7 4 -5 8 9
10 6 23 2 -1 -1 7 11
9 3 5 -2 4 4 6 6
7 15 0 8 21 20 6 6
19 8 12 -8 4 5 2 9
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
예제 출력 2
17
풀이
분할정복 문제
sorting 함수 설명
1. 2*2 행렬의 원소 4개를 오름차순으로 정렬하여 배열 arr에 저장한다.
2. 두번째로 큰 수는 arr[2]에 저장되어 있다. 이를 2*2 행렬의 좌측상단(행과 열의 인덱스가 가장 작은 자리)에 저장한다.
pooling(size) 함수 설명
1. 입력받은 행렬을 2*2 행렬로 쪼갠 후sorting 함수를 호출한다.
2. size를 반으로 나눠서 pooling 함수를 재귀적으로 호출한다.
3. 만약 size가 2보다 작다면 (=1) 입력받은 행렬의 (0,0) 원소를 출력한다.
더 공부할 것
분할정복 문제를 더 많이 풀어봐야겠다.
다른 분의 풀이를 보았는데, 이게 내 풀이보다 훨씬 깔끔한 것 같다.
전체 코드
import java.util.*;
public class Main {
static int[][] values;
public static void sorting(int row, int col){
int[] arr = new int[4];
int k=0;
for(int i=row; i<row+2; i++)
for(int j=col; j<col+2; j++)
arr[k++] = values[i][j];
Arrays.sort(arr);
values[row/2][col/2] = arr[2];
}
public static void pooling(int size){
if(size < 2){
System.out.println(values[0][0]);
return;
}
for(int i=0; i<size/2; i++)
for(int j=0; j<size/2; j++)
sorting(2*i, 2*j);
pooling(size/2);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<Integer> list = new ArrayList<>();
int size = sc.nextInt();
values = new int[size][size];
for(int i=0; i<size; i++)
for(int j=0; j<size; j++)
values[i][j] = sc.nextInt();
pooling(size);
}
}
