# 재귀 알고리즘 (Recursive)


## 재귀 알고리즘이란?
- 자신이 수행할 작업을 처리하는 도중에 자기 자신을 호출하여 작업을 수행하는 알고리즘
- 함수나 프로시저가 자기 자신을 호출하는 것
- 재귀 알고리즘은 깊이가 무한정하게 들어갈 수 있으며, 무한루프에 빠질 가능성도 있으므로 조심해서 사용해야 한다
- 장점
- 코드가 간결하고 이해하기 쉽다
- 명확하게 해결하고자 하는 문제를 표현하기 쉽다
- 단점
- 재귀 알고리즘은 반복문보다 실행 속도가 느릴 수 있다
- 함수 호출에 따른 메모리 공간이 필요하므로 메모리 사용량이 증가할 수 있다
- 재귀 호출이 무한루프에 빠질 가능성이 있으므로, 종료 조건을 반드시 설정해야 한다

## 재귀 알고리즘 예시

1. 팩토리얼 계산 문제
- 정수 N이 주어졌을 때, N!을 계산하는 문제
2. 피보나치 수열 문제
- 정수 N이 주어졌을 때, 피보나치 수열의 N번째 항을 구하는 문제
3. 이진 검색 문제
- 정렬된 배열과 찾고자 하는 값이 주어졌을 때, 이진 검색을 이용하여 해당 값의 인덱스를 구하는 문제
4. 하노이의 탑 문제
- N개의 원판이 있는 탑이 있을 때, 모든 원판을 다른 기둥으로 옮기는 문제
5. 최대공약수 문제
- 두 수가 주어졌을 때, **유클리드 호재법**을 이용하여 최대공약수를 구하는 문제

> 재귀 문제는 반복문으로 대체가 가능하다. 반복문이 아닌 재귀를 사용할 경우 메모리 측면에서 비효율적이기 때문에 알고리즘 문제를 풀 때 적합한 방법은 아니다.

### 하노이탑 문제

- 백준 알고리즘 1914번 ==[링크](https://www.acmicpc.net/problem/1914)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 수도코드 해답 예

1. 원판의 개수 N을 입력받는다.
2. 최소 이동 횟수를 계산한다 (2^N - 1).
3. 최소 이동 횟수를 출력한다.
4. 원판 개수가 20개 이하인 경우 이동 과정을 출력한다.
5. 하노이 탑 알고리즘을 구현한다 (재귀 함수).
    a. 이동할 원판이 없는 경우 반환한다.
    b. N-1개의 원판을 출발 기둥에서 보조 기둥으로 이동한다 (하노이 탑 알고리즘 호출).
    c. N번째 원판을 출발 기둥에서 도착 기둥으로 이동한다.
    d. N-1개의 원판을 보조 기둥에서 도착 기둥으로 이동한다 (하노이 탑 알고리즘 호출).

#### 소스코드 해답 예

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 원판의 개수 입력

        // 최소 이동 횟수 계산 및 출력
        BigInteger minMoves = BigInteger.valueOf(2).pow(N).subtract(BigInteger.ONE);
        System.out.println(minMoves);

        // 원판 개수가 20개 이하인 경우 이동 과정 출력
        if (N <= 20) {
            hanoi(N, 1, 2, 3);
        }
    }

    // 하노이 탑 알고리즘 구현
    public static void hanoi(int N, int from, int aux, int to) {
        if (N == 0) return; // 이동할 원판이 없는 경우 반환

        hanoi(N - 1, from, to, aux); // N-1개의 원판을 출발 기둥에서 보조 기둥으로 이동
        System.out.println(from + " " + to); // N번째 원판을 출발 기둥에서 도착 기둥으로 이동
        hanoi(N - 1, aux, from, to); // N-1개의 원판을 보조 기둥에서 도착 기둥으로 이동
    }
}

### 최대공약수 구하기

#### 유클리드 호제법(Euclidean algorithm)

