[CS-008][중급] 재귀로 문제를 나누고 합쳐 해결하기
페이지 정보
본문
[이번 수업]
재귀 함수가 멈추는 원리를 이해하고, 큰 문제를 작은 문제로 나눈 뒤 답을 합치는 분할정복을 병합 정렬로 연습합니다.
[선수지식]
CS-003의 함수, CS-004의 리스트, CS-006의 시간·공간복잡도, CS-007의 정렬 기초를 알아야 합니다.
[학습목표]
1. 종료 조건과 재귀 단계를 구분한다.
2. 호출 스택이 깊어지는 이유를 설명한다.
3. 분할·정복·결합 단계로 병합 정렬을 구현한다.
[핵심개념]
재귀(Recursion)는 함수가 자기 자신을 호출해 같은 모양의 더 작은 문제를 푸는 방법입니다. 반드시 바로 답을 낼 수 있는 종료 조건(Base Case)과 문제를 줄이는 재귀 단계(Recursive Case)가 있어야 합니다. 예를 들어 길이가 0 또는 1인 목록은 이미 정렬되어 있고, 더 긴 목록은 절반으로 나눌 수 있습니다. 입력이 매번 종료 조건에 가까워지는지도 확인해야 합니다.
호출할 때마다 매개변수·지역 변수·돌아갈 위치가 호출 스택(Call Stack)에 쌓입니다. 호출이 끝나면 역순으로 꺼내집니다. 종료 조건이 없거나 입력이 줄지 않으면 스택이 계속 깊어지고, Python은 최대 재귀 깊이를 넘을 때 `RecursionError`를 냅니다. 제한을 무작정 높이기보다 종료 조건과 입력 크기를 점검하고, 매우 깊은 선형 작업은 반복문이나 명시적 스택을 검토합니다.
분할정복(Divide and Conquer)은 문제를 작은 부분으로 나누고(Divide), 각 부분을 해결하고(Conquer), 답을 합치는(Combine) 설계입니다. 병합 정렬은 목록을 절반씩 나눠 길이 1로 만든 뒤, 정렬된 두 목록의 앞 값을 비교하며 합칩니다. 각 단계에서 전체 원소를 합치는 데 선형 시간이 들고 단계 수는 로그 규모라 전체 시간복잡도는 O(n log n)입니다. 새 목록을 만들기 때문에 추가 공간도 사용합니다.
재귀가 항상 더 빠른 것은 아닙니다. 트리처럼 구조 자체가 반복되는 문제나 균형 있게 나눌 수 있는 문제에 잘 맞지만, 함수 호출 비용과 스택 공간이 듭니다. 실무 정렬은 검증되고 최적화된 `sorted()`나 `list.sort()`를 우선하고, 직접 구현은 원리 학습이나 특별한 요구가 있을 때 사용합니다.
[따라하기]
다음을 `merge_sort_demo.py`로 저장합니다. 원본을 바꾸지 않고 새 정렬 목록을 반환하며 재귀 호출 횟수도 셉니다.
```python
calls = 0
def merge(left, right):
result = []
i = j = 0
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
return result + left[i:] + right[j:]
def merge_sort(values):
global calls
calls += 1
if len(values) <= 1:
return values[:]
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
return merge(left, right)
data = [7, 2, 9, 1, 5, 3]
print("정렬 결과:", merge_sort(data))
print("원본 유지:", data)
print("호출 횟수:", calls)
```
Windows PowerShell에서는 `py merge_sort_demo.py`, macOS·Linux에서는 `python3 merge_sort_demo.py`를 실행합니다. 예상 결과입니다.
```text
정렬 결과: [1, 2, 3, 5, 7, 9]
원본 유지: [7, 2, 9, 1, 5, 3]
호출 횟수: 11
```
[흔한 실수]
- 종료 조건을 빼거나 도달할 수 없게 만든다.
- 재귀 호출의 입력을 이전보다 작게 만들지 않는다.
- 결합 단계에서 남은 원소를 결과에 붙이지 않는다.
- 재귀가 반복문보다 항상 빠르다고 생각한다.
- 원본 변경 여부와 추가 메모리를 확인하지 않는다.
[보안 주의]
외부에서 받은 중첩 JSON, 폴더 구조, 수식은 깊이와 크기를 제한한 뒤 처리합니다. 공격자가 지나치게 깊은 입력을 보내면 스택·CPU·메모리를 소모시킬 수 있습니다. 재귀 제한을 사용자 입력에 맞춰 올리지 말고 최대 깊이, 노드 수, 처리 시간을 정합니다. 심볼릭 링크가 있는 폴더 순회에서는 방문 경로와 경계도 확인하며 실습은 본인 소유 로컬 데이터로만 합니다.
[직접 해볼 과제]
빈 목록, 원소 하나, 중복 값이 있는 목록을 각각 정렬하세요. 세 결과가 `sorted()`와 같은지 `assert`로 확인하고 호출 횟수가 입력 길이에 따라 어떻게 달라지는지 기록합니다.
[확인문제]
1. 재귀 함수에 종료 조건이 반드시 필요한 이유는 무엇인가요?
2. 분할정복의 세 단계는 무엇인가요?
3. 매우 깊은 선형 문제에서 반복문을 검토해야 하는 이유는 무엇인가요?
[다음 학습]
다음 TOOL-008에서는 로그를 남기고 문제를 재현하는 방법을 배웁니다.
[공식 참고 자료]
- Python 재귀 깊이 문서: https://docs.python.org/3/library/sys.html#sys.getrecursionlimit
- Python 정렬 안내서: https://docs.python.org/3/howto/sorting.html
- MIT 병합 정렬 강의 자료: https://ocw.mit.edu/courses/6-100l-introduction-to-cs-and-programming-using-python-fall-2022/mit6_100l_f22_lec24.pdf
재귀 함수가 멈추는 원리를 이해하고, 큰 문제를 작은 문제로 나눈 뒤 답을 합치는 분할정복을 병합 정렬로 연습합니다.
[선수지식]
CS-003의 함수, CS-004의 리스트, CS-006의 시간·공간복잡도, CS-007의 정렬 기초를 알아야 합니다.
[학습목표]
1. 종료 조건과 재귀 단계를 구분한다.
2. 호출 스택이 깊어지는 이유를 설명한다.
3. 분할·정복·결합 단계로 병합 정렬을 구현한다.
[핵심개념]
재귀(Recursion)는 함수가 자기 자신을 호출해 같은 모양의 더 작은 문제를 푸는 방법입니다. 반드시 바로 답을 낼 수 있는 종료 조건(Base Case)과 문제를 줄이는 재귀 단계(Recursive Case)가 있어야 합니다. 예를 들어 길이가 0 또는 1인 목록은 이미 정렬되어 있고, 더 긴 목록은 절반으로 나눌 수 있습니다. 입력이 매번 종료 조건에 가까워지는지도 확인해야 합니다.
호출할 때마다 매개변수·지역 변수·돌아갈 위치가 호출 스택(Call Stack)에 쌓입니다. 호출이 끝나면 역순으로 꺼내집니다. 종료 조건이 없거나 입력이 줄지 않으면 스택이 계속 깊어지고, Python은 최대 재귀 깊이를 넘을 때 `RecursionError`를 냅니다. 제한을 무작정 높이기보다 종료 조건과 입력 크기를 점검하고, 매우 깊은 선형 작업은 반복문이나 명시적 스택을 검토합니다.
분할정복(Divide and Conquer)은 문제를 작은 부분으로 나누고(Divide), 각 부분을 해결하고(Conquer), 답을 합치는(Combine) 설계입니다. 병합 정렬은 목록을 절반씩 나눠 길이 1로 만든 뒤, 정렬된 두 목록의 앞 값을 비교하며 합칩니다. 각 단계에서 전체 원소를 합치는 데 선형 시간이 들고 단계 수는 로그 규모라 전체 시간복잡도는 O(n log n)입니다. 새 목록을 만들기 때문에 추가 공간도 사용합니다.
재귀가 항상 더 빠른 것은 아닙니다. 트리처럼 구조 자체가 반복되는 문제나 균형 있게 나눌 수 있는 문제에 잘 맞지만, 함수 호출 비용과 스택 공간이 듭니다. 실무 정렬은 검증되고 최적화된 `sorted()`나 `list.sort()`를 우선하고, 직접 구현은 원리 학습이나 특별한 요구가 있을 때 사용합니다.
[따라하기]
다음을 `merge_sort_demo.py`로 저장합니다. 원본을 바꾸지 않고 새 정렬 목록을 반환하며 재귀 호출 횟수도 셉니다.
```python
calls = 0
def merge(left, right):
result = []
i = j = 0
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
return result + left[i:] + right[j:]
def merge_sort(values):
global calls
calls += 1
if len(values) <= 1:
return values[:]
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
return merge(left, right)
data = [7, 2, 9, 1, 5, 3]
print("정렬 결과:", merge_sort(data))
print("원본 유지:", data)
print("호출 횟수:", calls)
```
Windows PowerShell에서는 `py merge_sort_demo.py`, macOS·Linux에서는 `python3 merge_sort_demo.py`를 실행합니다. 예상 결과입니다.
```text
정렬 결과: [1, 2, 3, 5, 7, 9]
원본 유지: [7, 2, 9, 1, 5, 3]
호출 횟수: 11
```
[흔한 실수]
- 종료 조건을 빼거나 도달할 수 없게 만든다.
- 재귀 호출의 입력을 이전보다 작게 만들지 않는다.
- 결합 단계에서 남은 원소를 결과에 붙이지 않는다.
- 재귀가 반복문보다 항상 빠르다고 생각한다.
- 원본 변경 여부와 추가 메모리를 확인하지 않는다.
[보안 주의]
외부에서 받은 중첩 JSON, 폴더 구조, 수식은 깊이와 크기를 제한한 뒤 처리합니다. 공격자가 지나치게 깊은 입력을 보내면 스택·CPU·메모리를 소모시킬 수 있습니다. 재귀 제한을 사용자 입력에 맞춰 올리지 말고 최대 깊이, 노드 수, 처리 시간을 정합니다. 심볼릭 링크가 있는 폴더 순회에서는 방문 경로와 경계도 확인하며 실습은 본인 소유 로컬 데이터로만 합니다.
[직접 해볼 과제]
빈 목록, 원소 하나, 중복 값이 있는 목록을 각각 정렬하세요. 세 결과가 `sorted()`와 같은지 `assert`로 확인하고 호출 횟수가 입력 길이에 따라 어떻게 달라지는지 기록합니다.
[확인문제]
1. 재귀 함수에 종료 조건이 반드시 필요한 이유는 무엇인가요?
2. 분할정복의 세 단계는 무엇인가요?
3. 매우 깊은 선형 문제에서 반복문을 검토해야 하는 이유는 무엇인가요?
[다음 학습]
다음 TOOL-008에서는 로그를 남기고 문제를 재현하는 방법을 배웁니다.
[공식 참고 자료]
- Python 재귀 깊이 문서: https://docs.python.org/3/library/sys.html#sys.getrecursionlimit
- Python 정렬 안내서: https://docs.python.org/3/howto/sorting.html
- MIT 병합 정렬 강의 자료: https://ocw.mit.edu/courses/6-100l-introduction-to-cs-and-programming-using-python-fall-2022/mit6_100l_f22_lec24.pdf
- 이전글[TOOL-008][중급] 로그로 오류를 다시 만들고 원인 찾기 26.09.03
- 다음글[CORE-008][중급] 가상머신과 컨테이너 알맞게 고르기 26.09.03
댓글목록
등록된 댓글이 없습니다.