[정글 베이직 12] — 분할 정복 · 최댓값 찾기

📋 문제 소개

문제 설명

분할 정복(Divide and Conquer) 방식으로 배열의 최댓값을 찾는다. 배열을 반으로 나누고, 각 부분의 최댓값을 재귀적으로 구한 후 비교한다.

INPUT

정수 배열 arr, 시작 인덱스 left, 끝 인덱스 right

OUTPUT

배열의 최댓값 (정수)

예제

입력

arr = [3, 5, 1, 8, 2, 9, 4] left=0, right=6

출력

9

💡 힌트

Base case: left == right일 때 arr[left] 반환. 배열을 반으로 나눠 재귀 호출 후 max()로 비교.

① 문제 이해

항목	내용
문제	분할 정복으로 배열의 최댓값을 구한다.
입력	정수 배열 arr, 시작 인덱스 left, 끝 인덱스 right
예제	[3,5,1,8,2,9,4] → 9

② 핵심 아이디어

Divide → Conquer → Combine 세 단계로 생각한다.

# 수도코드
if left == right:          # 원소 1개 → 그게 최댓값
    return arr[left]
mid = (left+right)//2
L = solve(arr, left, mid)         # 왼쪽 최댓값
R = solve(arr, mid+1, right)      # 오른쪽 최댓값
return max(L, R)                  # 둘 중 큰 값

③ 코드 분석

def find_max_divide_conquer(arr, left, right):
    if left == right:              # ① 베이스 케이스
        return arr[left]

    mid = (left + right) // 2     # ② 중간 지점

    max_left  = find_max_divide_conquer(arr, left, mid)       # ③ 왼쪽
    max_right = find_max_divide_conquer(arr, mid + 1, right)  # ④ 오른쪽

    return max(max_left, max_right)  # ⑤ Combine

번호	코드	의미
①	left == right	원소가 1개 → 그게 최댓값, 재귀 종료
②	(left+right)//2	배열을 두 절반으로 나누는 기준점
③④	재귀 호출	각 절반에서 최댓값을 독립적으로 구한다
⑤	max(L, R)	Combine 단계 — 두 결과 중 큰 값 반환

④ 자주 하는 실수

⚠️ 베이스 케이스 없이 재귀 호출

left == right 조건이 없으면 무한 재귀로 RecursionError가 발생한다. 재귀 함수엔 항상 베이스 케이스가 먼저다.

⚠️ mid+1 빠뜨리기

오른쪽 재귀는 mid+1부터 시작해야 한다. mid부터 시작하면 mid 원소가 양쪽에 중복 포함된다.

💡 분할 정복의 3단계: Divide(나누기) → Conquer(정복) → Combine(합치기). 이 문제의 Combine은 단순히 max() 한 줄이다.

⑤ 시간복잡도

항목	값	이유
시간	O(n)	모든 원소를 한 번씩 방문
공간	O(log n)	재귀 호출 스택 깊이 = log n

⑥ 핵심 정리

• 재귀 함수는 베이스 케이스가 없으면 무한 루프다.
• Divide → Conquer → Combine 순서를 머릿속에 그리고 코딩하자.
• 오른쪽 절반 시작은 mid+1 — mid를 두 번 쓰면 안 된다.