01. 재귀

1. Recursive Algorithm

 

• Recursive Algorithm : subproblem을 해결하기 위해 자기 자신을 호출하는 알고리즘

  • subproblem은 original problem과 유형 및 해결 방법이 동일하다.

• 이 알고리즘을 사용하면 복잡한 original problem을 subproblem의 합으로 구할 수 있다.

  • 예 : 정렬, 탐색, 수열 ... 

  • 몇몇 문제를 더 간단하게 해 준다.

    • 예 : 정렬, 탐색 ...

  • 몇몇 문제는 더 복잡하게 만들어서 치명적인 문제를 발생시킨다. 

    • 특히 재귀 호출 과정에서 중복 호출이 일어나는 경우 치명적으로 비효율적인 알고리즘이 된다.

    • 예 : 피보나치 수 구하기, 최적 행렬 곱 경로 ...

 

2. Recursive Algorithm 예시 1 - 재귀 알고리즘과 비재귀 알고리즘이 동일한 시간복잡도를 가지는 경우

• 수열 : n번째 원소는 자신과 성격이 똑같지만 순서가 하나 작은 원소(n-1번째 원소)에 특정 규칙을 적용한 결과

• 팩토리얼 : n! = n * (n-1)! / 재귀적 구조를 가진다.

  • 재귀 알고리즘

     

    factorial(n) = 1                                          (if   n=1)      $\leftarrow$ 이것을 Base case로 하는 알고리즘을 짠다                        = n*factorial(n-1)             (if   n>0)

     

     

  • 비재귀 알고리즘 : for 문으로 1씩 더해 가며 계속 곱해도 된다.

//입력값의 factorial을 두 가지 방법으로 출력하는 함수
//입력값을 받으면 해당 값의 팩토리얼을 재귀적 알고리즘과 비재귀적 알고리즘으로 계산한 후 각각을 출력
//하나의 출력 뒤에 바로 종료되는 간단한 함수이므로 scanf, printf 및 EOF코드를 쓰지 않음
//입력값은 10보다 같거나 작고 0보다 큰 자연수이다.

import java.util.Scanner;

public class factorial {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int input = scanner.nextInt();
        int recursiveResult = getFactorialR(input);
        int nonRecursiveResult = getFactorialNR(input);
        System.out.println(input + "! = "+ recursiveResult+"(by recursive algorithm)");
        System.out.println(input + "! = "+ nonRecursiveResult+"(by non-recursive algorithm)");
        
        scanner.close();

    }

    //재귀
    public static int getFactorialR(int input){
        if(input == 1)
            return 1;
        else
            return input*getFactorialR(input-1);
    }
    
    //비재귀
    public static int getFactorialNR(int input){
        int tmp = 1;
        for(int i=2; i<=input; i++){
            tmp = tmp*i;
        }
        return tmp;
    }
}

• 팩토리얼 문제를 해결하는 위 두 알고리즘 비교

• : 둘 다 $\theta(n)$의 시간 복잡도를 가진다.

• : getFactorialR은 getFactorialNR과 마찬가지로 1부터 n까지 하나씩 늘려가며 곱하는 알고리즘이나 다름없음

 

• 시간복잡도가 동일할 때 재귀 알고리즘을 선호할 이유: 코드의 간편성

  • 예 : 중첩 반복문n개의 원소 중 원소 k개를 고르는 경우의 수를 모두 출력하는 알고리즘을 구성한다고 하자.

    • k=4인 경우 $\Rightarrow$ 4중 for문으로 구성

    • k=5인 경우 $\Rightarrow$ 5중 for문으로 구성

      $\longrightarrow$ 그러나 재귀 알고리즘을 사용하면 '원소 고르고 재귀호출'  과정을 한 번만 더 반복하면 되기 때문에 더 간단한 코드를 짤 수 있다.

2. Recursive Algorithm 예시 2 - 재귀 알고리즘이 비재귀 알고리즘보다 비효율적인 경우

 

• 피보나치 수열

                  fib(n) = 1                if n= 1 or 2

                          = fib(n-1) + fib(n-2)     if n > 2

 

• 피보나치 수열 문제를 해결하는 재귀 알고리즘 vs 비재귀 알고리즘

//입력값 n을 받아 n번째 피보나치 수를 출력하는 함수
//재귀적 알고리즘을 사용한 결과값과 비재귀적 알고리즘을 사용한 결과값을 각각 출력한다.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int recursiveResult = getFiboR(n);
    int nonRecursiveResult = getFiboNR(n);
    System.out.println("Recursive : " + recursiveResult);
    System.out.println("Non_Recursive: "+ nonRecursiveResult);
    scanner.close();
  }

  //재귀
  public static int getFiboR(int n){
    if(n==0)
        return 0;
    else if(n==1)
        return 1;
    else{
        return getFiboR(n-1)+getFiboR(n-2);
    }
  }
  
  //비재귀
  public static int getFiboNR(int n){
    int tmp1 = 1;
    int tmp2 = 1;
    int result =0;
    for(int i=3; i<=n; i++){
      result = tmp1 + tmp2;
      tmp1 = tmp2;
      tmp2 = result;
    }
    return result;
  }
}

* 사실... 비재귀적 방법을 저렇게 적용하는 건 좀 야매스러운 느낌이 강하고 배열이나 리스트를 쓰는 게 맞다 또 DP와의 비교를 위해서는 배열을 쓰는 게 맞는데 걍 ㅋㅋ 좀 넘어가주셈 귀찮음

 

• 시간복잡도 분석

  • 재귀 함수 $\rightarrow O(2^{n/2})$

    • 재귀 함수를 호출하는 횟수가 T(n)의 함수를 따른다고 하면,

      • $T(0) = T(1) = 1$

      • $T(n-1)+T(n-2) > 2*T(n-2)$

        • $T(n) > 2*T(n-2)$

        • $T(n) > 2*(2*T(n-4))$

        • ...

        • $T(n) > 2^{n/2}*T(0)$

    • 수식적 계산을 해 보지 않고도, 재귀적 피보나치 알고리즘은 계속 두 개의 subproblem을 호출하면서 마치 바이너리 트리와 같은 형태로 실행된다는 것을 알 수 있다.(tight한 시간복잡도를 주는 것은 아니지만 그냥 대략 지수 시간이 걸린다는 것을 확인할 수 있겠다. 그리고 이 부분은 나중에 알고리즘에서 깊이 우선 탐색(DFS)를 다룰 때 더 자세히 할 거 같다.)

  • 비재귀 함수 $\rightarrow\theta(n)$

 

• 차이가 나는 이유

  • 트리 형태를 그려보면 알겠지만 중복된 연산을 너무 많이 한다

    • DP는 한번 연산 후 그것을 memoization함으로써 이러한 연산을 줄이는 기법이다.

 

3. 하노이 타워

• 설명할 필요도 없이 유명하다. 사실 코드 짜기 귀찮다. 걍 소스/데스/보조/개수 넣고 보조로 옮겼다가 데스로 옮겨

 

 

4. Search in an Array

• Unsorted array

  • 최악의 경우 모든 element를 확인해야 함 $\rightarrow$ 시간복잡도 $O(n)$

• Sorted array

  • linear search 

    • 최악의 경우 : $\theta(n)$

    • 평균 : $\theta(n)$

    • 최선의 경우 : $theta(1)$

    • 그냥... 경우 : $O(n)$

  • Binary search : $O(logn)$

• Binary search

  • 는 아래 링크를 참고하자

https://apple-apple-apple-apple-apple.tistory.com/21

Binary Search - Recursive / Non-recursive

• Search Kth smallest element

  • 도 아래 링크를 참고하자