[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (17)(2021.2.9 ~ 10)

본 내용은 해당 강의 토대로 작성

재귀함수와 스택

재귀함수

• 자기 자신을 호출하는 함수
• 반복문처럼 사용할 수 있다.
• 스택 자료구조 사용

예시 1

def DFS(x):
    if x > 0:
        print(x, end = " " );
        DFS(x - 1); # 자기자신 호출

if __name__=="__main__":
    n = int(input());
    DFS(n) # 깊이 우선 탐색

• 정수를 넣으면 내림차순으로 출력한다.
• 10 입력시: 10 9 8 7 … 1 출력

예시 2

def DFS(x):
    if x > 0:
        DFS(x - 1); # 자기자신 호출
        print(x, end = " " );

if __name__=="__main__":
    n = int(input());
    DFS(n) # 깊이 우선 탐색

• 정수를 넣으면 오름차순으로 출력
• 10 입력시: 1 2 3 4 5 … 10

예시 1, 예시 2 분석

• 재귀함수는 스택 자료 구조를 사용
  • 위의 이유로, 재귀함수 정의시 print 아래에 함수가 호출되면 내림차순으로, 위에서 호출되면 오름차순으로 출력되는 것이다.

오름차순의 경우

• print명령이 실행되기 전에, 재귀함수가 호출되어 스택 프레임이 쌓인다.
  • 스택 프레임 : 복귀할 주소, 지역변수, 매개변수가 포함되어 있다.
• 조건문 x > 0을 만족하지 않는 시점에서 함수 호출이 멈추고 print명령이 실행된다.
• 마지막 스택프레임부터 처음의 스택프레임까지 print 명령 실행
• 3을 입력했을 때

쌓이는 순서	1	2	3
	1 스택프레임	2 스택프레임	3스택프레임(재귀함수 호출 종료)
출력 순서	3	2	1

재귀함수를 이용한 이진수 출력

나의 전략

• 10진수에서 2진수로 변환하는 방법을 알고리즘으로 구현
• 재귀함수 이용
  • stack 자료구조를 이용하여 나중 입력이 제일 먼저 나오도록 한다.

문제 풀이

def bi(x):
    if x != 1:
        print(x)
        a = x // 2;
        b = x % a;
        if a == a:
            print(a, end="");
        bi(a); # 재귀함수
        print(b, end = "");

if __name__ == "__main__":
    n = int(input());
    bi(n);

• case 2, 3을 풀지 못함

문제 해설

• if else 같이 사용하기
  • if는 함수 종료
  • else에는 함수 실행 코드를 작성

문제 답안

def DFS(x):
    if x == 0: # 값이 0일 때
        return; # 종료
    else:
        DFS(x // 2);
        print(x % 2, end = '');

if __name__ == "__main__":
    n = int(input());
    DFS(n);

풀이와 답안 비교

재귀 함수가 익숙하지 않은 상태에서 너무 복잡하게 생각했기때문에 case2, 3에서 오답처리가 나왔다.