[DFS,BFS 기초] 재귀함수를 이용한 이진수 출력

문제

10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다.

 

입력설명

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

 

출력설명

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

 

입력예제 1

11

 

출력예제 1

1011

 

---

 

 

DFS(11)을 넘겨주므로 11을 2진수로 변환해서 출력해줘야한다

여기서 n이 0이 되면 재귀함수가 멈춰야 한다 그니까 들어오는 n이 11 이였다가 5 였다가 2 였다가 1이였다가 0이 되어야 한다

그리고 그 나머지를 출력하니까 1011 거꾸로 출력해줘야한다

 

 

if (n==0) return; 종료 조건 달아준다

else에서는 DFS(n/2) 이렇게 2로 나눈 몫으로 바꿔줘야한다

출력은 2로 나눈 나머지를 출력해야하므로 n%2로 출력해준다

 

이제 출력코드를 dfs 호출 앞에다가 넣으면 1101 으로 출력되고

dfs 호출 뒤에다가 넣으면 1011 이렇게 거꾸로 출력된다

이유는 스택 때문이다

 

그러면 D(11)이 먼저 스택에 들어가고 DFS(n/2)까지만 하고 대기상태로 넘어가고, 그 다음 D(5) 들어가고 대기상태,

D(2) 들어가고 대기상태, D(1) 들어가고 대기상태, D(0) 들어가고 얘는 종료조건 0이니까 자기 할 일 다하고 pop 됨

그럼 이제 스택이니까 맨 상단 D(1) 차례로 복귀됨

차례대로 하면 1011 출력됨