[파이썬] 분할 정복을 공부합시다.

분할 정복 (Divide & Conquer)

분할 정복은 문제를 여러개로 나누어서 푸는 알고리즘입니다.

문제를 여러개로 분할하여 정복하기

 

동적 계획법(DP)과의 차이점은

 

• 동적 계획법은 분할한 문제들이 서로 영향을 미침.
• 분할 정복은 분할한 문제들이 서로 영향을 미치지 않음.

이 있습니다.

 

 

분할 정복의 필요조건

• 문제를 나눌 수 있어야 합니다.
• 부분 문제의 답을 이용하여 원래 문제의 답을 계산하는 방법이 있어야 합니다.

 

 

 

분할 정복의 알고리즘의 접근법은 다음과 같습니다.

1. 분할 : 문제를 작은 문제로 분할하는 과정
2. 정복 : 분할한 작은 문제들을 해결.
3. 조합 : 작은 문제에 대한 결과를 원본 문제에 대한 결과로 조합합니다

 

분할 정복 문제 하나를 가져와서 함께 풀어보겠습니다.

풀어볼 문제는 1074번 Z입니다.

문제를 한번 읽어보고 오세용.

 

 

문제 이해하기

input이 3,7,7인 경우입니다.

맵은 2³(8*8)의 사이즈를 가지고 (7, 7)의 좌표에 있는 값이 몇인지 구하는 문제입니다.

여기서는 63이네요.

 

각 인덱스는 Z모양으로 수가 주어집니다.

 

해결 로직

 

n, r, c = map(int,input().split())

result = 0
solved(block_size=2**n, x=0, y=0)

 

n, r, c를 int로 입력받습니다.

graph는 따로 만들지 않고, solved라는 함수를 만들어서 처리할 것입니다.

 

result : index를 세어줄 변수

x, y : 각 탐색의 좌표를 가지는 변수

block_size : 정사각형 탐색 범위의 값을 가지는 변수입니다.

초기값은 2**n, 테스트케이스에서는 3을 쓰니 2³으로 8입니다.

 

solved 함수 풀코드

def solved(block_size, x, y):
    global result

    if x == r and y == c:
        print(result)
        sys.exit(0)

    if block_size == 1:
        result += 1
        return 

    if not (x <= r < x+block_size and y <= c < y+block_size):
        result += block_size*block_size
        return 
    
    # 분할
    nbs = block_size//2
    # 1
    solved(nbs, x, y)
    # 2
    solved(nbs, x, y+nbs)
    # 3
    solved(nbs, x+nbs, y)
    # 4
    solved(nbs, x+nbs, y+nbs)

 

 

if x == r and y == c:
    print(result)
    sys.exit(0)

만약 (x,y)의 값이 (r,c)이 되었을 때, 다시 말해 값을 찾았을 때

result를 출력하고 프로그램을 종료합니다.

 

if block_size == 1:
    result += 1
    return

앞에서 이미 탐색을 성공하였을 때는 걸러졌으니, 탐색을 실패하고, 탐색 범위가 1일때

result에 += 1을 할당합니다.

더 작아질 수 없으니, 재귀를 return합니다.

분할 정복의 정복 부분입니다.

 

if not (x <= r < x+block_size and y <= c < y+block_size):
    result += block_size*block_size
    return

이 코드에서 가장 큰 백트래킹 부분입니다.

코드 이해를 위해 GIF로 봅시다.

아래 있는 x,y 블럭은 x <= r < x+block_size와 y <= c < y+block_size의 조건입니다.

두 조건이 전부 맞아야만 탐색을 진행하고, 아니라면 안에 값이 없다는 의미이니,

가지치기를 진행합니다.

result에는 block_size*block_size를 더해줍니다. (넓이)

 

가지치기가 끝났다면 다음과 같이 각 사분면을 탐색합니다.

nbs = block_size//2
# 1
solved(nbs, x, y)
# 2
solved(nbs, x, y+nbs)
# 3
solved(nbs, x+nbs, y)
# 4
solved(nbs, x+nbs, y+nbs)