[WEEK 02] 알고리즘 - 분할 정복 문제풀이

2630. 색종이 자르기

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

이 문제는 쿼드 트리라는 개념을 이용해 답을 구할 수 있다. 쿼드 트리는 대량의 좌표 데이터를 저장하기 위해 사용하는 기법으로 주어진 공간을 4개로 분할하여 재귀적으로 표현한다.

import sys

input = sys.stdin.readline

N = int(input())

matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

white, blue = 0, 0

def quad_tree(N, x, y):
    global matrix, white, blue
    vertex = matrix[x][y]
    
    for i in range(x, x + N):
        for j in range(y, y + N):
            if vertex != matrix[i][j]:
                quad_tree(N // 2, x, y)
                quad_tree(N // 2, x + N // 2, y)
                quad_tree(N // 2, x, y + N // 2)
                quad_tree(N // 2, x + N // 2, y + N // 2)
                return
    if vertex == 0:
        white += 1
    elif vertex == 1:
        blue += 1

quad_tree(N, 0, 0)

print(white)
print(blue)

함수 안에서 return 하지 않으면 결과값이 완전히 달라진다. 전역 변수 global는 많은 재귀 함수 문제에서 함수를 정의할 때에 사용되므로 더욱 자세히 알아야 할 것 같다.

---

1629. 곱셈

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

분할 정복은 한번에 해결하기 힘든 문제를 작은 문제들로 분할하여 문제를 해결하는 방법이다.

단순한 연산 문제라고 생각하여 반복문을 사용하면 세 변수의 범위가 매우 크게 주어지기 때문인지 시간 초과가 발생한다. 그렇기 때문에 분할 정복을 이용하여 해결하는 문제이다.

import sys

input = sys.stdin.readline

A, B, C = map(int, input().split())

def divide_conquer(A, B):
    if B == 1:
        return A % C
    
    temp = divide_conquer(A, B // 2)
    
    if B % 2 == 0:
        return temp * temp % C
    
    else:
        return temp * temp * A % C

print(divide_conquer(A, B))

이 문제에서는 분할을 통해 지수 변수 B를 절반으로 나누는 방법을 사용하여 문제를 해결하였다. 다른 분할 정복 문제에서는 어떠한 분할 방법을 통해 문제를 해결할 수 있는지 알고 싶다.

---

6549. 히스토그램에서 가장 큰 직사각형

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

import sys

input = sys.stdin.readline

while True:
    arr = list(map(int, input().split()))
    
    if arr[0] == 0:
        break
    
    heights = arr[1:]
    heights.insert(0, 0)
    heights.append(0)
    
    stack = [0]
    max_square = 0
    
    for i in range(1, arr[0] + 2):
        while stack and heights[i] < heights[stack[-1]]:
            index = stack.pop()
            max_square = max(max_square, (i - stack[-1] - 1) * heights[index])
        stack.append(i)
    print(max_square)

답안 코드의 한 줄도 이해하지 못했다. 다른 사람의 답안 코드를 그대로 옮겨 적었다.

---

10830. 행렬 제곱

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

1629. 곱셈 문제와 비슷한 풀이를 통해 문제를 해결할 수 있다.

import sys

input = sys.stdin.readline

N, B = map(int, input().split())
A = list()

for i in range(N):
    A.append(list(map(int, input().split())))

def matrix_mul(N, matrix1, matrix2):
    result = [[0 for i in range(N)] for i in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
            result[i][j] %= 1000
    return result

def matrix_div(N, B, matrix):
    if B == 1:
        return matrix
    elif B == 2:
        return matrix_mul(N, matrix, matrix)
    else:
        temp = matrix_div(N, B // 2, matrix)
        if B % 2 == 0:
            return matrix_mul(N, temp, temp)
        else:
            return matrix_mul(N, matrix_mul(N, temp, temp), matrix)

result = matrix_div(N, B, A)

for i in result:
    for j in i:
        print(j % 1000, end=' ')
    print()