Algorithm - 재귀함수를 활용한 이진수 출력

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[재귀함수를 활용한 이진수 출력]

 

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

(단, 재귀함수를 이용하여 출력해야 함)

 

 

*입력 설명

첫 번째 줄에 10진수 N(1 ≤ N ≤ 1,000)이 주어진다.

 

*출력 설명

첫 번째 줄에 이진수를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_43.txt', 'rt')

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

if __name__ == "__main__":
    n = int(input())
    DFS(n)
    
# 출력 : 1 0 1 1

 

input_43.txt(입력)

11

 

 

중요내용

1. 여기서 DFS() 함수가 재귀함수이다.
2. 재귀함수는 스택 자료구조를 사용한다.
3. 위의 예시코드에서 재귀함수가 스택 자료구조를 활용하여 작동하는 원리를 이해하는 것이 중요하다. (이전 글 참고!!)
4. 재귀함수의 return은 해당 함수를 종료해주는 기능을 한다.
5. x % 2는 x를 2로 나눈 나머지를 반환해주는 코드이다.
6. x // 2는 x를 2로 나눈 몫을 반환해주는 코드이다.