- 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘
- 원리
- 두 수 a와 b (a > b)의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다
- 즉, GCD(a, b) = GCD(b, a % b)
- 예시 : a = 56이고 b = 48일 때
1. `GCD(56, 48) = GCD(48, 56 % 48) = GCD(48, 8)`
2. `GCD(48, 8) = GCD(8, 48 % 8) = GCD(8, 0)`
3. b가 0이 되었으므로, a와 b의 최대공약수는 8이다

#### 최소공배수를 구하는 방법
- 유클리드 호제법을 사용하여 최대공약수를 구했다면, 최소공배수(LCM, Least Common Multiple)도 쉽게 구할 수 있다.
- LCM(a, b) = (a * b) / GCD(a, b)

---

# 분할 정복 알고리즘 (Divide & Conquer)


## 분할 정복이란?
- 하나의 문제를 작은 부분 문제로 나누어 해결하는 알고리즘
- 문제를 분할하고, 각 부분 문제를 해결하여 전체 문제의 해결책을 찾는다
- 분할 정복 알고리즘은 다음과 같은 세 단계로 이루어진다
- 분할(Divide) 단계: 문제를 작은 부분 문제로 분할한다
- 정복(Conquer) 단계: 부분 문제를 해결한다
- 결합(Combine) 단계: 부분 문제의 해결책을 결합하여 전체 문제의 해결책을 구한다
- 장점
- 문제를 나누어서 해결하므로, 병렬 처리에 적합하다
- 문제를 나누어서 해결하기 때문에, 코드가 간결하고 이해하기 쉽다
- 분할된 문제가 서로 독립적이기 때문에, 처리 속도가 빠르다
- 단점
- 분할 단계에서 부분 문제를 작게 나누면 오버헤드가 발생하여 실행 시간이 증가할 수 있다
- 문제를 작게 나누어서 해결하므로, 스택 오버플로우 등의 문제가 발생할 수 있다

> 분할정복과 재귀함수
> - 분할정복과 재귀함수는 유사하지만 기본 원리와 적용 방식에 차이가 있다
> - 재귀 알고리즘은 문제를 해결하기 위해 자기 자신을 호출하는 방식으로 동작하며, 이는 분할 정복 알고리즘의 한 가지 구현 방식일 뿐이며, 두 알고리즘은 독립적인 개념으로 이해해야 한다.
> - 분할 정복은 문제를 부분 문제로 나누고, 각 부분 문제를 정복하여 원래 문제의 해결책을 찾는 전략이며, 재귀 알고리즘은 함수가 자기 자신을 다시 호출하는 방식으로 문제를 해결하는 전략
> - 분할 정복 알고리즘은 문제를 작은 부분으로 나누어 해결하는 접근 방식이기 때문에, 재귀 함수가 아닌 반복문을 사용하여 구현할 수도 있다. 예를 들어 이진 검색 알고리즘은 반복문을 사용하여 구현할 수도 있으며, 이 경우에도 작은 부분 문제로 나누어 해결하는 분할 정복 알고리즘의 전략을 따른다

## 분할 정복 알고리즘 예시

1. 병합 정렬(Merge Sort)
- 정렬되지 않은 배열이 주어졌을 때, 분할 정복 알고리즘을 이용하여 배열을 정렬하는 문제
2. 퀵 정렬(Quick Sort)
- 정렬되지 않은 배열이 주어졌을 때, 분할 정복 알고리즘을 이용하여 배열을 정렬하는 문제
3. 거듭제곱 계산 문제
- 양의 정수 a와 b가 주어졌을 때, a의 b제곱을 계산하는 문제
4. 이항 계수 계산 문제
- 양의 정수 n과 k가 주어졌을 때, 이항 계수(nCk)를 계산하는 문제
5. 최대 수익 문제
- 길이가 n인 정수 배열이 주어졌을 때, 두 수의 차이가 최대가 되는 경우의 수익을 구하는 문제

> 일반적으로 다음과 같은 특징이 보이면 분할 정복 알고리즘을 고려해본다
> - 문제를 독립적인 부분 문제로 나눌 수 있는 경우
> - 부분 문제의 해답을 병합하는 과정이 존재하는 경우
> - 중복되는 부분 문제가 없는 경우
> - 재귀적 구조를 가지고 있는 경우

