재귀(Recursion) 자료구조 요약

Cheatsheet Content

### 재귀(Recursion) 정의 - **정의**: 함수가 더 작은 입력에 대해 자기 자신을 호출하여 문제를 해결하는 기법. - **두 가지 필수 구성 요소**: - **재귀(일반) 사례**: 문제를 더 작은 문제 인스턴스로 축소합니다. - 예: `factorial(n) = n * factorial(n - 1)` - **기본(Base) 사례**: 더 이상 재귀 호출 없이 해결되는 가장 작은 입력입니다. - 예: `factorial(0) = 1` - **항상 확인해야 할 두 가지 규칙**: - **작아짐(Smaller)**: 하나 이상의 인수가 엄격하게 감소해야 합니다. - **멈춤(Stop)**: 재귀는 결국 기본 사례에 도달해야 합니다. 그렇지 않으면 종료되지 않습니다. ### 재귀 설계 지침 재귀 솔루션이 올바른지 확인하려면 다음 질문에 "예"라고 답해야 합니다. 1. **기본 사례(Base Case)**: 알려진 솔루션이 있는 가장 작은 문제. - 비재귀적 중단 조건이 있는가? - 함수가 이 경우에 대해 올바른 결과를 반환하는가? 2. **더 작은 문제(Smaller Problem)**: 문제가 엄격하게 감소해야 합니다. - 각 재귀 호출이 문제 크기를 줄이는가? - 반복되는 호출이 결국 기본 사례에 도달하는가? 3. **올바른 구성(Correct Composition)**: 재귀 단계는 정확성을 유지해야 합니다. - 재귀 호출이 올바르게 작동한다고 가정할 때, 그 결과를 결합하면 원래 문제가 해결되는가? #### 예시: Factorial 구현 (C++) ```cpp // Pre: n >= 0 // Post: Return n! int Factorial(int n) { if (n == 0) { // 기본 사례 (멈춤) return 1; } else { // 재귀 사례 (더 작아짐) return n * Factorial(n - 1); } } ``` ### 재귀 추적(Recursion Trace) - 재귀 호출은 기본 사례에 도달할 때까지 호출 스택에 쌓입니다. - **Factorial(4) 추적 예시**: - Factorial(4) 호출 - Factorial(3) 호출 - Factorial(2) 호출 - Factorial(1) 호출 - Factorial(0) 호출 (기본 사례, 1 반환) - Factorial(1)은 1 * 1 = 1 반환 - Factorial(2)는 2 * 1 = 2 반환 - Factorial(3)은 3 * 2 = 6 반환 - Factorial(4)은 4 * 6 = 24 반환 ### 주요 알고리즘 설계 패러다임 - **탐욕법(Greedy)**: 각 단계에서 지역적으로 최적의 선택을 합니다. 전역적으로 최적의 솔루션을 제공하지 않을 수 있습니다. - **동적 계획법(Dynamic Programming)**: 문제를 겹치는 하위 문제로 분해하고, 중간 결과를 저장하여 중복 계산을 피합니다 (메모이제이션/타뷸레이션). - **분할 정복(Divide-and-Conquer)**: 문제를 더 작은 하위 문제로 나누고, 독립적으로 해결한 다음, 그 결과를 결합합니다. - **재귀는 분할 정복을 구현하는 자연스러운 방법입니다.** ### 재귀와 분할 정복 - **분할 정복 (일반 전략)**: - 문제를 더 작은 하위 문제로 나눕니다. - 각 하위 문제를 해결합니다. - 솔루션을 결합합니다. - **재귀 (특수 사례)**: - 문제를 자기 자신보다 작은 인스턴스로 나눕니다. - 동일한 함수를 호출하여 해결합니다. - 반환할 때 결과를 결합합니다. - 기본 사례에서 종료됩니다. ### 예시: `ValueInList` 설계 - **문제**: 배열 `list.info[start_index ... list.length - 1]`에서 `value`가 나타나는지 여부를 `true` 또는 `false`로 반환하는 재귀 함수 `bool ValueInList(const ListType & list, int value, int start_index)`를 작성합니다. - **재귀 아이디어**: `(value가 첫 번째 위치에 있는가?)` OR `(value가 나머지 리스트에 있는가?)` - **문제 크기**: `size = list.length - start_index`. 각 재귀 호출은 `start_index`를 증가시키므로 `size`는 엄격하게 감소합니다. - **기본 사례**: - `list.info[start_index] == value`이면 `true` 반환 (값을 찾음). - `start_index == list.length - 1`이면 `false` 반환 (리스트의 끝에 도달했고 값을 찾지 못함). - **재귀 사례**: - `return ValueInList(list, value, start_index + 1)` (나머지 리스트 검색). #### `ValueInList` 구현 (C++) ```cpp bool ValueInList(const ListType & list, int value, int start_index) { if (list.info[start_index] == value) { return true; // 기본 사례 1 (찾음) } else if (start_index == list.length - 1) { return false; // 기본 사례 2 (못 찾음) } else { return ValueInList(list, value, start_index + 1); // 재귀 사례 (더 작아짐) } } ``` ### 이진 탐색(Binary Search) - **전제 조건**: 배열은 오름차순으로 정렬되어 있어야 합니다. - **작동 방식**: 중간 요소를 반복적으로 검사하여 탐색 범위를 절반으로 줄입니다. - **세 가지 주요 경우**: - **대상을 찾음 (기본 사례)**: `target == data[mid]`이면 성공적으로 종료됩니다. - **왼쪽 절반 탐색 (재귀 사례)**: `target data[mid]`이면 새 범위는 `[mid + 1, high]`입니다. - **탐색 실패 (기본 사례)**: `low > high`이면 후보 구간이 비어 있고 대상이 배열에 존재하지 않습니다. #### 이진 탐색 구현 (C++) ```cpp bool BinarySearch(const int data[], int target, int low, int high) { if (low > high) // 기본 사례 (못 찾음) return false; else { int mid = low + (high - low) / 2; // 오버플로우 방지 if (target == data[mid]) return true; // 기본 사례 (찾음) else if (target ### 하노이의 탑(Towers of Hanoi) - **목표**: 모든 디스크를 A(원본)에서 C(대상)로 B(보조) 막대를 사용하여 옮깁니다. - **규칙**: - 한 번에 하나의 디스크만 옮길 수 있습니다. - 큰 디스크를 작은 디스크 위에 놓을 수 없습니다. - **재귀 전략**: 1. `n-1`개의 디스크를 A에서 B로 옮깁니다 (C 사용). 2. 가장 큰 디스크 (`n`번째 디스크)를 A에서 C로 옮깁니다. 3. `n-1`개의 디스크를 B에서 C로 옮깁니다 (A 사용). - **작동 원리**: 각 단계는 문제 크기를 줄이고, 문제의 구조는 자기 유사하며, 우리는 동일한 문제의 더 작은 버전을 해결합니다. #### 하노이의 탑 구현 (C++) ```cpp void TowerOfHanoi(int n, char from, char to, char aux) { if (n == 0) { // 기본 사례 return; } TowerOfHanoi(n - 1, from, aux, to); // n-1 디스크를 보조 막대로 이동 std::cout ### 재귀 알고리즘 분석 - **재귀에서 점화식(Recurrence Relation)으로**: 재귀는 자연스럽게 점화식으로 이어집니다. - **예시**: `T(n) = 2T(n/2) + n` (병합 정렬과 유사) - 이 방정식은 실행 시간을 함수로 표현하고, 더 작은 인스턴스(하위 문제) 측면에서 문제의 비용을 표현하며, 계산 구조를 상징적인 형태로 표현합니다. - **이진 탐색의 재귀 수준**: - `n` 크기의 배열이 주어졌을 때, 각 비교 후 남은 크기는 `n/2`로 줄어듭니다. - `k`번의 비교 후 남은 크기는 `n/2^k`입니다. - 기본 사례에 도달할 때 (남은 요소가 1개일 때), `n/2^k = 1`입니다. - 따라서 `2^k = n`이며, `k = log_2 n`입니다. - 이는 이진 탐색이 최대 `log_2 n`번의 재귀 수준을 가진다는 것을 의미합니다. ### 재귀적 제곱(Recursive Squaring) - **문제**: `p(x, n) = x^n`을 계산합니다. - **순진한(Naïve) 버전**: `p(x, n) = x * p(x, n-1)` (n번의 재귀 호출, n번의 곱셈). - **재귀적 제곱 버전 (더 효율적)**: - `p(x, n) = 1` if `n = 0` - `p(x, n) = x * p(x, (n-1)/2)^2` if `n`이 홀수 - `p(x, n) = p(x, n/2)^2` if `n`이 짝수 - **주요 관찰**: 각 재귀 호출은 `n`을 절반으로 줄입니다. 따라서 재귀 수준은 `log_2 n`입니다. - 중복 계산을 피하기 위해 재귀 결과를 변수에 저장하는 것이 중요합니다. #### 재귀적 제곱 구현 (C++) ```cpp double Power(double x, int n) { if (n == 0) return 1; double y = Power(x, n / 2); // 재귀 결과를 저장 if (n % 2 == 0) { return y * y; } else { return x * y * y; } } ``` - **점화식**: `T(n)`은 곱셈의 횟수입니다. - `T(n) = 1 + T(n/2)` (1번의 곱셈 + 절반 크기 문제) - `T(1) = 0` (기본 사례) ### 배열 재귀의 세 가지 스타일 1. **길이 기반(Length-based)**: 1씩 줄입니다 (예: 재귀 카운트다운, 배열 역순 출력). - 문제 크기: `n` - 재귀 호출: `F(n-1)` 2. **양 끝 기반(Index-based)**: 양 끝에서 줄입니다 (예: 양 끝에서 최대값 찾기). - 문제 크기: `hi - lo + 1` - 재귀 호출: `F(lo, hi-1)` 또는 `F(lo+1, hi)` 3. **반으로 분할(Divide & Conquer)**: 배열을 반으로 나눕니다 (예: 배열 분할을 통한 최대값 찾기, 이진 탐색). - 문제 크기: `n` - 재귀 호출: `F(n/2)` 또는 `2 * F(n/2)` - 각 스타일은 다른 점화식, 시간 복잡도 및 구현 세부 사항으로 이어집니다.