JH 개발 블로그

  *  
 * * 
*****

https://www.acmicpc.net/problem/2448

n = int(input())

def star(l):
    if l == 3:
        return ['  *  ',' * * ','*****']

    arr = star(l//2)
    stars = []
    for i in arr:
        stars.append(' '*(l//2)+i+' '*(l//2))

    for i in arr:
        stars.append(i + ' ' + i)

    return stars

print('\n'.join(star(n)))

n = 3일때

  *  
 * * 
*****

n = 6일때

     *     
    * *    
   *****   
  *     *  
 * *   * * 
***** *****

n = 12일때 

           *           
          * *          
         *****         
        *     *        
       * *   * *       
      ***** *****      
     *           *     
    * *         * *    
   *****       *****   
  *     *     *     *  
 * *   * *   * *   * * 
***** ***** ***** *****

n= 3일때 트리 모양이 n=6이 되면서 밑에 2개가 더 생기고, 원래 트리가 가운데로 옮겨졌습니다.

원래 트리가 가운데로 옮기도록 하려면 n//2 일때 트리모양에서 양옆으로 l//2만큼 공백을 추가하면 됩니다.

그리고 아래 트리 2개는 가운데에 공백을 하나만 추가하면 됩니다.

https://www.acmicpc.net/problem/2447

n = int(input())

def star(l):
    if l == 3:
        return ['***','* *','***']

    arr = star(l//3)
    stars = []

    for i in arr:
        stars.append(i*3)

    for i in arr:
        stars.append(i+' '*(l//3)+i)

    for i in arr:
        stars.append(i*3)

    return stars

print('\n'.join(star(n)))

n = 3일때

***
* *
***

n = 9일때

*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********

n = 27일때

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태입니다.

따라서 N의 패턴을 알려면 N//3 의 패턴을 알아야 합니다. 결국 재귀를 돌면서 N은 최소단위인 3이 되고, N=3일때의 패턴을 만들고 리턴해줍니다.

3의 패턴을 가지고 9의 패턴을 알게되고, 9의 패턴을 가지고 27의 패턴을 알게되고.. 반복하면서 결국 N의 패턴을 알게 됩니다. 패턴을 만들때 가운데부분은 비워주는걸 유의해야 합니다.

https://www.acmicpc.net/problem/1891

d, num = input().split()
d = int(d)
x,y = map(int,input().split())

def find_coordinate(num,idx,r,c,size):
    if size == 0:
        global num_r,num_c
        num_r,num_c = r,c
        return

    if num[idx] == '1':
        find_coordinate(num,idx+1,r,c+size,size//2)
    elif num[idx] == '2':
        find_coordinate(num,idx+1,r,c,size//2)
    elif num[idx] == '3':
        find_coordinate(num,idx+1,r+size,c,size//2)
    elif num[idx] == '4':
        find_coordinate(num,idx+1,r+size,c+size,size//2)

def make_answer(num_r,num_c,size,ans):
    if size == 0:
        print(ans)
        return

    if 0 <= num_r < size and size <= num_c < 2*size:
        make_answer(num_r,num_c-size,size//2,ans+'1')
    elif 0 <= num_r < size and 0 <= num_c < size:
        make_answer(num_r, num_c, size//2, ans+'2')
    elif size <= num_r < 2*size and 0 <= num_c < size:
        make_answer(num_r-size, num_c, size//2, ans+'3')
    elif size <= num_r < 2*size and size <= num_c < 2*size:
        make_answer(num_r-size,num_c-size,size//2,ans+'4')

num_r = num_c = 0
find_coordinate(num,0,num_r,num_c,(2**d)//2)
num_r -= y
num_c += x
if 0 <= num_r < 2**d and 0 <= num_c < 2**d:
    make_answer(num_r,num_c,(2**d)//2,'')
else:
    print(-1)

번호의 좌표를 찾아낸 후, 이동시킨다음 이동된 좌표를 이용해 답을 구해내면 된다.

예를들어 num(번호) = 341 일때, 좌표는 8*8 격자 안에 존재할 것이다.

좌표 [0,0], idx=0 부터 시작한다. num[idx]=3 이므로 3사분면에 존재한다.

따라서 좌표는 [0+size,0], idx +=1 이 된다. 재귀적으로 반복하여 좌표를 찾아간다.

size가 0이되면 종료한다.

구해낸 좌표를 이동시킨다. 만약 이동이 격자 안의 범위를 벗어났다면 -1을 출력한다.

이동시킨 좌표에서 시작한다. size를 이용해서 현재 몇사분면인지 구한다음 ans에 더해주고, 좌표값을 조정해준다.

재귀적으로 반복하여 답을 구해낸다.

https://www.acmicpc.net/problem/1201

n, m, k = map(int, input().split())

if n < m+k-1 or n > m*k:
    print(-1)
else:
    l = list(range(k,0,-1))
    n -= k
    m -= 1
    while m:
        l.extend(range(k+n//m,k,-1))
        k += n//m
        n -= n//m
        m -= 1
    print(*l)

m+k-1 <= n <= m*k

1.  m+k-1 <= n

예를들어 m=2, k=2라고 했을 때
이 조건을 만족하는 가장 짧은 길이의 수열은 [1,3,2] 으로, n=3입니다.
여기서 LIS와 LDS가 공통적으로 3을 공유하고 있습니다.
이렇듯 가장 짧은 수열은 공통의 수 하나를 LIS와 LDS가 무조건 공유합니다.
따라서 n은 m+k-1보다 같거나 커야합니다.

2. n <= m*k

예를들어 m=2, k=2 라고 했을 때
이 조건을 만족하는 가장 긴 수열은 [ [2,1], [4,3] ] 으로, n=4입니다.
만약 n=5라면, 절대 만들 수 없습니다.

n=13, m=5 , k=4일때로 예를 들어보겠습니다.
A = [ [4,3,2,1], [6,5], [8,7], [10,9] ,[13,12,11] ]는 조건을 만족합니다.
여기서 LIS의 길이는 행의 개수입니다..(=5)
여기서 LDS의 길이는 열의 최대 길이입니다.(=4)

A = []로 두고, 먼저 k=4이므로 4,3,2,1 을 A에 추가합니다.
그 후 n개의 수 중에서 k개를 사용했으므로, n에서 k를 뺀다(n=9). 9개의 수를 앞으로 사용할 수 있습니다.
총 행의개수 5에서 행을 이미 하나 만들었으므로 앞으로 만들 행의 개수는 4개입니다.(m=4)
이제 앞으로 n과 m을 0으로 만들면 됩니다.

n//m = 9//4 = 2 다음으로 만들 행의 원소의 개수를 의미합니다.
[k+2:k] 의 수를 A에 추가합니다. 6,5가 추가됩니다.
2개의 수를 사용했기 때문에 n=7이고, 1개의 행을 더 만들었기 때문에 m=3이 됩니다.
k는 +=2를 해줘서 6으로 갱신해줍니다.
7//3 = 2이므로 A에 [k+2:k]인 8,7이 추가됩니다. 그 후 n,m,k = 5,2,8이 됩니다.
5//2 = 2이므로 A에 10,9가 추가합니다. n,m,k = 3,1,10
3//1 = 3이므로 A에 13,12,11이 추가합니다. n,m,k = 0,0,13
그럼 조건을 만족하는 수열이 완성됩니다.

만약 n=9 , m=3 , k=3이라면
A = []
A에 3,2,1 추가 n,m,k = 6,2,3
A에 6,5,4 추가 n,m,k = 3,1,6
A에 9,8,7 추가 n,m,k = 0,0,9

만약 n이 m*k보다 크다면, 길이가 m+1인 LIS나 k+1인 LDS가 무조건 만들어지기 때문에, 답을 구할 수 없습니다.

https://www.acmicpc.net/problem/1074

N,r,c = map(int,input().split())
ans = 0

while N > 1:
    size = (2**N)//2
    if r < size and c >= size: #2사분면
       ans += size**2
       c -= size
    elif r >= size and c < size: #3사분면
        ans += 2*(size**2)
        r -= size
    elif r >= size and c >= size: #4사분면
        ans += 3*(size**2)
        r -= size
        c -= size
    N -= 1

if (r,c) == (0,0):
    print(ans)
elif (r,c) == (0,1):
    print(ans+1)
elif (r,c) == (1,0):
    print(ans+2)
else:
    print(ans+3)

한변의 길이가 2^n인 정사각형을 문제에서 4등분으로 나눈 뒤 재귀적으로 방문한다 했으므로

그대로 4등분으로 나누고, 몇사분면에 위치하는지 구해서 ans에 (size**2) 값을 몇번 더해줄지 정하고

r,c의 위치를 2사분면에 오도록 조정해주는 작업을 재귀적으로 반복하면 된다.

만약 N == 1이 되면 지금까지 구한 ans에 0,1,2,3 중 하나를 더해주면 된다.

https://www.acmicpc.net/problem/2263

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
inorder = list(map(int,input().split()))
postorder = list(map(int,input().split()))
position = [0]*(n+1)
for i in range(n):
    position[inorder[i]] = i

def preorder(istart,iend,pstart,pend):
    if istart > iend or pstart > pend:
        return

    root = postorder[pend]
    print(root,end=' ')

    left_cnt = position[root] - istart
    right_cnt = iend - position[root]

    preorder(istart,position[root]-1,pstart,pstart+left_cnt-1)
    preorder(position[root]+1,iend,pend-right_cnt,pend-1)


preorder(0,n-1,0,n-1)

inorder(중위순회), postorder(후위순회)를 통해 preorder(전위순회)를 구할 수 있습니다.

1. postorder의 맨 마지막 정점은  preorder의 처음 정점입니다.

postorder는 (왼쪽자식)(오른쪽자식)(정점) 인 반면 preorder는 (정점)(왼쪽자식)(오른쪽자식) 이기 때문입니다.

2. postorder의 맨 마지막 정점을 이용해 inorder에서 왼쪽자식의 개수, 오른쪽자식의 개수를 알 수 있습니다.

inorder는 (왼쪽자식)(정점)(오른쪽자식) 이기 때문에 inorder에서의 정점의 인덱스를 알고 있으면 왼쪽자식의 개수, 오른쪽자식의 개수를 알 수 있습니다.

3. 왼쪽자식, 오른쪽자식으로 나눠 왼쪽자식 먼저 재귀를 돌면서 전위순회를 찾아냅니다.

https://ca.ramel.be/114 

참고한 블로그입니다.