[Algorithm] Recursive

Author

고경수

Published

September 20, 2024

재귀

코딩 테스트 합격자 되기 - 파이썬 편 책 정리 내용입니다.

3. 실전 문제

문제 1: 숫자의 각 자리수를 거꾸로 나열하기

문제 설명:

양의 정수 n이 주어졌을 때, n의 각 자리수를 재귀를 사용하여 거꾸로 나열한 값을 반환하는 함수를 작성하세요.

예시 입/출력:

  • 입력: n = 12345

  • 출력: 54321

설명:

정수 12345를 재귀적으로 처리하여 54321이 반환됩니다.

제한 사항:

  • n은 1 이상 1,000,000 이하의 자연수입니다.

풀이

def solution(input):
    if len(input) == 1:
        return input
    
    return input[-1] + solution(input[:-1])
solution('54321')
'12345'

문제 2: 이진수를 십진수로 변환하기

문제 설명:

이진수로 표현된 문자열이 주어졌을 때, 해당 이진수를 재귀를 사용하여 십진수로 변환하는 함수를 작성하세요.

예시 입/출력:

  • 입력: binary_str = "1101"

  • 출력: 13

설명:

이진수 1101은 십진수로 변환하면 13이 됩니다.

제한 사항:

  • 문자열의 길이는 1 이상 32 이하입니다.

  • 이진수는 0과 1로만 구성되어 있습니다.

def solution(input):
    n = len(input)
    if n == 1:
        return int(input)
    
    return int(input[0])*(2**(n-1)) + solution(input[1:])    
solution("1101")
13

문제 3: 문자열 압축하기

문제 설명:

문자열이 주어졌을 때, 재귀를 사용하여 동일한 문자가 연속될 경우 그 문자의 반복 횟수를 세어 압축한 문자열을 반환하는 함수를 작성하세요.

예시 입/출력:

  • 입력: s = "aaabccccdd"

  • 출력: "a3b1c4d2"

설명:

연속된 문자를 카운트하여 “a3b1c4d2”가 반환됩니다.

제한 사항:

  • 문자열의 길이는 1 이상 1,000 이하입니다.
count = 0
temp = ""
def solution(input):
    if len(input) == 1:
        count += 1
        return input + str(count)    
        
    if (count == 0) and (input[0] != input[1]):
        return input[0] + "1" + solution(input[1:])
        

    while (len(input)> 1) and (input[0] == input[1]):
        count += 1
        temp = input[0]
        input = input[1:]

    count = 0
    return temp + str(count) + solution(input)        
            
        
solution("aaabccccdd")
UnboundLocalError: local variable 'count' referenced before assignment

문제 4: 하노이의 탑 문제

문제 설명:

3개의 기둥과 N개의 원판이 주어졌을 때, 재귀를 사용하여 하노이의 탑 문제를 해결하는 알고리즘을 작성하세요, 모든 원판을 첫 번째에서 세 번째 기둥으로 옮기는 과정을 출력하세요.

예시 입/출력:

  • 입력: N=3

  • 출력:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

제한 사항:

  • 원판의 개수 N은 1 이상 20 이하입니다.

문제 5: 숫자 분해하기

문제 설명:

양의 정수 n이 주어졌을 때, n을 두 정수의 곱으로 분해하는 모든 방법을 찾는 재귀 함수를 작성하세요.

예시 입/출력:

  • 입력: n = 12

  • 출력: [(1, 12), (2, 6), (3, 4)]

설명:

12를 두 정수의 곱으로 나타내면 (1, 12), (2, 6), (3, 4)와 같이 분해됩니다.

제한 사항:

  • n은 1 이상 10,000 이하의 정수입니다.