[JavaScript] 백준 분할정복(Divide&Conquer) 문제 : 2447번 별 찍기 - 10

분할정복(Divide&Conquer)이란?

분할정복(Divide & Conquer) 알고리즘은 문제를 해결하는 일반적인 방법 중 하나로, 주어진 문제를 더 작고 동일한 유형의 하위 문제로 나눈 다음, 이 하위 문제들을 해결하여 원래 문제의 해답을 구하는 방식입니다. 이 방법은 여러 가지 알고리즘 설계 기법 중에서도 특히 강력하고 널리 사용됩니다.

분할정복 알고리즘은 세 가지 주요 단계로 구성됩니다:

1. 분할(Divide): 문제를 더 작고 독립적인 하위 문제로 나눕니다. 이 단계에서는 주어진 문제를 나누는 기준과 방법을 결정합니다.
2. 정복(Conquer): 나눈 하위 문제들을 재귀적으로 해결합니다. 이 단계에서는 하위 문제를 해결하기 위해 다시 분할정복 알고리즘을 적용하거나, 더 이상 나눌 수 없을 만큼 작은 경우 직접 해결합니다.
3. 결합(Combine): 하위 문제의 해답들을 결합하여 원래 문제의 해답을 만듭니다. 이 단계에서는 하위 문제들의 해답을 이용해 전체 문제의 해답을 도출하는 방법을 정의합니다.

 

DP와의 공통점 및 차이점

공통점

• 큰 문제를 더 작은 하위 문제로 나누어 해결한다.

차이점

• 분할 정복 : 하위 문제가 서로 독립적
• DP : 하위 문제들이 중복 되는 경우

 

알고리즘을 공부 할 수록, 서로 비슷한 알고리즘이 많다는 것을 알게 된다. 비슷하지만 다른 알고리즘들을 확실히 이해하고 각 문제에 적합한 알고리즘을 찾는 능력을 키우는 것이 중요해진다.

 

문제 요구사항

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

 

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3^k이며, 이때 1 ≤ k < 8이다.

 

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

입출력 예

입력	출력
27

 

문제 이해하기

문제 설명이 자세하지 않아 문제를 이해하는데 시간이 걸렸다.

 

이해한 결과, 3의 제곱수인 N이 주어질 때, N은 다음과 같이 구성된다.

• N이 1일 때

*

• N이 3일 때 : 가운데에 크기가 3/3 = 1*1인 공백을 두고 3*3의 패턴이 완성된다.

***
* *
***

• N이 9일 때 : N이 3일 때의 패턴을 반복한다. 단, 가운데에 크기가 9/3 = 3*3인 공백을 두고 패턴을 그린다.

• N이 27일 때 : N이 9일 때의 패턴을 반복한다. 단, 가운데에 크기가 27/3 = 9*9인 공백을 두고 패턴을 그린다.

즉, N이 커질수록 N/3에서 사용한 패턴을 재사용하여 3X3의 패턴을 만드는데, 중앙은 빈 형태로 그리게 되는 것이다.

그럼 이 문제는 하위 패턴을 재사용한다는 점에서 DP가 아닐까 싶긴하지만, 그림이 아닌 문자열을 하나씩 찍어나가는 것이기에, DP보다는 분할정복이 더 적합하다고 볼 수 있다.

 

성공 코드

function solution(N) {
    // 2차원 배열 생성 후 각 자리의 문자 저장 -> 마지막에 join
    let pattern = Array.from({ length: N }, () => Array(N).fill(' '));

    function fillPattern(x, y, size) {
        if (size === 1) {
            pattern[x][y] = '*';
            return;
        }

        let newSize = size / 3;
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                if (i === 1 && j === 1) continue; // 가운데 비우기
                fillPattern(x + i * newSize, y + j * newSize, newSize);
            }
        }
    }

    fillPattern(0, 0, N);

    for (let i = 0; i < N; i++) {
        console.log(pattern[i].join(''));
    }
}

solution(N[0]);

1. 문자열을 담을 2차원 배열을 생성한다 -> N*N 배열
2. fillPattern 함수를 재귀적으로 호출하며 배열을 채운다
   
   • fillPattern(0, 0, 9)
     1. fillPattern(0, 0, 3) -> fillPattern(0, 0, 1) -> [0, 0] 자리에 *
     2. 반복하여 [ 0~2, 0~2 ] 자리에 3X3 패턴 생성
     3. fillPattern(0, 3, 3) -> fillPattern(0, 3, 1) -> [0, 3] 자리에 *
     4. 반복하여 [ 0~2, 3~5 ] 자리에 3X3 패턴 생성
     5. 위의 과정 반복하며 한 패턴씩 생성하여 9X9 패턴 완성
   • 위의 9X9 패턴 생성 반복
3. 마지막에 배열을 join함으로서 문자열 형태로 출력

 

지피티의 도움을 받아 문제를 풀었다. 처음에는 단순 패턴 반복이라 생각하였는데, 너무나도 인적 사고였고.. 한 줄씩 출력하며 패턴을 완성해야하는 프로세스를 구현하기가 어려웠다. 컴퓨터적 사고를 통해 알고리즘을 구현해내는 것을 더 연습해야 할 듯 하다.