### 병합 정렬 (Merge sort)


- 배열을 반으로 나누어 각각을 정렬한 후, 정렬된 두 배열을 병합하여 전체를 정렬하는 알고리즘
- 원리
1. 분할(Divide): 주어진 배열이나 리스트를 반으로 나눈다. 이 과정을 더 이상 나눌 수 없을 때까지 반복한다. 이렇게 되면 모든 부분 배열은 하나의 원소를 가지게 된다.
2. 정복(Conquer): 가장 작은 부분 배열(하나의 원소를 가진 배열)부터 시작하여, 인접한 두 부분 배열을 정렬하면서 병합한다. 이렇게 정렬된 배열은 다시 인접한 정렬된 배열과 병합되어 최종 정렬된 배열을 얻을 때까지 반복한다.
3. 병합(Merge): 인접한 두 부분 배열을 정렬하면서 병합하는 과정. 각 부분 배열의 첫 번째 원소를 비교하여 더 작은 값을 결과 배열에 넣고, 해당 원소를 부분 배열에서 제거한다. 이 과정을 두 부분 배열의 원소가 모두 소진될 때까지 반복한 후, 남은 원소가 있는 배열의 나머지 원소를 결과 배열에 추가한다.
- 
- 장점
- 안정적인 정렬 알고리즘으로, 입력 데이터의 분포와 순서에 영향을 받지 않는다.
- 최악의 경우에도 시간 복잡도가 O(nlogn)으로 빠르며, 대부분의 경우에 빠른 실행 속도를 보인다.
- 분할 정복 알고리즘을 사용하므로, 병렬 처리가 가능하다.
- 추가적인 메모리가 필요하지만, 입력 데이터의 크기가 크더라도 메모리 사용량이 고정적이며, 크기가 큰 데이터에 대해서도 처리가 가능하다.
- 단점
- 입력 데이터의 크기가 작은 경우에는 다른 정렬 알고리즘들보다 느린 실행 속도를 보일 수 있다.
- 추가적인 메모리 공간이 필요하므로, 메모리 사용량이 더 많아질 수 있다.
- 합병 과정에서 인덱스를 이동하는 등의 연산이 필요하므로, 다른 알고리즘들보다 연산 속도가 느릴 수 있다.
- 시간복잡도 : `O(nlogn)`
- 입력 배열의 크기가 n일 때, 문제를 분할하는 단계 수는 log2(n)이므로, 분할된 문제를 해결하는 데 필요한 시간은 `O(logn)` 소요
- 병합 과정에서는 두 배열을 비교하여 더 작은 값을 임시 배열에 저장하고, 임시 배열을 입력 배열로 복사하는 과정을 거치므로, 상수 시간인 `O(n)`이 소요
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

