[Python] S2_17829_222-풀링 2️⃣ 2️⃣ 2️⃣

https://www.acmicpc.net/problem/17829

문제

조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(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로 만들었을 때 어떤 값이 남아있을지 궁금해한다.

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

입력

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

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

출력

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

예제

조건

• 시간 제한: 1초
• 메모리 제한: 256MB

코드

import sys
input = sys.stdin.readline

n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)]

def DAC(x,y,n):
    if n == 2:
        lst = []
        for i in range(x,x+n):
            for j in range(y,y+n):
                lst.append(graph[i][j])
        
        # 두번째로 큰 수        
        return sorted(lst, reverse = True)[1]
    
    # 1,2,3,4사분면
    one = DAC(x, y, n//2)
    two = DAC(x, y+n//2, n//2)
    three = DAC(x+n//2, y, n//2)
    four = DAC(x+n//2, y+n//2, n//2)
    
    # 최종적으로 나온 수
    return sorted([one, two, three, four], reverse = True)[1]
    
print(DAC(0,0,n))

1. 그래프를 입력받습니다.

2. n == 2 , 즉 2x2의 형태가 될 때까지 1,2,3,4사분면으로 나누어줍니다.

• 각 사분면의 값들을 lst 에 넣어준 다음에, 내림차순으로 정렬해서 두 번째 숫자를 return 해줍니다.

• return sorted(lst, reverse = True)[1]

3. return 값을 받은 후에, 순차적으로 값을 비교하여 최종적인 답을 구합니다.

• 2번 과정을 통해 1사분면에서는 6, 2사분면에서는 14, 3사분면에서는 9, 4사분면에서는 5 라는 값을 return 받을 수 있었습니다.

• [6, 14, 9, 5] 가 담겨 있는 lst를 정렬하여 다시 2번째로 큰 수인 9를 return 합니다.

• 이는 원래의 형태인 n==8 , 즉 8x8 에서의 1사분면에 해당합니다

• 이러한 과정들을 반복하며 원래 nxn 크기의 1,2,3,4 사분면을 비교하여 최종적인 답을 return 합니다.

느낀 점 & 배운 점

1. 2번째로 큰 수를 구하는 방법이 여러 가지가 있을 것 같은데.. 더 효율적인 방법을 알아보면 좋을 듯하다.

2. 이제 분할 정복에 대해서는 어느정도 감을 익힌 것 같다. 몇 번 정도만 더 연습해보자!