[파이썬 알고리즘 문제풀이 입문] 완전탐색 (백트랙킹, 상태트리와 CUT EDGE) / DFS(깊이우선탐색) 기초 - 재귀함수를 이용한 이진수 출력

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

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

 

 

 

풀이

• 내 풀이

import sys
input = sys.stdin.readline

def DFS(num):
    if num > 0:
        DFS(num//2)
        print(num%2, end='')

N = int(input())
DFS(N)

• 답안 : Python

import sys
input = sys.stdin.readline

def DFS(N):
    if N == 0:
        return
    else:
        DFS(N//2)
        print(N%2, end='') #스택을 사용하기 때문에 출력 아래 -> 위

N = int(input())
DFS(N)

- 재귀함수를 써야한다는 조건에 따라 문제를 풀어보았다. 답안과 비교했을 때 if문의 조건 부분만 살짝 다르고, 로직은 크게 다를게 없었다.

- 재귀함수는 기본적으로 stack을 이용하기 때문에, 나머지들을 거꾸로 출력해야하는 현 상황에서는 재귀함수 호출 부분 뒤에서 print를 해주어야 한다.

 

cf.) 재귀함수 이미지