**병합 정렬 코드**

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);  // 왼쪽 부분 배열을 정렬한다
            mergeSort(arr, mid + 1, right);  // 오른쪽 부분 배열을 정렬한다
            merge(arr, left, mid, right);  // 정렬된 두 부분 배열을 병합한다
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[arr.length];  // 임시 배열을 생성한다
        int i = left;  // 왼쪽 부분 배열의 시작 인덱스
        int j = mid + 1;  // 오른쪽 부분 배열의 시작 인덱스
        int k = left;  // 병합된 배열의 시작 인덱스

        while (i <= mid && j <= right) {  // 왼쪽 부분 배열과 오른쪽 부분 배열을 비교하며 병합한다
            if (arr[i] <= arr[j]) {  // 왼쪽 요소가 작거나 같은 경우
                temp[k++] = arr[i++];  // 왼쪽 요소를 임시 배열에 저장하고 인덱스를 증가시킨다
            } else {  // 오른쪽 요소가 작은 경우
                temp[k++] = arr[j++];  // 오른쪽 요소를 임시 배열에 저장하고 인덱스를 증가시킨다
            }
        }

        // 남은 요소들을 임시 배열에 복사한다
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 임시 배열에 저장된 정렬된 요소들을 원래 배열로 복사한다
        for (int index = left; index < k; index++) {
            arr[index] = temp[index];
        }
    }

    public static void main(String[] args) {
        int[] arr = {21, 10, 12, 20, 25, 13, 15, 22};
        int left = 0;
        int right = arr.length - 1;

        mergeSort(arr, left, right);

        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

---

### 퀵 정렬 (Quick sort)


- pivot 값을 기준으로 배열을 두 부분으로 분할하고, 각 부분을 재귀적으로 정렬하는 알고리즘
- 추가 메모리를 거의 사용하지 않는 인플레이스(in-place) 정렬 알고리즘이기 때문에, 메모리 사용량 측면에서 장점이 있다
- 원리
1. 피벗 선택(Select Pivot): 배열에서 피벗 엘리먼트를 선택한다. 피벗을 선택하는 방법에는 여러 가지가 있으며, 일반적으로는 배열의 첫 번째 원소, 마지막 원소 또는 무작위로 선택한 원소를 사용한다.
2. 분할(Partition): 피벗을 기준으로 배열을 두 부분으로 분할한다. 피벗보다 작은 값은 피벗 왼쪽에 위치하고, 피벗보다 큰 값은 피벗 오른쪽에 위치하게 된다. 분할 작업이 완료되면, 피벗은 최종 정렬 위치에 있게 된다.
3. 재귀 정렬(Recursive Sort): 피벗을 제외한 왼쪽 부분 배열과 오른쪽 부분 배열을 다시 퀵 정렬로 정렬한다. 이 과정은 부분 배열의 크기가 1 또는 0이 될 때까지 재귀적으로 반복된다.
- 
- 장점
- 평균적으로 가장 빠른 실행 속도를 보이는 정렬 알고리즘 중 하나
- 입력 데이터의 크기가 큰 경우에도 빠른 실행 속도를 보인다
- 추가적인 메모리 공간이 필요하지 않으므로, 메모리 사용량이 적다
- 분할 정복 알고리즘을 사용하므로, 병렬 처리가 가능하다
- 단점
- pivot 값을 잘못 선택하면, 최악의 경우에는 시간 복잡도가 O(n^2)까지 증가할 수 있다. 이를 방지하기 위해, pivot 값을 잘 선택하는 것이 중요하다
- 입력 데이터가 무작위로 주어지는 경우에는 평균적으로 빠른 실행 속도를 보이지만, 이미 정렬되어 있는 경우나 입력 데이터의 분포가 균일하지 않은 경우에는 실행 속도가 저하될 수 있다
- 항상 안정적인 정렬을 보장하지 않는다
- 시간복잡도
- 평균 : O(nlogn)
- 최악 : O(n^2)

**퀵 정렬 코드**

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);  // 피벗을 선택하고, 분할 작업을 수행한다
            quickSort(arr, left, pivot - 1);  // 피벗을 기준으로 왼쪽 부분 배열을 정렬한다
            quickSort(arr, pivot + 1, right);  // 피벗을 기준으로 오른쪽 부분 배열을 정렬한다
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];  // 피벗을 오른쪽 끝 요소로 선택한다
        int i = left - 1;  // 피벗보다 작은 요소들을 저장할 인덱스

        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);  // 피벗보다 작은 요소를 왼쪽으로 이동시킨다
            }
        }
        swap(arr, i + 1, right);  // 피벗을 정렬된 위치로 이동시킨다
        return i + 1;  // 피벗의 인덱스를 반환한다
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {21, 10, 12, 20, 25, 13, 15, 22};
        int left = 0;
        int right = arr.length - 1;

        quickSort(arr, left, right);  // 퀵 정렬을 수행한다

        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

---

> 안정 정렬 (Stable Sort)이란 중복된 값을 입력 순서와 동일하게 정렬하는 알고리즘의 특성을 의미한다.
> - 안정 정렬 : 삽입정렬, 병합정렬, 버블정렬
> - 불안정 정렬 : 선택정렬, 퀵정렬

---
# 과제 : 백준 알고리즘 2609번 풀어보기 (유클리드 호제법)

- 백준 알고리즘 2609번 ==[링크](https://www.acmicpc.net/problem/2609)==

---

###### tags: `과외(하희영)`