태야

<내 코드>

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개씩 분할하는 방법이라고 한다.

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

<내 코드>

from itertools import combinations

N = int(input())
S = list(list(map(int, input().split())) for _ in range(N))
comb = combinations(range(N), N//2)  # 0 ~ N-1을 N/2 만큼 씩 조합
ans = float('inf')  # inf는 어떤 숫자와 비교해도 무조건 크다고 판정
# -inf는 어떤 수보다 무조건 작다

for c in comb:
    start_team = list(c)
    link_team = list(set(range(N)) - set(c))  # 차집합 후 리스트화

    start_ability, link_ability = 0, 0

    for i in range(N//2 - 1):
        for j in range(i+1, N//2):
            start_ability += S[start_team[i]][start_team[j]
                                              ] + S[start_team[j]][start_team[i]]
            link_ability += S[link_team[i]][link_team[j]] + \
                S[link_team[j]][link_team[i]]

    ans = min(ans, abs(start_ability - link_ability))

print(ans)

이번 문제는 백트래킹 문제지만 브루트포스로 풀었다. 다른 사람의 풀이를 참조하면서 새로운 개념들을 몇 가지 알게 됐다. 집합을 이용해 팀을 나누는 방법을 사용했다.

inf - 어떤 숫자와 비교해도 무조건 크다고 판정되는 파이썬 기능

-inf - 어떤 숫자와 비교해도 무조건 작다

<내 코드>

N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

# 비교값
max_ = -1e9
min_ = 1e9


def dfs(cnt, res, add, sub, mul, div):
    global max_, min_
    # 재귀 탈출 조건
    if cnt == N:
        max_ = max(res, max_)
        min_ = min(res, min_)
        return

    if add:
        dfs(cnt+1, res+nums[cnt], add-1, sub, mul, div)
    if sub:
        dfs(cnt+1, res-nums[cnt], add, sub-1, mul, div)
    if mul:
        dfs(cnt+1, res*nums[cnt], add, sub, mul-1, div)
    if div:
        dfs(cnt+1, int(res/nums[cnt]), add, sub, mul, div-1)


dfs(1, nums[0], add, sub, mul, div)
print(max_)
print(min_)

백트래킹을 이용해 모든 경우를 다 탐색하는 방법이다. 아직까지 재귀와 백트래킹 개념이 어려운 것 같다..

<내 코드>

import sys
N, M = map(int, sys.stdin.readline().split())
visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색
            visited[i] = 1

            arr.pop()  # 탐사한 내용 제거
            # 시작 탐색 값만 제외시키도록 나머진 초기화
            for j in range(i+1, N):
                visited[j] = 0


dfs(0)

<내 코드>

N, M = map(int, input().split())
#visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        arr.append(i+1)
        dfs(cnt+1)  # 다음 깊이 탐색
        arr.pop()  # 탐사한 내용 제거


dfs(0)

앞의 (1), (2) 순열, 조합 문제랑은 다르게 같은 수 중복 제거가 없다. 중복이 허용되고 그냥 탐사한 내용만 제거해주면 간단하게 된다.

<내 코드>

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []

def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1  # 중복 제거
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색
            arr.pop()  # 탐사한 내용 제거

            # 순열 부분과의 차이점
            for j in range(i+1, N):
                visited[j] = 0

dfs(0)

처음 i의 DFS 탐색에 사용 된 i값을 제외시키는 것이 순열과 다른 조합의 차이다.

파이썬 itertools 모듈의 combinations를 사용한 방법

from itertools import combinations

N, M = map(int, input().split())

p = combinations(range(1, N+1), M)
for i in p:
    print(*i)

<내 코드>

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1  # 중복 제거
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색

            visited[i] = 0  # 탐사 완료 후 다시 초기화
            arr.pop()  # 탐사한 내용 제거


dfs(0)

DFS와 백트래킹을 이용해 푸는 문제다. 재귀가 사용되다 보니 이해를 하는데 꽤 힘들었다.. 

파이썬 itertools 모듈을 사용한 방법

from itertools import permutations

N, M = map(int, input().split())

p = permutations(range(1, N+1), M)
for i in p:
    print(*i)