[파이썬/알고리즘] 재귀함수를 이용한 이진수 출력

파이썬을 이용한 이진수 출력 문제

문제) 10진수가 입력되면 2진수로 변환해 출력하는 프로그램을 작성하라.

입력

첫 줄에 10진수 n이 주어진다.

풀이

n=int(input())

def DFS(x):
   if x==0:
      return
   else:
      DFS(x//2)
      print(x%2, end='')

DFS(n)

DFS(깊이 우선 탐색)

우선, 십진수를 이진수로 바꾸는 방법을 알아야한다. (간단히 설명하자면, 십진수를 2로 나누어 나온 나머지를 역순으로 나열하면 된다.)

 

예를 들어 n=11 일 때, 작동하는 과정은 아래와 같다.

DFS(11) 호출, 함수의 호출 정보를 스택에 기록, print(11%2, end='')는 시행되지 못하고 DFS(11//2) 호출로 넘어감

DFS(5) 호출, 함수의 호출 정보를 스택에 기록, print(5%2, end='')는 시행되지 못하고 DFS(5//2) 호출로 넘어감

DFS(2) 호출, 함수의 호출 정보를 스택에 기록, print(2%2, end='')는 시행되지 못하고 DFS(2//2) 호출로 넘어감

DFS(1) 호출, 함수의 호출 정보를 스택에 기록, print(1%2, end='')는 시행되지 못하고 DFS(1//2) 호출로 넘어감

DFS(0) 호출 -> 종료(return), 함수가 종료되어 사라진다.

 

그후 스택에서 가장 최근에 기록된 것부터 복귀하여 시행한다. (앞에서 시행되지 못했던 print가 작동한다.)

아래줄부터 print 실행된다.

print(1%2, end='')

print(2%2, end='')

print(5%2, end='')

print(11%2, end='')

 

>> 1011