백준 [단계별로 풀어보기]: (21단계) "재귀", python

백준 [단계별로 풀어보기]: (21단계) 재귀", python

 

1. 문제번호 및 정답비율

21단계 재귀 : 문제번호 및 정답 비율

 

2. 문제별 필요 지식 및 풀이 포인트

# 1. 27433 팩토리얼2

 

# 2. 10870 피보나치 수 5

 

# 3. 25501 재귀의 귀재

'''다시 풀어보기 / 펠린드롬 알고리즘 외우기'''
'''global변수선언 방식과 활용법 알기, def recursion(s,l,r,cnt):방식도 가능'''

 

# 4. 24060 알고리즘 수업 - 병합 정렬1

 

# 5. 4779 칸토어 집합

'''
cantor(0) = '-'
cantor(1) = cantor(0)+' '*3**0+cantor(0) = '- -'
cantor(2) = cantor(1)+' '*3**1+cantor(1) = '- -   - -'
cantor(3) = cantor(2)+' '*3**2+cantor(2) = '- -   - -         - -   - -'
'''

 

# 6. 2447 별 찍기 -10

'''흠..왜 항상 마무리를 못짓지..?'''
'''핵심풀이
1. x=1일때만 '*'를 반환해주면서,
2. a에 (x/3)꼴을 재귀를 통해 호출(=['*'])하면,
3. for문으로 상/중/하 나누어서 배열에 담기
4. 재귀함수에 넣은 입력값을 '\n'.join 조인으로 출력
참고) https://velog.io/@miiingirok/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-2447.-%EB%B3%84-%EC%B0%8D%EA%B8%B0Python
'''

 

# 7. 11729 하노이 탑 이동 순서

'''
내생각)
1. (x-1)번째 원판이 3에 있을때, 1~(x-2)번째 원판이 2에 순차적으로 쌓여있으면 된다.
2. 원판수n 짝수일때, 최상단원판1이 2부터
           홀수일때, 최상단원판1이 3부터 쌓기 시작한다.
3. 옮긴수k (예상) 1 3 7 15 .. 2^n-1 인가?
코딩)
그런데 문제는 코딩으로 못 옮기겠음.. 흠..
해설)
1. 풀이1.이 이 문제의 핵심으로 잘 짚었으나, 짝/홀 나누는 것까지 생각 안해도 된다.
2. 재귀함수 선언 시, 원판수, 시작막대, 끝막대까지 3개의 변수를 넣어줘야 한다.
3. 
참고) https://study-all-night.tistory.com/6 '''

3. 문제별 풀이 코드

# 1. 27433 팩토리얼2
def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)
print(factorial(int(input()))) #factorial(int(input()))만 하면 틀림

# 2. 10870 피보나치 수 5
#"0" 1 1 2 3 5 8 13 21
def fibo(x):
    if x<2 :return x #if x<=2 : return 2는 0번째 값을 가져올 수 없음
    return fibo(x-1) + fibo(x-2)
print(fibo(int(input())))

# 3. 25501 재귀의 귀재
'''다시 풀어보기 / 펠린드롬 알고리즘 외우기'''
'''global변수선언 방식과 활용법 알기, def recursion(s,l,r,cnt):방식도 가능'''
#문제에 제시된 코드를 python문법으로 따라 입력하면,
def recursion(s, l, r): #str, left:startN, right:endN
    global cnt #recursion함수 호출 횟수 : global변수로 선언
    cnt += 1
    if l>=r: return 1
    elif s[l] != s[r]: return 0
    else: return recursion(s, l+1, r-1) #startN ->"중앙값"<- endN 을 향한다.

def isPalindrome(s):
    return recursion(s, 0, len(s)-1)

#print('ABBA', isPalindrome('ABBA')) #1
#print('ABC', isPalindrome('ABC')) #0

for _ in range(int(input())):
    cnt = 0
    print(isPalindrome(input()), cnt)

# 4. 24060 알고리즘 수업 - 병합 정렬1
'''다시 풀어보기 / 알고리즘 암기'''
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = (len(arr)+1)//2 #중앙값 설정
    left = merge_sort(arr[:mid]) #앞쪽 정렬
    right = merge_sort(arr[mid:]) #뒷쪽 정렬

    sorted_arr = []
    i=j=0
    while i < len(left) and j < len(right): #TypeError: '<' not supported between instances of 'int' and 'list'
        if left[i] <= right[j]:
            sorted_arr.append(left[i])
            ans.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            ans.append(right[j])
            j += 1
    while i <len(left): #앞쪽 배열이 남는 경우
        sorted_arr.append(left[i])
        ans.append(left[i])
        i += 1
    while j < len(right): #뒷쪽 배열이 남는 경우
        sorted_arr.append(right[j])
        ans.append(right[j])
        j += 1
    return sorted_arr

ans = []
n,k = map(int, input().split())
a = list(map(int, input().split()))
merge_sort(a)

print(ans[k-1] if k <= len(ans) else -1)

# 5. 4779 칸토어 집합
def cantor(n):
    if n == 0:
        return '-'
    return cantor(n-1)+' '*3**(n-1)+cantor(n-1)

while True:
    try:
        print(cantor(int(input())))
    except:
        break

# 6. 2447 별 찍기 -10
def star(x): #x= 3,9,27..
    if x == 1: return ['*']
    arr = []
    a = star(int(x//3))
    #print(x) #3, 9, ..
    #print(a) #['*'], ['***','* *','***'], ..
    #print(arr) #[], [], ..
    for i in a:
        arr.append(i*3)
    for i in a:
        arr.append(i+' '*(x//3)+i)
    for i in a:
        arr.append(i*3)
    return arr
    
n = int(input())
print('\n'.join(star(n))) # *** * * ***, ...

# 7. 11729 하노이 탑 이동 순서
def hanoi(x,s,e):
    if x==1:
        print(s,e)
        return
    else:
        hanoi(x-1,s,6-s-e) #막대번호1 2 3을 합치면 6이며, s,e번호를 알고있기 때문
        print(s,e)
        hanoi(x-1,6-s-e,e)
        
n = int(input())
print(2**n -1)
hanoi(n,1,3)