분할정복

어떤 문제를 더 이상 쪼갤 수 없을 때까지 분할(Divide)한 후 하위 문제를 해결(Conquer)하고 합치면서(Combine) 문제의 답을 도출하는 알고리즘

가장 대표적인 분할정복 문제인 병합정렬 코드를 예시로 살펴봅시다.

병합 정렬

위에서 말한 바와 같이 분할 정복의 핵심은 Divide와 Conquer, Combine입니다. 아래의 하늘색 부분과 같이 리스트를 계속 두 개의 부분 리스트로 나눈 후, 파란색 부분과 같이 리스트를 계속 두 개씩 합치며 정렬합니다.

위의 그림에서 2,8 / 5,6 을 어떻게 Combine하는지 봅시다. 어차피 왼쪽과 오른쪽 각각이 정렬되어 있기 때문에 왼쪽과 오른쪽 배열의 원소를 한 개씩 판단하며 합쳐 나가면 됩니다. 2과 5를 비교해서 2를 왼쪽에 두고, 5와 8을 비교해서 5를 왼쪽에 놓습니다. 이후 6과 8을 비교해 6을 왼쪽에 두면, 남은 8은 자연스럽게 마지막에 놓아지게 됩니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid] 
    right = arr[mid:]

    left = merge_sort(left) #재귀
    right = merge_sort(right) #재귀

    return merge(left, right)

def merge(left, right):
    result = []
    i = 0
    j = 0
    
    #차례대로 한 개씩 비교하며 merge 시킨다.
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while i < len(left):
        result.append(left[i])
        i += 1

    while j < len(right):
        result.append(right[j])
        j += 1

    return result
    
print(merge_sort(4,3,7,1,2,8,5,6)) #[1,2,3,4,5,6,7,8]

병합정렬은 분할 단계에서 2개씩 분할해나가므로 O(logN)의 시간복잡도를, 병합 단계에서 N개의 원소에 대해 한 번씩 비교하므로 O(N)의 시간복잡도를 가지기 때문에 최종적으로 O(NlogN)의 시간복잡도를 가집니다. 이번 기회에 이 외에 여러 정렬 알고리즘에 대해서도 공부해 보세요 !

이번에는 아래 문제를 풀어봅시다.

Z

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

이 문제를 자세히 들여다보면 Z 속의 Z 속의 Z ..의 로직을 볼 수 있습니다. 당연히 재귀를 사용할 수 있겠죠? 재귀의 핵심은 return문과 다시 재귀로 들어가는 함수입니다. divide_and_conquer(x,y,size) 함수의 4가지 if 문을 파악해봅시다.

1. 만약 현재 위치 (x, y)가 목표 좌표 (R, C)와 일치하면, 해당 위치를 찾았다는 의미로 turn을 출력하고 프로그램을 종료합니다.

2. 만약 현재 행렬의 크기가 1이라면, 즉, 더 이상 분할할 수 없는 최소 단위라면, turn을 1 증가시키고 return 합니다.

3. 주어진 좌표 (R, C)가 타겟하는 행렬의 범위가 아니라면, 해당 부분 행렬을 전체 크기만큼 방문했다고 가정하고 turn을 업데이트합니다. ex. 35번째 칸을 가고 싶은데 0이나 16과 같은 행렬 칸에 접근했을 경우

4. 그렇지 않으면 현재 행렬을 4분할하여 각각의 부분 행렬에 대해 재귀적으로 divide_and_conquer 함수를 호출합니다. (왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래)

import sys
input=sys.stdin.readline

N,R,C=map(int,input().split())
#정답을 저장해둘 배열
turn=0
def divide_and_conquer(x,y,size):
    global turn
    if y==R and x==C: 
        print(turn)
        exit()
    if size==1:
        turn+=1
        return
    if not (y<=R<y+size and x<=C<x+size):
        turn+=size*size
        return
    #4등분씩 방문. 기준은 맨 왼쪽 위
    else:    
        divide_and_conquer(x, y, size//2)
        divide_and_conquer(x+size//2, y,size//2)
        divide_and_conquer(x, y+size//2, size//2)
        divide_and_conquer(x+size//2,y+size//2, size//2)

divide_and_conquer(0, 0, 2**N)

풀어볼 문제

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

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