17829 222-풀링 파이썬 (-0)
문제
조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(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개만 남을 때 반환하는 형식.
보통 분할 후 정복을 통해서 그값들을 한번만 이용해서 끝나는 식이 아니었다.
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))