17829 222-풀링 파이썬 (-0)

문제

조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다.

다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다

1. 행렬을 2×2 정사각형으로 나눈다.
2. 
3. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다.
4. 
5. 2번 과정에 의해 행렬의 크기가 줄어들게 된다.

종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다.

랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.

입력

첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)

다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다. 

출력

마지막에 남은 수를 출력한다.

 

 

 

분할 정복을 계속 반복해서 1개만 남을 때 반환하는 형식.

보통 분할 후 정복을 통해서 그값들을 한번만 이용해서 끝나는 식이 아니었다.

 

1. 2*2로 나눈다.

2. 2번째 큰수만 남긴다.

3. 행렬 크기를 줄인다.

위의 반복.

 

 

나는 분할 정복 함수를 만들어서 그 함수를 여러번 반복하는 형식을 생각했다.

def 

n=2면 2번재 큰 수를 찾아서 따로 배열에 append

 

아니면 쿼드트리 처럼 4개로 나눠서 재귀

 

 

그 후 Numpy의 reshape를 이용해서 2차원 배열로 만들고 반복하려 했으나

백준에서는 외부 라이브러리를 못사용해서 실패

 

1차원 배열로 뽑으면 순서가 뒤죽박죽이 되서 두번째 풀링을 할 수가 없었다. 이 순서를 어떻게 할까에서 막힘.

 

 

출처:

https://home-body.tistory.com/701

 

분할 정복으로 풀링된 배열 생성 ->  그배열을 재귀로 넣고 또 풀링된 배열 생성

-> 1개의 원소가 나올 때 까지. 이런방향으로 구현하셨다.

 

 2차원 빈 배열을 미리 안에 만들어 둔 후

2중 for문을 사용해서 2번째 큰 수를 순서에 맞게 넣었다. 

 

한 번 풀링할 때마다 2의 간격으로 줄어들기 때문에

new_arr[i//2]로 넣게 되면 풀링된 값들이 행과 열 순서대로 차례차례 들어가게 된다.

 

 

 

import sys
input=sys.stdin.readline
def Find(x,y,temp):
    return sorted ([temp[x][y],temp[x][y+1],temp[x+1][y],temp[x+1][y+1]])[2]
def search(arr,n):
    #1개 남으면 정답 출력
    if n==1:
        return arr[0][0]
    #풀링한번 돌고 난 값들 저장할 배열
    new_arr=[ [] for _ in range(n//2)]
    for i in range(0,n,2): # 행의 각 시작점들
        for j in range(0,n,2): # 열의 각 시작점
            new_arr[i//2].append(Find(i,j,arr))
    return search(new_arr,n//2)
N=int(input())
arr=[list(map(int,input().split())) for _ in range(N)]
print(search(arr,N))