Algorithm - DFS(Recursive Function)

• 2023-12-18 에 풀이한 문제
• 1번 문제 풀이 시간 : 0925 ~ 0930 ( 풀이 성공 )
• 2번 문제 풀이 시간 : 0945 ~ 0948 ( 풀이 성공 )

• 나의 풀이 깃허브 : 풀이 1 클릭! 풀이 2 클릭!

알고리즘 문제(Java) : 재귀함수 ( DFS )

1. 문제

자연수 N이 입력되면 재귀함수를 이용하여 1~N까지 출력하는 프로그램을 작성하세요

2. 입력

• 첫 줄은 정수 N(3<=N<=10)이 주어집니다.

3. 출력

• 첫 줄에 출력합니다.

4. 문제 풀이

• 재귀 함수에 대하여 완벽히 이해 해야한다.
• 재귀함수는 “스택”을 사용하여 계산한다. “스택프레임”이라고 한다. 그 개념을 알아야 한다.
  • DFS(n) 이 생성되면, DFS(n)에 대한 매개변수 지역변수 복귀주소가 들어있는게 스택에 생성된다.
  • DFS(3) 을 하면, DFS(3) DFS(2) DFS(1) DFS(0) 이 스택에 순차적으로 쌓이게 된다.
  • DFS(3) 을 하면, DFS(3-1) 을 호출하게 되는데, 그럼 그 아래에 있는 System.out.print(n + “ “); 은 잠시 대기 상태가 된다.
  • 그래서 DFS(0) 이 될때까지 System.out.print(n + “ “); 은 대기하다가, DFS(0) 부터 차례로 (스택이니까) 완료 시키며 pop(); 한다.
  • 그래서 아래 코드처럼 작성하면, System.out.print(n + “ “); 이 역순으로 출력되는 것이다. ( 스택 상단부터 내려오듯 실행되니까 )
  • 그래서 DFS(n-1) 보다 앞에 System.out.print(n + “ “); 이 있으면, n n-1 n-2 n-3 ~ n-.. 이렇게 출력이 되고,
  • DFS(n-1) 보다 뒤에 System.out.print(n + “ “); 가 있으면, n-.. ~ n-2 n-1 n 이렇게 출력되는 것이다.
  • 스택프레임은 스택이니 재귀호출 한 아래의 코드는 peek (상단) 부터 pop 되면서 호출된다고 생각하면 된다.

public class Recursive_Function {

    public static void DFS(int n) {
        if ( n == 0 ) return;
        else {
            DFS(n-1);
            System.out.print(n + " ");
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        DFS(scan.nextInt());
    }

}

• 비슷한 문제로 10진수를 2진수로 바꿀 때 재귀함수를 활용할 수 있다.
• 아래는 문제2, 재귀함수를 활용한 10진수를 2진수로 바꾸는 문제 풀이이다.

public class Binary_Recursive_Functions {

    public static void DFS(int n) {
        if ( n == 0 ) return;
        else {
            DFS(n / 2);
            System.out.print(n % 2);
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        DFS(scan.nextInt());
    }

}

• 이건 10진수를 2진수로 바꾸는 방법만 알고있으면, 그리고 스택프레임의 개념을 알고있으면 쉽게 풀 수 있는 문제이다.