[바미] 별 찍기 - 10

문제

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

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const N = parseInt(input, 10);

function generateStarPattern(size) {
    if (size === 1) {
        return ['*'];
    }

    const subPattern = generateStarPattern(size / 3);
    const pattern = [];

    for (let i = 0; i < size; i++) {
        pattern[i] = '';
        for (let j = 0; j < size; j++) {
            if (Math.floor(i / (size / 3)) % 3 === 1 && Math.floor(j / (size / 3)) % 3 === 1) {
                pattern[i] += ' ';
            } else {
                pattern[i] += subPattern[i % (size / 3)][j % (size / 3)];
            }
        }
    }

    return pattern;
}

const result = generateStarPattern(N);
console.log(result.join('\n'));

 

generateStarPattern(size) 함수는 재귀적으로 크기 size의 패턴을 생성해줍니다.

generateStarPattern(size) 함수의 동작 형태는 먼저 size === 1일 때 문자열 '*'를 반환해주고, 크기 size를 3등분하여, 가운데 부분이 공백인 패턴을 생성해줍니다. 그 후 subPattern은 크기 size / 3의 패턴을 저장하며, 이를 반복적으로 사용하여 전체 패턴을 생성해줍니다.

문제 해설

주어진 문제는 재귀적으로 패턴을 생성하여 별을 출력하는 문제입니다. 문제에서 제시한 조건을 바탕으로 재귀적인 접근을 통해 패턴을 생성해야 합니다.

 

𝑁 = 3 일 때의 기본 패턴은 아래와 같습니다.

***
* *
***

 

N이 3보다 클 경우, 크기 𝑁의 패턴은 가운데 부분이 공백으로 채워진 (𝑁 / 3) × (𝑁  / 3) 정사각형을 크기 𝑁 / 3의 패턴으로 둘러싼 형태로, 주어진 크기 𝑁에 대해 크기 𝑁 / 3인 패턴을 반복적으로 사용하여 생성하는 재귀 함수를 작성하여 문제를 풀었습니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

각 레벨에서 𝑁길이의 문자열을 3등분하여 처리합니다.

 

이 때 재귀 호출의 깊이는 \(\log _{3}\left( N\right)\)가 됩니다.

그리고 각 레벨에서 수행되는 작업의 총 합은 𝑁입니다.
따라서, 전체 시간 복잡도는 \(O\left( N\log _{3}\left( N\right) \right)\)이 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

재귀 호출의 깊이는 \(\log _{3}\left( N\right)\) 입니다.

각 호출 스택 프레임은 일정한 공간을 차지하므로, 총 공간 복잡도는 재귀 호출의 깊이에 비례합니다.

 

따라서 전체 공간 복잡도는 \(O\left( N\log _{3}\left( N\right) \right)\)이 됩니다.