[바미] 칸토어 집합

 

 

문제

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

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

function generateCantorSet(N) {
    if (N === 0) return '-';
    
    const prevSet = generateCantorSet(N - 1);
    const space = ' '.repeat(prevSet.length);
    
    return prevSet + space + prevSet;
}

const results = input.map(line => {
    const N = parseInt(line, 10);
    return generateCantorSet(N);
});

console.log(results.join('\n'));

문제 해설

칸토어 집합을 재귀적으로 생성하는 문제를 해결하기 위해, 주어진 길이의 문자열을 3등분하고 가운데 부분을 공백으로 대체하는 작업을 반복적으로 수행합니다. 재귀 함수를 사용하여 간단하게 해결할 수 있습니다.

 

시간 복잡도

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

 

각 단계에서 문자열의 길이는 3배가 되며, 재귀 호출을 통해 길이가 \(3^{N}\) 인 문자열을 만듭니다.
이 때 재귀 깊이는 𝑂(𝑁)이며, 각 호출에서 문자열을 합치는 작업이 수행됩니다.

 

따라서 전체 시간 복잡도는 \( O\left( 3^{N} \right) \)입니다.

공간 복잡도

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

 

각 단계에서 생성되는 문자열의 크기는 \(3^{N}\) 이므로, 전체 공간 복잡도는 \( O\left( 3^{N} \right) \)입니다.