조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다. 다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다 1. 행렬을 2×2 정사각형으로 나눈다. 2. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다. 3. 2번 과정에 의해 행렬의 크기가 줄어들게 된다.
종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다. 랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.
설명
NxN 행렬이 주어지면 N/2개의 2x2 크기의 정사각형으로 나눌 수 있다. 각 정사각형의 첫 숫자 즉 좌측 상단 인덱스에 접근하기 위해 i와 j를 0부터 N/2에 접근하고 2만큼 곱해준다. 즉 i,j에 대해서 정사각형의 4개의 인덱스는 (2*i,2*j),(2*i+1,2*j),(2*i,2*j+1),(2*i+1,2*j+1)이다. 접근한 4개의 index 중 두번째로 큰 값을 찾아서 원래의 배열에서 (i,j)에 저장하여 (N/2)x(N/2) 행렬을 만들어준다.
위 과정을 N이 1이 될 때까지 반복하면 최종적으로 출력할 숫자가 (0,0)에 저장된다.
코드
//17829번 222-풀링.java
package week7;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 풀링_222_17829 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws NumberFormatException, IOException {
int N = Integer.parseInt(br.readLine());
int[][] square = new int[N][N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++) {
square[i][j] = Integer.parseInt(st.nextToken());
}
}
while(N!=1) {
N /= 2;
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
int[] temp = new int[4];
temp[0]=square[2*i][2*j];
temp[1]=square[2*i+1][2*j];
temp[2]=square[2*i][2*j+1];
temp[3]=square[2*i+1][2*j+1];
Arrays.sort(temp);
square[i][j]=temp[2];
}
}
}
System.out.println(square[0][0]);
}
}
