분할정복: 백준 1074 문제

핵심 개념: 분할 정복(Divide & Conquer)

• 2^N × 2^N 크기의 Z 모양 방문 순서를 따라 특정 위치 (r, c)가 몇 번째로 방문되는지 구하는 문제
• 전체 배열을 4개 사분면으로 나누고, (r, c)가 속한 사분면을 찾아 이동하면서 문제를 해결함
• 재귀적으로 크기를 줄여나가면서 (r, c)의 정확한 위치를 찾아 점프하는 방식

---

문제 풀이 과정

Z 모양 방문 순서 이해

• 가장 작은 N=1의 경우부터 Z 순서를 따라가는 패턴이 있음
• N=2일 때 방문 순서 예시:

  0   1   4   5  
  2   3   6   7  
  8   9   12  13  
  10  11  14  15  

  • (r=3, c=1)의 방문 순서는 11
• 결론: N이 커질수록 4개의 작은 Z 패턴이 반복됨 → 사분면을 나눠서 탐색해야 함

---

핵심 접근법: 재귀 & 사분면 탐색

• 2^N × 2^N 크기의 배열을 4개의 2^(N-1) × 2^(N-1) 크기의 사분면으로 나눈다.
• (r, c)가 어느 사분면에 속하는지 찾아서 해당 사분면의 시작 순서를 더한 후, 좌표를 조정하여 재귀 호출한다.

사분면	시작 위치	조건 (r, c 위치)	추가 방문 카운트
1사분면 (좌상)	0	r < half, c < half	0
2사분면 (우상)	1 * half²	r < half, c >= half	1 * half²
3사분면 (좌하)	2 * half²	r >= half, c < half	2 * half²
4사분면 (우하)	3 * half²	r >= half, c >= half	3 * half²

• 여기서 half = 2^(N-1), 즉 배열을 반으로 나눈 크기임

---

코드 분석

def devide(N, r, c):
    if N == 0:
        return 0  # 가장 작은 단위까지 내려가면 방문 순서는 0
    
    half = 2 ** (N - 1)  # 현재 크기의 반
    
    # 1사분면 (좌상)
    if r < half and c < half:
        return devide(N - 1, r, c)
    
    # 2사분면 (우상) -> 1사분면의 크기만큼 점프
    if r < half and c >= half:
        return 1 * half**2 + devide(N - 1, r, c - half)
    
    # 3사분면 (좌하) -> 1,2사분면의 크기만큼 점프
    if r >= half and c < half:
        return 2 * half**2 + devide(N - 1, r - half, c)
    
    # 4사분면 (우하) -> 1,2,3사분면의 크기만큼 점프
    else:
        return 3 * half**2 + devide(N - 1, r - half, c - half)

---

오답 노트

1. 사분면을 나누는 기준이 헷갈릴 수 있음

   • (r, c)가 어느 사분면에 속하는지 확실히 이해해야 함.
   • 특히 r >= half 또는 c >= half 조건을 사용할 때 실수할 가능성이 높음.
   • 이상, 이하 판단 잘해서 넣을 것

2. 좌표를 조정할 때 half를 빼야 함

   • 예를 들어 우하 (4사분면)으로 이동할 때, (r - half, c - half)를 새로운 r, c 좌표로 사용해야 함.
   • 만약 r - half, c - half 처리를 하지 않으면 무한 루프 발생 가능.
   • 절반을 정확히 빼줘서 새로운 base 형성해줄 것

3. 각 사분면의 방문 순서를 더하는 논리가 정확해야 함

   • 1사분면: 그냥 재귀 호출
     • 이게 이해가 안 갈 수도 있는데, 이미 그 앞에서 재귀를 불러오면서 계속해서 제 1사분면이 뜬게 아닌 이상 많은 수가 더해진 상태임.
   • 2사분면: 1 * half²을 더해줌
   • 3사분면: 2 * half²을 더해줌
   • 4사분면: 3 * half²을 더해줌
   • half²을 활용해서 점프하는 개념이 중요함.

4. 재귀 호출이 너무 깊어질 수 있음

   • 백준 문제에서 N ≤ 15이므로 재귀 호출이 15번 정도 이루어짐.
   • 파이썬 기본 재귀 한계 (sys.setrecursionlimit)를 늘릴 필요는 없지만, 너무 깊은 재귀를 피하는 것이 좋음.

---

시간 복잡도

• O(1)로 바로 값을 찾을 수 없기 때문에, N번 재귀 호출을 반복한다.
• 각 단계에서 계산량은 O(1)이므로, 전체 시간 복잡도는 O(N).

---

예제 테스트

예제 1: N=2, r=3, c=1

• 입력: 2 3 1
• 과정:
  1. N=2, r=3, c=1 → 3사분면 (+8), 새로운 (1,1)
  2. N=1, r=1, c=1 → 4사분면 (+3), 새로운 (0,0)
  3. N=0, r=0, c=0 → 0
• 출력: 11

---

정리

1. Z 모양 탐색을 어떻게 수행하는지 개념 설명

   • 작은 N=1부터 시작해서 N=2, N=3으로 확장
     • 사실상 N=0도 있는거임
   • 사분면을 나누는 원리 시각적으로 표현

2. 재귀를 어떻게 사용해서 최적화하는지 설명

   • 배열을 직접 만들지 않고 O(N)에 해결
   • 각 단계에서 half^2을 이용해 계산량을 줄이는 원리 >> 그냥 이전까지의 연산 다 더한다음 새로 시작하면 되니까 +로도 해결이 되어버림 ;;;

3. 오답 노트 정리

   • 정답보고 이해할 때 사분면 판별까지는 괜찮은데
   • 좌표 조정 (r-half, c-half)에서 이해하는데 시간 좀 걸렸고
   • 방문 순서 계산에서 half^2 곱하는 부분 이해하는데 또한 시간 좀 걸렸음 ;;
   • 그런데 애당초 이거 아예 접근방식이 틀렸어서 다시 풀어봐야 할 듯... 하 ;;; 분할정복 이거 저번에도 틀렸던 것 같은데;;;;

---

잊지 말자

• 배열을 직접 만들지 않고도 방문 순서를 O(N)으로 구하는 법 → 재귀 활용하면 쉬움
• 실수하기 쉬운 포인트 → 사분면 판별, 좌표 조정, half^2 점프 개념