[Python] 2447번

프랙탈처럼 어떤 세분화된 소 문제로 쪼갤수 있다면 분할정복 알고리즘을 사용해야한다.

분할정복법 (Devide & Conquer)

큰문제를 작은문제로 분할해 재귀적으로 해결
시간복잡도 : O(n) 이다.

import sys
N = int(sys.stdin.readline())
star=["***","* *","***"]

def stars(N):
    new_star=[]
    for i in range(3 * len(N)):
        if i // len(N) == 1:
            new_star.append(N[i % len(N)] + " " * len(N) + N[i % len(N)])
        else:
            new_star.append(N[i % len(N)] * 3)
    return(list(new_star))


K=0
while N!=1:
    N = N//3
    K= K+1
for i in range(K):
    star = stars(star)
for i in star:
    print(i)

코드를 입력하세요

출력함수의 경우 시간복잡도가 크다 !

global : 함수 밖에 선언한 친구들을 수정할 때는 전역변수를 써줘야 한다.