[Python] 백준 17829번 222-풀링 (실버2)

문제

입력

첫째 줄에 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

---

풀이

CNN에서의 2*2 MaxPooling(이 문제에서는 2nd Max)을 숫자 하나가 남을 때까지 반복 수행하는 문제입니다.

재귀함수를 적절히 정의하는 것이 중요하겠습니다.

Point

• 재귀함수
• 분할정복법

---

소스코드

def pooling(matrix, N):
    if N == 1 :
        return matrix[0][0]
    s = [[0] * (N // 2) for _ in range(N // 2)]
    for i in range(N//2):
        for j in range(N//2):
            l = sorted(matrix[2*i][2*j:2*j+2]+matrix[2*i+1][2*j:2*j+2])
            s[i][j] = l[-2]
    return pooling(s,N//2)

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

 

Line 1~3

def pooling(matrix, N):
    if N == 1 :
        return matrix[0][0]

 

pooling 함수는 NxN matrix와 그 크기 N을 입력으로 받습니다.이후재귀함수를 끝내는 조건입니다.문제에서 제시한 대로 마지막에 남은 1*1 matrix의 값을 return합니다.

Line 4

    s = [[0] * (N // 2) for _ in range(N // 2)]

 

입력 행렬 크기의 절반인 행렬 s를 초기 설정하여 pooling을 1회 실시한 결과값을 받도록 준비해 줍니다.

(입력 행렬 : [[-6, -8,  7, -4],   s : [[0, 0], )
                    [-5, -5, 14, 11],         [0, 0]]
                    [11,  11,  -1, -1],
                    [ 4,   9,  -2, -4]]

Line 5~9

    for i in range(N//2):
        for j in range(N//2):
            l = sorted(matrix[2*i][2*j:2*j+2]+matrix[2*i+1][2*j:2*j+2])
            s[i][j] = l[-2]
    return pooling(s,N//2)

 

pooling을 실행하게 되는 핵심부분입니다.

입력 matrix의 크기의 절반만큼 i 와 j를 for문으로 잡아줍니다.

( (i , j) = (0, 0) , (0, 1) , ... , (0, (N//2)-1), (1, 0), (1, 1), ... , ((N//2)-1, (N//2)-1) )

 

그렇게 되면 입력 행렬을 2*2 matrix로 쪼갠 후, 그 첫번째 위치(0,0)의 원소는 입력 행렬의 (2*i, 2*j)위치로 표현할 수 있습니다.

(입력 행렬 : [[-6, -8, |  7, -4],   matrix[0*2][0*2] = -6 , matrix[0*2][1*2] = 7 , matrix[1*2][0*2] = 11 등)
                    [-5, -5, | 14, 11], 
                    [11,  11, |  -1, -1],
                    [ 4,   9,  | -2, -4]]

 

이제 빈 행렬 s에 쪼갠 2*2 matrix에서 2번째로 큰 값을 담아봅시다.

l 에 쪼갠 각 matrix의 원소를 1차원 list로 담은 후, 정렬해 줍니다. ( ex. [-6, -8, -5, -5] )

두번째로 큰 값인 l[-2]를 s에서 해당되는 각 위치에 넣어줍니다. ( s = [ [-5, 11] , [11, -1]] )

 

재귀 호출을 하여 덜 쪼개어진 행렬 s를 다시 pooling 하게 되면, 종료 조건인 matrix의 크기가 1*1일 때까지 같은 함수가 다시 돕니다.

 

다행히 입력 matrix의 크기는 2의 거듭제곱으로 주어지기 때문에, size가 안맞아떨어질 걱정은 안해도 됩니다.

( 같은 맥락에서 CNN의 pooling layer 때문에 딥러닝 시 input size를 2의 거듭제곱으로 맞춰놔야 편합니다...)

---

Line 11~14

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

 

첫 번째 입력값은 초기 matrix의 사이즈인 n으로 받고,이후 n회 동안 input값을 받아서 행렬에 넣어주면 pooling의 입력값 matrix가 완성됩니다.