[Algorithm] 재귀호출 백준 PS (1)

18511 큰 수 구하기

depth는 길이,

→ 종료 조건은 깊이, 정답에는 비교 후 큰 것 넣도록

집합에 있는 자연수는 1~9의 자연수, 이 자연수는 중복해서 사용할 수 있다.

N의 자릿수를 넘어가면 어차피 N보다 커지기 때문에 구할 필요가 없음, 따라서 함수의 반환(종료) 조건은 자릿수가 N과 같아질 때로 한다.

그리고 중복을 허용하기 때문에 모든 경우를 확인해야 한다. → 반복문에서 배열의 수 선택 후 N과 비교해 작다면 재귀 호출.

더 큰 경우는? 현재 수 그냥 넣어서 재귀 호출하고, 이 경우에는 10 제곱수가 곱해지고 1의 자리가 안 더해졌기 때문에 수에 0이 포함되어 있음.

따라서 비교 조건에서 0이 들어가 있는 경우는 제외하도록한다.

N, K = map(int, input().split())
arr = list(map(int, input().split()))

ans = 0

def fun(order, num):
    global ans
    
    if order == len(str(N)):
        if not '0' in str(num):
            ans = max(ans, num)
        return
    
    for i in range(K):
        now_num = arr[i] * (10 ** (len(str(N)) - order - 1)) + num
        
        if now_num <= N:
            fun(order + 1, now_num)
        
        else:
            fun(order + 1, num)

fun(0, 0)

print(ans)
    

10994 별 찍기

유추 했을 때 4 * n - 3 으로 별이 찍힘

row 기준 그 다음 row는 겉에만 찍히고, 그 다음에 다시 찍히게됨

→ 2,2 씩 더한다고 볼 수 있다.

N = int(input())
length = N * 4 - 3
stars = [[' ' for _ in range(length)] for _ in range(length)]

def fill_star(n, x, y):
    if n == 1:
        stars[x][y] = '*'
        return
    
    length = 4 * n - 3
    
    for i in range(length):
        stars[y][x + i] = '*'
        stars[y + i][x] = '*'
        stars[y + length - 1][x + i] = '*'
        stars[y + i][x + length - 1] = '*'
        
    fill_star(n - 1, x + 2, y + 2)

fill_star(N, 0, 0)

for s in stars:
    print(''.join(s))

1991 트리 순회

Pre → 출력, 왼쪽 자식, 오른쪽 자식
Mid → 왼쪽 자식, 출력, 오른쪽 자식
Post → 왼쪽 자식, 오른쪽 자식, 출력

N = int(input())
tree = {}

for i in range(N):
    root, left, right = input().split()
    tree[root] = [left, right]
# 0은 자신, 1은 왼쪽 자식, 2는 오른쪽 자식

def pre_order(root):
    if root == '.':
        return
    
    print(root, end='')
    pre_order(tree[root][0])
    pre_order(tree[root][1])
    
def mid_order(root):
    if root == '.':
        return
    
    mid_order(tree[root][0])
    print(root, end='')
    mid_order(tree[root][1])

def post_order(root):
    if root == '.':
        return
    
    post_order(tree[root][0])
    post_order(tree[root][1])
    print(root, end='')
    
pre_order('A')
print()
mid_order('A')
print()
post_order('A')