태야

<내 코드>

n = int(input())
video = [list(input()) for _ in range(n)]


def divide(x, y, n):
    ans = []
    check = True
    color = video[x][y]

    for i in range(x, x+n):
        if not check:
            break
        for j in range(y, y+n):
            if color != video[i][j]:
                check = False
                ans.append("(")
                ans.extend(divide(x, y, n//2))
                ans.extend(divide(x, y+n//2, n//2))
                ans.extend(divide(x+n//2, y, n//2))
                ans.extend(divide(x+n//2, y+n//2, n//2))
                ans.append(")")
                return ans
    return color


print("".join(divide(0, 0, n)))

list.append와 list.extend의 차이에 대해 알게 됐다.

a = [1, 2, 3]
b = [4, 5, 6]

a.append(b)
print(a) # [1, 2, 3, [4, 5, 6]]

a = [1, 2, 3]
b = [4, 5, 6]

a.extend(b)
print(a) # [1, 2, 3, 4, 5, 6]

append는 해당 리스트(b) 그 자체를 리스트(a) 끝에 넣어준다. 반면에 extend는 해당 리스트(b) 안의 요소들을 (a)리스트 끝에 넣어 확장시켜준다.

<내 코드>

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

white, blue = 0, 0


def divide(x, y, n):
    global white, blue
    color = paper[x][y]
    check = True

    for i in range(x, x+n):
        if not check:
            break

        for j in range(y, y+n):
            if color != paper[i][j]:
                check = False
                divide(x, y, n//2)  # 1사분면
                divide(x, y+n//2, n//2)  # 2사분면
                divide(x+n//2, y, n//2)  # 3사분면
                divide(x+n//2, y+n//2, n//2)  # 4사분면
                break
    if check:
        if color:
            blue += 1
        else:
            white += 1


divide(0, 0, N)
print(white)
print(blue)

이 문제는 처음 접하는 개념인 '쿼드트리'를 만드는 것이었다. 트리의 자식노드가 4개씩 분할하는 방법이라고 한다.

여기서 분할 된 영역 안에서 같은 색인지 판단해 다르다면 또 다시 나누면서 찾아간다. 일반 동적 계획법과 다르게 분할 정복은 중복되는 하위 문제가 없다는 것이 차이다.

<내 코드>

import sys
sys.setrecursionlimit(10**6)

n = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))

pos = [0]*(n+1)
for i in range(n):
    pos[in_order[i]] = i

# 전위 순회
def divide(in_start, in_end, p_start, p_end):

    if(in_start > in_end) or (p_start > p_end):
        return

    parents = post_order[p_end]  # 후위순회에서 부모노드 찾기
    print(parents, end=" ")

    left = pos[parents] - in_start  # 왼쪽인자 갯수
    right = in_end - pos[parents]  # 오른쪽인자 갯수

    divide(in_start, in_start+left-1, p_start, p_start+left-1)  # 왼쪽 노드
    divide(in_end-right+1, in_end, p_end-right, p_end-1)  # 오른쪽 노드


divide(0, n-1, 0, n-1)

후위 순회에서 부모 노드를 찾아 중위 순회에서 기준으로 삼아 왼쪽, 오른쪽 나눈다. 그리고 왼쪽 자식 트리 노드, 오른쪽 자식 트리 노드를 순회하며 앞의 과정을 반복한다.