> For the complete documentation index, see [llms.txt](https://koalas-organization.gitbook.io/koala_codingtest_study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://koalas-organization.gitbook.io/koala_codingtest_study/search/undefined.md).

# 분할정복

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

### 병합 정렬

위에서 말한 바와 같이 분할 정복의 핵심은 <mark style="background-color:yellow;">Divide와 Conquer, Combine</mark>입니다.\
아래의 하늘색 부분과 같이 리스트를 계속 두 개의 부분 리스트로 나눈 후,\
파란색 부분과 같이 리스트를 계속 두 개씩 합치며 정렬합니다.&#x20;

<figure><img src="/files/6U3kicotNV5CSYYc6jCT" alt="" width="375"><figcaption></figcaption></figure>

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

```python
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

{% embed url="<https://www.acmicpc.net/problem/1074>" %}

이 문제를 자세히 들여다보면 Z 속의 Z 속의 Z ..의 로직을 볼 수 있습니다. 당연히 재귀를 사용할 수 있겠죠?\
재귀의 핵심은 <mark style="background-color:yellow;">return문</mark>과 <mark style="background-color:yellow;">다시 재귀로 들어가는 함수</mark>입니다. \
divide\_and\_conquer(x,y,size) 함수의 4가지 if 문을 파악해봅시다.

1. 만약 현재 위치 `(x, y)`가 목표 좌표 `(R, C)`와 일치하면, 해당 위치를 찾았다는 의미로 `turn`을 출력하고 프로그램을 종료합니다.
2. 만약 현재 행렬의 크기가 1이라면, 즉, 더 이상 분할할 수 없는 최소 단위라면, `turn`을 1 증가시키고 return 합니다.&#x20;
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)
```

## 풀어볼 문제

{% embed url="<https://www.acmicpc.net/problem/2448>" %}

{% embed url="<https://www.acmicpc.net/problem/11728>" %}