알고리즘 풀이 노트

Q문제 코드

Java

public class Main {

    public static void main(String[] args) {
        int[] data = {3, 5, 8, 12, 17};
        System.out.println(func(data, 0, data.length - 1));
    }

    static int func(int[] a, int st, int end) {
        if (st >= end) return 0;           // 기저 조건
        int mid = (st + end) / 2;
        return a[mid] + Math.max(
            func(a, st, mid),             // 왼쪽 절반
            func(a, mid + 1, end)         // 오른쪽 절반
        );
    }
}

System.out.println() 출력 결과

func(0,4) = a[2] + max(func(0,2), func(3,4)) = 8 + max(8, 12) = 20

1문제 유형

재귀 함수의 실행 결과를 직접 추적(Trace)하는 문제입니다.
배열을 절반씩 분할하는 분할 정복(Divide & Conquer) 구조를 사용하며, 각 재귀 호출의 반환값이 어떻게 합산되는지 이해하는 것이 핵심입니다.

알고리즘 시험에서 자주 출제되는 「재귀 트레이싱」 유형으로, 호출 스택을 직접 그려가며 값을 추적해야 합니다.

2함수 동작 원리

🔴기저 조건: st ≥ end이면 0을 반환합니다. 구간이 원소 1개 이하로 쪼개지면 더 이상 계산하지 않습니다.
🔵분할: 현재 구간의 중간 인덱스 mid = (st+end)/2를 계산합니다.
🟢정복: a[mid]에 왼쪽(st~mid)과 오른쪽(mid+1~end) 재귀 결과 중 더 큰 값을 더하여 반환합니다.

3재귀 호출 트리

4단계별 계산 과정

호출	st	end	mid	a[mid]	왼쪽 결과	오른쪽 결과	max	반환값
func(0,0)	0	0	—	—	—	—	—	0 (기저)
func(1,1)	1	1	—	—	—	—	—	0 (기저)
func(0,1)	0	1	0	a[0]=3	func(0,0)=0	func(1,1)=0	max(0,0)=0	3+0 = 3
func(2,2)	2	2	—	—	—	—	—	0 (기저)
func(0,2)	0	2	1	a[1]=5	func(0,1)=3	func(2,2)=0	max(3,0)=3	5+3 = 8
func(3,3)	3	3	—	—	—	—	—	0 (기저)
func(4,4)	4	4	—	—	—	—	—	0 (기저)
func(3,4)	3	4	3	a[3]=12	func(3,3)=0	func(4,4)=0	max(0,0)=0	12+0 = 12
func(0,4)	0	4	2	a[2]=8	func(0,2)=8	func(3,4)=12	max(8,12)=12	8+12 = 20

5핵심 풀이 요약

📌최초 호출은 func(data, 0, 4)이며 배열 전체 구간을 다룹니다.
🔁각 호출은 구간을 절반으로 나누어, 중간값 + max(왼쪽 결과, 오른쪽 결과)를 반환합니다.
⛔st ≥ end인 경우(원소 1개 이하) 0을 반환하는 것이 기저 조건입니다.
🌿최종적으로 func(0,4)는 a[2]=8에 max(8, 12)=12를 더해 20을 반환합니다.

6최종 출력값

System.out.println() 출력 결과

func(0,4) = a[2] + max(func(0,2), func(3,4)) = 8 + max(8, 12) = 8 + 12 = 20

분할 정복 재귀 함수 출력값 추적