자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 이진수 출력

 

 

https://hyejin.tistory.com/1252

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 재귀 함수

-> 이전 문제 풀이 

 

2. 이진수 출력 

설명

10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요.

단 재귀함수를 이용 해서 출력해야 합니다.

 

입력

첫 번째 줄에 10진수 N(1<=N<=1,000)이 주어집니다

 

출력

첫 번째 줄에 이진수를 출력하세요.

 

예시 입력 1 

11

 

예시 출력 1

1011

 

 

문제 풀이 1

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

👾 : 이 문제는 주어진 숫자 n에 대해서 2진수를 출력하는 문제이다. 

2진수는 주어진 숫자에 나누기 2한 값의 나머지를 출력해주면 된다. 

예시인 11을 보면 DFS(11) -> DFS(5) -> DFS(2) -> DFS(1) 이렇게 재귀함수를 호출해주면서 2로 나눈 나머지 값을 출력해주면 된다. 

 

 

밑의 그림은 강의에서 설명 중 그린 스택 캡쳐 화면이다..

 

맨 처음에는 DSF(11)을 호출하기 때문에 스택에 가장 먼저 쌓이고, 함수가 끝나기전에 자기 자신을 다시 호출하기 때문에 6라인까지만 수행하고 DFS(5)을 호출한다. 

 

스택에 DFS(5)가 쌓이고, 수행하는데 마찬가지로 DFS(2)를 호출하기 때문에 6라인까지만 하고, DFS(2)를 호출한다. 

 

 

동일하게 DFS(2) -> DFS(1) 까지 호출한 다음, DFS(0)에서는 return 하기 때문에 함수가 종료되었고, 

다시 DFS(1)로 돌아와서 6라인 다음부터 함수를 실행한다. 따라서 n % 2 한 값이 출력되고 종료된다. -> 1 

DFS(2) 로 넘어와서 n % 2 한 값인 0을 출력하고 함수 종료한다. -> 0 

DFS(5) 에서는 n % 2 한 값인 1 을 출력하고 함수 종료하고 -> 1 

DFS(11)에서는 n % 2 한 값인 1을 출력하고 함수 종료한다. -> 1 

 

따라서 결과인 1011이 출력된다!