TIL 코딩공장

백준 파이썬 공부 2025.01.01
1914번 하노이 탑 (골드 5)

1. 문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 
각 원판은 반경이 큰 순서대로 쌓여있다. 
이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 
단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

2. 입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

3. 출력
첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 
두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 
이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. 
N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

4. 문제 풀이
하노이 탑의 풀이법은 재귀이다.
일단은 가장 큰 원판을 제외한 모든 원판을 한 덩어리로 생각하자.
그리고 원판이 위치한 장대을 start, 도착지 장대를 end, 보조 장대를 sub라 할 때, 
모든 원판을 마지막 원판에 옮기는 방법은
1) 덩어리 원판을 start에서 sub 장대로 옮기고
2) 가장 큰 원판을 start에서 end 장대로 옮기고,
3) 덩어리 원판을 sub에서 end 장대로 옮기는 것이다.

이를 재귀 함수로 만들어 돌리면 된다.

>>코드

def hanoi(n):
    if n == 1:
        return 1
    return 2 * hanoi(n - 1) + 1 # 덩어리 원판 2번 옮기기 + 큰 원판 한번 옮기기

def print_hanoi(start, end, sub, n):
    if n == 0:
        return
    print_hanoi(start, sub, end, n - 1)  # start >> sub로 덩어리 원판 옮기기
    print(start, end)  # start >> end로 가장 큰 원판 이동 출력
    print_hanoi(sub, end, start, n - 1)  # sub >> end로 덩어리 원판 옮기기

n = int(input())
print(hanoi(n))
if n <= 20:
    print_hanoi(1, 3, 2, n)

5. 문제 링크
https://www.acmicpc.net/problem/1914

20240424 백준 파이썬 공부
25501번 재귀의 귀재

1. 문제
정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 
재귀 함수와 관련된 문제를 출제하기로 했다.

팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 
팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 
팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다.

어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 
아래 코드의 isPalindrome 함수는 
주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다.

>>>Python3, Pypy3 코드

def recursion(s, l, r):
    if l >= r: return 1
    elif s[l] != s[r]: return 0
    else: return recursion(s, l+1, r-1)

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

print('ABBA:', isPalindrome('ABBA'))
print('ABC:', isPalindrome('ABC'))

정휘는 위에 작성된 isPalindrome 함수를 이용하여 어떤 문자열이 팰린드롬인지 여부를 판단하려고 한다.

구체적으로는, 문자열 
$S$를 isPalindrome 함수의 인자로 전달하여 팰린드롬 여부를 반환값으로 알아낼 것이다. 더불어 판별하는 과정에서 recursion 함수를 몇 번 호출하는지 셀 것이다.

정휘를 따라 여러분도 함수의 반환값과 recursion 함수의 호출 횟수를 구해보자.

2. 입력
첫째 줄에 테스트케이스의 개수 T가 주어진다. 
(1 <= T <= 1,000)
둘째 줄부터 T개의 줄에 알파벳 대문자로 구성된 문자열 S가 주어진다. 
(1 <= |S| <= 1,000)

4. 출력
각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 
한 줄에 공백으로 구분하여 출력한다.

>>>코드

import sys

def recursion(s, l, r):
    if l >= r: return 1
    elif s[l] != s[r]: return 0
    else: return recursion(s, l+1, r-1)
    
def recount(count, s, l, r):
    if l < r and s[l] == s[r]:
        count += 1
        return recount(count, s, l+1, r-1)
    else: return count

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

for _ in range(int(input())):
    word = sys.stdin.readline().strip()
    count = 1
    print(isPalindrome(word), recount(count, word, 0, len(word)-1),sep = ' ')

>> 문제 해설
그냥 횟수를 세는 함수(recount)를 따로 만들었다    

>>>문제링크
https://www.acmicpc.net/problem/25501