211126 백준 코딩연습 파이썬 재귀 함수 10829 이진수 변환

https://solved.ac/

 

파이썬

이전 문제에 이어서 dfs, bfs를 위해 이해가 필요한 재귀 함수 문제를 풀어 보았다.

재귀 함수(Recursive Function)는 자기 자신을 다시 호출하는 함수이다.

재귀 함수를 문제 풀이에서 사용할 때는 종료 조건을 꼭 명시해야 한다.

그렇지 않으면 재귀 함수가 무한으로 호출되며 재귀의 최대 깊이를 초과했다는 오류 메시지를 보게 될 것이다.

컴퓨터 내부에서 재귀 함수의 수행은 이전에 설명했던 스택 자료구조를 이용한다.

함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

컴퓨터의 구조 측면에서 보자면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재되므로 재귀 함수는 스택 자료구조와 같다고 할 수 있다.

따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다.

대표적인 예가 바로 DFS이다.

재귀 함수를 이용하는 대표적인 예로는 팩토리얼(Factorial) 문제가 있다.

브2 이진수 변환

맞은 코드

stackNum = []
def printBinary(num):
    if num == 0:
        return
    stackNum.append(num % 2)
    printBinary(num // 2)
    
import sys
N = int(sys.stdin.readline())
printBinary(N)
for i in range(len(stackNum)):
    print(stackNum.pop(), end = "")

이진수 변환을 나누기 연산한 값이 0이 될 때까지 재귀로 구현하였고 나머지 연산한 값을 스택을 이용하여 저장한 후 pop()하여 거꾸로 출력해주었다.

남의 코드 1

print(bin(int(input()))[2:])

사실 파이썬에는 bin()이라는 10진수를 2진수로 변환해주는 함수가 있다.

그러나 bin() 함수를 사용하면 0b가 변환된 2진수 앞에 붙어서 인덱스 2부터 출력한 것이다.

남의 코드 2

def a(n):
    
    if n==1:
        return 1
    b=n%2
    n=n//2
    
    return 10*a(n)+b
n=int(input())
print(a(n))

내 풀이보다 이렇게 10을 곱해서 자릿수를 올려주는 방법이 더 좋은 것 같다.