재귀, 완전탐색과 분할정복

1. 재귀

재귀 함수는 자기 자신을 직접 또는 간접적으로 호출한다. 올바른 재귀에는 두 요소가 필요하다.

• 기저 조건: 더 이상 호출하지 않고 값을 반환하는 조건
• 재귀 단계: 문제 크기를 줄여 자기 자신을 호출하는 단계

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

각 호출의 지역변수와 복귀 위치는 호출 스택에 저장된다. 재귀 깊이가 너무 크면 스택 오버플로가 발생할 수 있다.

2. 완전탐색과 백트래킹

완전탐색은 가능한 모든 후보를 확인한다. 경우의 수가 작다면 가장 확실한 방법이지만 입력이 커지면 지수적으로 느려질 수 있다.

백트래킹은 후보를 만들다가 현재 선택으로는 정답이 될 수 없다고 판단하면 더 깊이 내려가지 않고 이전 단계로 돌아간다. 이를 가지치기라고 한다.

• 순열·조합 생성
• N-Queen
• 부분집합 합
• 경로 탐색

백트래킹은 최악의 경우 여전히 모든 후보를 볼 수 있으므로 항상 빠른 것은 아니다.

3. 분할정복

분할정복은 문제를 독립적인 작은 문제로 나누어 해결한 뒤 결과를 결합한다.

1. Divide: 문제를 부분 문제로 나눈다.
2. Conquer: 부분 문제를 해결한다.
3. Combine: 부분 결과를 합친다.

대표 예는 이진 탐색, 병합정렬, 퀵정렬이다.

병합정렬

배열을 절반으로 계속 나눈 뒤, 정렬된 두 배열을 병합한다. 각 레벨에서 O(n) 작업을 하고 레벨 수가 O(log n)이므로 전체 O(n log n)이다.

퀵정렬

피벗으로 배열을 분할한다. 분할이 균등하면 재귀 깊이가 O(log n)이지만 계속 한쪽으로 치우치면 O(n)이 되어 전체 O(n²)이 된다.

4. 재귀 관계의 직관

• T(n)=T(n-1)+O(1) → O(n)
• T(n)=2T(n/2)+O(n) → O(n log n)
• T(n)=T(n/2)+O(1) → O(log n)

복잡한 수학 증명보다 “부분 문제 수, 문제 크기, 각 단계의 추가 작업”을 파악하는 것이 중요하다.

5. 비교

6. 호출 스택 추적

factorial(4)의 호출은 다음처럼 쌓였다가 역순으로 반환한다.

factorial(4)
 └─ 4 * factorial(3)
       └─ 3 * factorial(2)
             └─ 2 * factorial(1)
                   └─ 1
반환: 1 → 2 → 6 → 24

재귀 호출 전 코드와 호출 후 코드의 실행 시점을 구분해야 트리 순회·하노이탑 문제를 정확히 추적할 수 있다.

7. 분할정복과 동적 계획법의 경계

분할정복은 부분 문제가 대체로 독립적이다. DP는 부분 문제가 겹치므로 결과를 저장한다.

병합정렬: 왼쪽 절반과 오른쪽 절반이 독립
피보나치: F(n-1)과 F(n-2)가 다시 같은 하위 문제를 계산

독립 부분 문제를 무조건 메모이제이션해도 이득이 거의 없을 수 있고, 겹치는 부분 문제를 저장하지 않으면 지수적 중복이 생길 수 있다.

8. 백트래킹 상태 설계

def permute(path, used):
    if len(path) == n:
        answer.append(path[:])
        return
    for i in range(n):
        if used[i]:
            continue
        used[i] = True
        path.append(nums[i])
        permute(path, used)
        path.pop()          # 선택 복원
        used[i] = False

백트래킹은 선택, 재귀, 선택 취소의 순서를 지킨다. 상태 복원을 빠뜨리면 다른 분기가 오염된다. 후보가 정답 조건을 만족할 가능성이 없을 때 호출 전에 가지치기한다.

9. 경우의 수와 복잡도

• n개 순열: n!
• n개 중 r개 조합: C(n,r)
• n개의 부분집합: 2^n

출력 자체가 n!개라면 모든 순열을 생성하는 알고리즘은 최소한 출력 크기만큼 시간이 필요하다. 가지치기는 실제 탐색량을 줄이지만 최악 상한이 여전히 지수적일 수 있다.

10. 재귀 관계 해석

병합정렬의 재귀 트리는 레벨마다 총 n개 원소를 처리하고 레벨 수가 log n이다.

n                 비용 n
n/2  n/2          비용 n
4개 n/4           비용 n
...
리프 n개          레벨 수 log n

퀵정렬은 균형 분할이면 같은 구조지만, T(n)=T(n-1)+Θ(n)이면 Θ(n²)이다.

11. 꼬리재귀와 반복 변환

재귀 호출 뒤 추가 계산이 없는 꼬리재귀는 반복문으로 바꾸기 쉽다. 언어·컴파일러가 꼬리호출 최적화를 보장하지 않으면 꼬리재귀도 호출 스택을 사용할 수 있으므로 무조건 O(1) 공간이라고 단정하지 않는다.

12. 가지치기 예시

부분집합 합에서 모든 수가 양수이고 현재 합이 목표를 초과했다면 더 선택해도 줄어들지 않으므로 중단할 수 있다. 음수가 허용되면 같은 가지치기는 안전하지 않다. 가지치기의 정당성 조건을 확인해야 한다.

최종 확인 문제

1. n개 원소의 모든 부분집합 수와 모든 순열 수를 각각 쓰시오.
2. 백트래킹 코드에서 재귀 호출 후 선택 상태를 복원해야 하는 이유는 무엇인가?
3. T(n)=T(n-1)+Θ(n)의 복잡도를 구하시오.
4. 분할정복과 동적 계획법을 구분하는 대표 기준을 설명하시오.
5. 양수만 있는 부분집합 합에서 현재 합이 목표를 초과하면 가지치기할 수 있지만 음수가 있으면 위험한 이유를 설명하시오.