백준 알고리즘 2447번 파이썬

김형준·2022년 4월 14일
0

9단계 재귀함수

❌❌❌ <1회차 최종 실패!>

-> 코드 리뷰 및 이해에 초점

3) 2447번 별찍기 (재귀함수, 프랙탈 구조)

처음에 핵심 구조 (프랙탈 구조)임을 이해하고 이에 대한 코드를 작성하려 했다.
2차원 배열에 대한 개념이 없어서 1차원 배열을 활용하여 재귀함수로 정답코드를 작성하려하다 보니 굉장히 애를 먹었던 문제이다.
구글링하여 정답 코드를 참고해보니 1차원 배열을 이용한 답안은 모두 반복문을 사용했다.
나는 공부하는 입장이기에 재귀함수로 완성 코드를 탐구하고 싶었고, 2차원 배열을 활용한 (아주 깔끔하고 논리적인..) 코드를 운좋게 찾을 수 있었다. 작성자님의 조언대로 디버깅을 해보며 결국 이해까지는 완료한 상태이다.
따라서 아래에는 내가 작성한 것이 아니며 고수님의 코드에 내가 이해한대로 주석만을 덧붙인 코드를 첨부한다.
출처:https://study-all-night.tistory.com/5
2차원 배열에 대한 개념 없이 이해하다보니 상당히 시간이 오래 소요되었지만 결국 내 나름대로 이해할 수 있었고, 앞으로 2차원 배열을 더욱 학습하고 꼭 다시 풀어보고 싶은 문제이다. 그때는 내가 작성한 코드를 밑에 덧붙이겠다.

# 별 찍는 재귀 함수
def draw_star(n):
    # 전역 변수인 Map을 불러온다.
    global Map

    # n이 3이 될 때 까지 recursion하여  n이 3일 때의 3x3 2차원 배열을 전체 배열의 [:3][:3]에 입력해준다.
    if n == 3:
        Map[0][:3] = Map[2][:3] = [1] * 3
        Map[1][:3] = [1, 0, 1]
        return

    a = n // 3
    draw_star(n // 3)
    # 3의 거듭제곱 단계별로 아래 반복문이 돌며 값이 채워진다
    # 범위가 3인 것은 모든 단계에서 크게보면 결국 이전 단계의 결과가 한칸으로 3x3 배열을 채우기 때문이다.
    for i in range(3):
        for j in range(3):
            # 모든 단계에서 가운데에 들어가는 칸은 0 그대로 냅둔다 (공백)
            if i == 1 and j == 1:
                continue
            # 3의 거듭제곱 범위에서,
            for k in range(a):
                # 좌항은 Map의 [3의 거듭제곱 x 0,1,2중 하나(행)][3의 거듭제곱 x 0,1,2 : 3의 거듭제곱 x 1,2,3까지(열)]
                # 즉 좌항은 새롭게 값이 들어갈 부분이고,
                # 우항은 기존에 값이 들어가 있던곳이자 좌항에 넣어줄 값이 된다 ( 프랙탈 구조이기에 반복되기 때문)
                Map[a * i + k][a * j:a * (j + 1)] = Map[k][:a]  # 핵심 아이디어


N = int(input())

# 메인 데이터 선언 (입력 받은 값 x 입력 받은 값의 배열을 만들어준다.)
Map = [[0 for i in range(N)] for i in range(N)]

draw_star(N)

# 0행 부터 순차적으로 배열에 담긴 값을 * 혹은 공백으로 출력해준다.
for i in Map:
    for j in i:
        if j:
            print('*', end='')
        else:
            print(' ', end='')
    print()
profile
BackEnd Developer

0개의 댓글