분할 정복의 힘 (2630번, 1074번 파이썬)

분할 정복 (Divide and Conquer)

: 문제를 나눌 수 없을 때까지 나누어 각각의 부분을 연산한 뒤 다시 합치며 답을 얻는 알고리즘이다.

 

의사코드(psuedo code)를 작성해 본다면 다음과 같다.

function F(x):
	if 문제를 더 이상 나눌 수 없는 조건:
    	return 계산한 값
   	else:
    	x를 문제의 조건 내에서 분할
        return F(x1), F(x2) .... 분할한 데이터로 함수를 재귀적으로 호출

이 의사코드를 보고난 후, 문제를 어떻게 풀어야 할지 감이 바로 왔다.

 

#2630번 색종이 만들기 https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

# 색종이 -> 분할 정복

# 분할정복
# 1. 어떻게 나눌 것인가?
# 2. 분할과 계산을 구분하는 조건은 무엇인가?
# 색종이는 색깔을 기준으로 결정된다.
# 사각형 내부의 색이 통일된 경우예는 계산을 진행하고
# 통일되지 않은 경우에는 분할한다.

N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
answer = [0, 0]  # w, b


def sum_of_2D(matrix):
    result = 0
    for r in matrix:
        result += sum(r)
    return result


def solve(paper):
    global answer
    s = sum_of_2D(paper)
    if s == 0:  # is white
        answer[0] += 1
        return
    elif s == len(paper)**2:
        answer[1] += 1
        return
    else:
        N1 = [sub_p[:len(sub_p)//2] for sub_p in paper[:len(paper)//2]]
        N2 = [sub_p[len(sub_p)//2:] for sub_p in paper[:len(paper)//2]]
        N3 = [sub_p[:len(sub_p)//2] for sub_p in paper[len(paper)//2:]]
        N4 = [sub_p[len(sub_p)//2:] for sub_p in paper[len(paper)//2:]]

        for n in [N1, N2, N3, N4]:
            solve(n)


solve(paper)
for a in answer:
    print(a)

맨 위부터 나오는 주석은 요즘 지켜나가는 습관이다. 문제를 이해하고 머릿속에 떠오른 풀이 과정을 메모한 뒤 진행한다.

 

정말 쉽다.

문제에서 정답을 count하는 조건을 찾아 재귀함수의 종료조건으로 설정하고 만족하지 않을 경우 문제의 조건에 맞게 분할한 뒤 재귀적으로 호출하면 된다.

 

N1~N4 부분을 더욱 간단하게 바꿀 수 있을 것 같지만 딱히 떠오르진 않았다. 

 

여기저기 찾아봤지만 다 비슷하게 짠 듯 하다.

 

참고한 블로그

https://moz1e.tistory.com/85

[백준BOJ] 단계별로 문제풀기 - 분할 정복 정답 및 후기(파이썬, python)

 

#1074번 Z https://www.acmicpc.net/problem/1074

1074번: Z

자신감이 생겨 이 문제에도 도전했다.

 

틀린코드

N, r, c = map(int, input().split())
graph = [[False]*(2**N) for _ in range(2**N)]
graph[r][c] = True
answer = [0, False]  # count, isItFound?


def solve(graph):
    global answer
    if len(graph) == 2:
        for r in graph:
            for num in r:
                if num:
                    answer[1] = True
                    return
                else:
                    answer[0] += 1
        return
    else:
        s1 = [sub[:len(sub)//2] for sub in graph[:len(graph)//2]]
        s2 = [sub[len(sub)//2:] for sub in graph[:len(graph)//2]]
        s3 = [sub[:len(sub)//2] for sub in graph[len(graph)//2:]]
        s4 = [sub[len(sub)//2:] for sub in graph[len(graph)//2:]]

        for s in [s1, s2, s3, s4]:
            if not answer[1]:
                solve(s)


solve(graph)
print(answer[0])

위 문제와 동일한 알고리즘을 적용했는데 메모리 초과가 났다.

전체 맵의 크기는 2**n * 2**n 인데, n 의 최댓값이 15이기 때문에 2의30제곱 길이의 리스트를 만들게 된다.

리스트의 한 인덱스가 1바이트를 차지한다고 했을 때 (맞나?),

n=15인 경우, 2의30제곱 Byte가 되는데

이는 2의20제곱 KB (KiB라고 표기하는게 정확하긴 하다.),

2의10제곱 MB (MiB가 정확) 이 된다.

 

문제의 메모리 제한은 512MB이기 때문에 위와 같은 알고리즘은 메모리 제한을 한참 초과한다.

 

때문에 리스트를 전부 탐색하는 형태의 분할정복이 아니라 분할정복 알고리즘을 응용한 수학적 연산이 필요하다.

 

정답코드

# z 방문 횟수
# 그래프를 탐색하면 안됨
# 수치적 진행
# N 이 1씩 줄어들 때마다 4분의 1이 됨
N, r, c = map(int, input().split())

count = 0
while N > 0:
    tmp = 2**N//2
    quarter = (2**(N-1))**2
    if 0 <= r < tmp and tmp <= c:
        count += quarter
        c -= tmp
    elif tmp <= r and 0 <= c < tmp:
        count += quarter*2
        r -= tmp
    elif tmp <= r and tmp <= c:
        count += quarter*3
        r, c = r-tmp, c-tmp
    N -= 1

print(count)

간단하다. N이 1씩 줄어들 때마다 리스트의 크기는 4분의 1이 된다. 목표점의 위치가 어느 사분면에 존재하는지 판단한 후, 도달하기 위해 지나쳐야하는 사분면을 다 더해주면 된다.

 

r, c가 3사분면에 있다면

정답에 1사분면과 2사분면의 갯수를 더해준 뒤,

N을 1만큼 감소시켜 전체 리스트를 4분의 1로 만든다.

이와 동시에 r과 c도 조정해야한다.

 

처음에는, 2,3,4 사분면 모두에서  r,c를 전부 조절했었는데,

생각해보니 2사분면은 c값만 조절하면 되고 3사분면은 r값만 조절하면 된다.

 

조금만 고민해보면 쉬운 문제인데

노력하기도 전에 겁먹는 날이 잦은 요즘이다.