https://www.acmicpc.net/problem/2447
문제
재귀적인 패턴으로 별을 찍어 보자. 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=3k이며, 이때 1 ≤ k < 8이다.
출력
첫째 줄부터 N번째 줄까지 별을 출력한다.
예제 입력 1
27
예제 출력 1
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
********* *********
* ** ** * * ** ** *
********* *********
*** *** *** ***
* * * * * * * *
*** *** *** ***
********* *********
* ** ** * * ** ** *
********* *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************처음 이 문제를 풀때 생각했던 방식은, 이 전 문제인 (단계별로 풀어보기로 하나씩 전부 풀고있는 중이다.) '칸토어 집합 문제를 응용해서 3의 배수를 찾고, 그 배수만큼 반복하는 행동을 1차원이 아닌 2차원으로 접근한다.'로 생각하고 문제를 해결하려고 했다. 하지만 처음 작성한 코드는 다음과 같이 출력이 반복되었다.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<char>> star;
void removeCenter(int size)
{
if (size < 1) return;
int third = size / 3;
for (int i = third; i < 2 * third; i++)
{
for (int j = third; j < 2 * third; j++)
{
star[i][j] = ' ';
}
}
removeCenter(third);
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
star.resize(n, vector<char>(n, '*'));
removeCenter(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << star[i][j];
cout << '\n';
}
return 0;
}***************************
* *************************
***************************
*** *********************
*** *********************
*** *********************
***************************
***************************
***************************
********* *********
********* *********
********* *********
********* *********
********* *********
********* *********
********* *********
********* *********
********* *********
***************************
***************************
***************************
***************************
***************************
***************************
***************************
***************************
***************************여기까지 했을때 자꾸만 '이렇게 푸는게 맞나?'라는 생각이 머리를 어지럽혔고, 계속해서 고민해봤지만 결국 풀 수 없었다. (뒤에 이를 바탕으로 해결하는 방법이 나온다.)
그렇게 GPT와 Gemini를 통해 '힌트'를 달라고 했지만 썩 직관적이거나 이해할만한 힌트를 제공해주지 않았다. 전부 다 수학적 규칙이 있으니 이를 공부해라, 거의 다 왔다 등으로 넘어갔다. 하지만 이 과정에서 나온 공통적인 힌트는 '좌표'였다. 함수의 파라미터에 좌표가 나와야 어디에 점을 찍을지 확실하게 알게 되는 것이고, 이를 이용하여 '빈 공간'을 찍어야 한다는 것이다. 하지만 아쉽게도 여기에서 과부화가 걸려 어떻게 해결해야 할지 모르게 되었고, 결국 검색을 통해 가장 많이 나온 해답을 확인하였다.
방법 1
#include <iostream>
using namespace std;
void makeStar(int y, int x, int num)
{
if ((y / num) % 3 == 1 && (x / num) % 3 == 1)
cout << ' ';
else
{
if (num / 3 == 0)
cout << '*';
else
makeStar(y, x, num / 3);
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
makeStar(i, j, n);
cout << '\n';
}
}코드를 읽었을때는 직관적으로 한번에 이해하지 못했다. 오히려 손코딩으로 몇번씩 해보며 그제야 코드를 깨달았다. 원리는 다음과 같다.
우선 함수 부분은 좌표와 크기를 나타낸다. 출력에서 다음과 같이 27을 입력한 상태를 자세히 살펴보면 규칙을 찾을 수 있다.
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
********* *********
* ** ** * * ** ** *
********* *********
*** *** *** ***
* * * * * * * *
*** *** *** ***
********* *********
* ** ** * * ** ** *
********* *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************크기가 3일 경우
- (1,1)
크기가 9일 경우
- (1,1), (1, 4), (1,7)
- (4, 1), (4, 4), (4,7)
- (7, 1), (7, 4), (7,7)
- (3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)
이렇게 빈 공간이 형성되게 된다.
즉, 이를 식으로 표현해본다면 (i, j)라고 했을 때, i % 3과 j % 3의 결과 값이 공통적으로 1이 나와야한다. 다만, 이렇게만 할 경우에 앞서 크기가 9일 경우의 가장 마지막 부분인, '가운데 부분이 크게 빈 공간이 되는 경우'를 올바르게 처리하지 못한다. 즉, 이 경우만 상정하여 코드를 작성하면 27을 입력했을 때 다음과 같은 출력을 볼 수 있다.
***************************
* ** ** ** ** ** ** ** ** *
***************************
***************************
* ** ** ** ** ** ** ** ** *
***************************
***************************
* ** ** ** ** ** ** ** ** *
***************************
***************************
* ** ** ** ** ** ** ** ** *
***************************
***************************
* ** ** ** ** ** ** ** ** *
***************************
***************************
* ** ** ** ** ** ** ** ** *
***************************
***************************
* ** ** ** ** ** ** ** ** *
***************************
***************************
* ** ** ** ** ** ** ** ** *
***************************
***************************
* ** ** ** ** ** ** ** ** *
***************************
가운데 부분이 크게 사라지는 부분도 규칙을 찾을 수 있다. 바로, 해당 num으로 숫자를 나눈 뒤, 그 값을 3으로 나눈 나머지 값이 1인 경우를 찾는 것이다.
호출을 반복하다가, 예를들어 크기가 9인 경우 (3,3)의 좌표를 만났다고 가정하자. 그러면 다음과 같이 볼 수 있다.
(3,3,9)
첫 조건,
if ((y / num) % 3 == 1 && (x / num) % 3 == 1)
(3/9) % 3 == 0 이므로 false가 된다.
그러면 다음 조건을 확인해야한다.
if (num / 3 == 0)
cout << '*';
else
makeStar(y, x, num / 3);
이때, 9 / 3 == 3이 되므로, 재귀 호출로 makeStar를 (3, 3, 3)으로 호출한다.
그렇다면 다시 첫 조건으로 돌아와서,
(3/3) % 3 ==1이 되므로 true, 공백 문자를 출력하게 된다.즉, 문제를 해결 가능한 가장 작은 단위까지 작게 만든 뒤, 값을 출력하는 분할 정복 문제인 것이다. 해결 가능한 가장 작은 사이즈를 3으로 두고, 재귀적으로 문제를 해결한다. 다만 나는 이러한 방법이 '직관적'으로 이해하기 좋은 방법이라고 생각하지 않았다. 그도그럴것이, 지난 단계인 카토어 집합 문제에서 풀었던 문제와 연관성이 있다고 생각을 했고, 이 문제를 해결한 방법이 일반적인 (물론 나처럼 코딩을 뛰어나게 잘하지 못하는 사람들 대부분) 상황에서 쉽게 나올 수 없는 해결책이라 생각한다. 그렇기에 다시금 칸토어 집합 문제를 풀 때 시도했던 방법으로 다시금 문제를 해결해보았다.
방법 2
#include <iostream>
#include <vector>
using namespace std;
void removeCenter(int y, int x, int size, vector<vector<char>> &star)
{
if (size < 3) return;
int third = size / 3;
for (int i = y + third; i < y + 2 * third; i++)
{
for (int j = x + third; j < x + 2 * third; j++)
{
star[i][j] = ' ';
}
}
for (int dy = 0; dy < 3; dy++)
{
for (int dx = 0; dx < 3; dx++)
{
if (dy == 1 && dx == 1) continue;
removeCenter(y + dy * third, x + dx * third, third, star);
}
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
vector<vector<char>> star;
int n;
cin >> n;
star.resize(n, vector<char>(n, '*'));
removeCenter(0, 0, n, star);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << star[i][j];
cout << '\n';
}
return 0;
}핵심은 다음고 같다.
- 처음 시도했던 방법을 확장하여, 좌표 계산을 추가한다.
- 별도의 배열을 두어 여기에 미리 * 문자를 채워두고 공백 문자를 이후에 계산을 통해 채워나가는 방식으로 설정한다.
예를 한번 들어보자. 앞선 예시처럼 크기는 9로 두고, 좌표는 (0, 0), (1,1) 그리고 (3,3)을 생각해보자. 물론 이 코드는 main 함수에서 반복문을 사용하여 모든 좌표를 검사하는 앞선 로직과는 다르게 함수를 한 번 실행하면 내부에서 알아서 공백을 모두 생성한다.
(0, 0, 9): 최초 호출
(0, 0, 9): 최초 호출
우선 첫번째 조건문인 if (size < 3)은 false 이므로 넘어간다.
처음으로 third는 3이 된다.
이는 칸토어 문제와 비슷하게 '가운데 부분'을 표시하기 위한 일종의 index로 사용한다.
i = 0 + 3; i < 0 + 2 *3; 즉, i = 3 부터 6보다 작을때까지 반복한다(j도 동일).
이중 반복문을 지나며 다음 부분을 (0, 0)으로 만든다.
(3, 3), (3, 4) (3, 5)
(4, 3), (4, 4) (4, 5)
(5, 3), (5, 4) (5, 5)
이렇게 처음 과정에서 9 * 9 배열의 가장 가운데 부분이 공백이 된다.
다음 dy, dx를 사용하는 이중 반복문은 처음에
removeCenter(0, 0, 3, star)를 호출한다.
(0, 0, 3): 두 번째 호출
우선 첫번째 조건문인 if (3 < 3)은 false 이므로 넘어간다.
third는 1이 된다.
i = 0 + 1; i < 0 + 2 *1; 즉, i = 1 부터 2보다 작을때까지 반복한다(j도 동일).
여기에서 3*3 크기의 중간값에 공백이 들어간다. 그리고 이 부분에서 size == 3인 경우의 재귀 호출은 끝나게 된다.
다시 돌아와서 dx, dy 반복문을 돌면 구역을 9개로 나누어 이 과정을 반복한다. 그림으로 보면 다음과 같이 설명할 수 있다.
즉, 가장 큰 부분에 해당하는 공백을 처음에 만들고, '구역의 크기가 3보다 크다면 9등분하여 각 영역별로 공백을 추가하는 로직을 반복' 하는 것이 핵심이다.
이 문제도 일단 정답이다. 그리고 여기에서 더 나아가, 메모리와 시간에서 차이가 왜 나는지까지 검토해보자.
우선, 개인적인 생각으로는 코드의 길이나 방법적인 측면에서는 첫 번째 방식이 더 유용한 것 같다. 하지만, 직관적인 것은 두 번째 방법이라고 생각한다.
1. 두 문제의 기저 조건(Base Case)
방법1: num / 3 == 0
방법2: size < 3 return
2. 두 문제의 재귀 단계(Recursive Step)
방법1
문제를 쪼개는 방법: num / 3
재귀 호출 횟수: makeStar 함수 내에서의 재귀 호출은 makeStar(y, x, num / 3) 1번. main에서 모든 픽셀에 대해 함수를 각각 독립적으로 호출한다.
방법2
문제를 쪼개는 방법: y + dy * third, x + dx * third, third, star. 문제를 9개 영역으로 쪼개고 size를 third로 줄여서 전달.
재귀 호출 횟수: 8. (size 9가 호출되면 size 3을 8번 호출, size 27이 호출되면 size 9를 8번 호출한다.)
좀 더 이해하기 쉽게 재귀 트리를 그려보자.
방법1
makeStar(y, x, 27)
│
├─ 조건 검사: (y/27)%3 == 1 && (x/27)%3 == 1 ?
│ ├─ 참 → ' ' 출력, 종료
│ └─ 거짓 → num/3 != 0 → makeStar(y, x, 9)
│
└── makeStar(y, x, 9)
│
├─ 조건 검사: (y/9)%3 == 1 && (x/9)%3 == 1 ?
│ ├─ 참 → ' ' 출력, 종료
│ └─ 거짓 → num/3 != 0 → makeStar(y, x, 3)
│
└── makeStar(y, x, 3)
│
├─ 조건 검사: (y/3)%3 == 1 && (x/3)%3 == 1 ?
│ ├─ 참 → ' ' 출력, 종료
│ └─ 거짓 → num/3 != 0 → makeStar(y, x, 1)
│
└── makeStar(y, x, 1)
│
├─ 조건 검사: (y/1)%3 == 1 && (x/1)%3 == 1 ?
│ ├─ 참 → ' ' 출력, 종료
│ └─ 거짓 → num/3 == 0 → '*' 출력, 종료if (size < 3) return; // 종료 조건
→ size >= 3 인 경우:
1. 중앙 (1/3 블록)에 공백 채움
2. 주변 8개의 블록에 대해 재귀 호출
removeCenter(y + dy*third, x + dx*third, third, star)
n=27일때
removeCenter(0, 0, 27)
│
├─ removeCenter(0, 0, 9)
├─ removeCenter(0, 9, 9)
├─ removeCenter(0, 18, 9)
├─ removeCenter(9, 0, 9)
│ (중앙 [9,9] 제외)
├─ removeCenter(9, 18, 9)
├─ removeCenter(18, 0, 9)
├─ removeCenter(18, 9, 9)
└─ removeCenter(18, 18, 9)
각 removeCenter(..., 9)에서
removeCenter(0, 0, 9)
│
├─ removeCenter(0, 0, 3)
├─ removeCenter(0, 3, 3)
├─ removeCenter(0, 6, 3)
├─ removeCenter(3, 0, 3)
│ (중앙 [3,3] 제외)
├─ removeCenter(3, 6, 3)
├─ removeCenter(6, 0, 3)
├─ removeCenter(6, 3, 3)
└─ removeCenter(6, 6, 3)
마지막으로 size == 3일때
if (size < 3) return; // 즉, size == 3에서 하위 호출 시 size/3 == 1 → 종료
즉, 트리의 일반적인 구조를 살펴보면 다음과 같다.
Depth 0: size = n → 1개 호출
Depth 1: size = n / 3 → 8개 호출
Depth 2: size = n / 9 → 8² = 64개 호출
Depth 3: size = n / 27 → 8³ = 512개 호출
...
Depth k: size = n / 3ᵏ → 8ᵏ개 호출
removeCenter(0,0,n)
/ | \ ... (8개)
/ | \
removeCenter(..., n/3)
/ | \ ... (8개)
/ | \
removeCenter(..., n/9)
.
.
.
removeCenter(..., 3)
└─ 종료 (size < 3)
이렇게 나온 재귀 트리를 바탕으로, 재귀 깊이를 계산해보자.
우선 첫번째 방법이다.
호출 시마다 size는 size / 3으로 작아지고, 종료 조건은 size < 3일 때이다. 따라서 각 호출에 대한 수열은 다음과 같이 줄어들게 된다. 따라서, 몇 번을 3으로 나누면 1보다 작아지는가를 계산하면 된다.
size₀ = n
size₁ = n/3
size₂ = n/9
size₃ = n/27
...그렇다면 종료 시점은 sizeₖ < 3일 때,
재귀 호출 단계 수는 Θ(log₃(n))이 된다.
두 번째 방법의 경우에도 third를 계속해서 3으로 나누어 가다가 사이즈가 3보다 작아지는 경우 호출을 끝내므로 동일하게 Θ(log₃(n))으로 볼 수 있다. 그럼 이제 호출 수를 보자.
호출 수란 전체적으로 이 함수가 몇 번 실행되는가를 말한다.
첫 번째, 픽셀별 검사 방식의 경우 외부에서 모든 픽셀에 대해 makeStar를 한 번씩 호출한다. 그리고 한 호출 내부에서는 num이 매번 num/3으로 호출되고, num < 3이 될떄까지 내려간다. 다만, 이때 (y/num)%3==1 && (x/num)%3==1이면 그 시점에서 바로 종료된다.
두 번째, 블록 재귀 방식의 경우 한 번 호출하면 그 호출은 중앙 블록을 공백으로 채우고 중앙을 제외한 8개의 블록의 각각에 대한 재귀 호출을 한다. 그리고 앞선 num과 마찬가지로 size는 매 호출마다 size / 3만큼 줄어들고 size < 3 이면 더 이상 재귀 호출하지 않는다.
이 두 방법을 AI를 통해 전체 호출수를 비교해보면 다음과 같다고 한다.
| 항목 | makeStar | removeCenter |
| 전체 호출 수(대표적 비교) | 최악: (n^2(\log_3 n + 1)) | 정확: |
즉, 첫 번째 방법은 픽셀마다 재귀를 시작하므로, 전체 호출 수는 n^2에 로그까지 곱해져 n이 커지면 기하급수적으로 매우 큰 값이 될 수 있다.
그리고 두 번째 방법은 전체를 블록 단위로 한 번에 처리하므로 픽셀별 호출을 하지 않아서 전체 호출 수는 형태로 따졌을때 더 작아진다. (이는 n이 크면 차이가 더 확연해진다.)
조금 더 쉽게 이야기해보자면, 첫 번째 방법은 별 하나 그릴 때마다 재귀를 새로탄다. 즉, 별 찍을 좌표가 1만 개 있으면 makeStar가 1만 번 새로 시작되고, 천만, 백만이면 그만큼 새로 시작된다. 그리고 한 번 시작된 makeStar는 안쪽에서 num을 계속해서 3으로 나누며 재귀 호출을 반복하니깐 별 하나 찍으려면 별 쇼를 다해야한다.
다만, removeCenter는 한 번 호출할 때 여러 별을 한꺼번에 처리한다. 그리고 여기서 재귀가 블록 단위로만 이루어진다. 모든걸 하나씩 검사하는 것 보다, 블록 단위로 타고 들어갈때 더 효율적인 것이다.
다음은 최종적으로 수정한 버전이다.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<char>> star;
void removeCenter(int y, int x, int size)
{
if (size < 3) return;
int third = size / 3;
for (int i = y + third; i < y + 2 * third; i++)
{
for (int j = x + third; j < x + 2 * third; j++)
{
star[i][j] = ' ';
}
}
for (int dy = 0; dy < 3; dy++)
{
for (int dx = 0; dx < 3; dx++)
{
if (dy == 1 && dx == 1) continue;
removeCenter(y + dy * third, x + dx * third, third);
}
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
star.resize(n, vector<char>(n, '*'));
removeCenter(0, 0, n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << star[i][j];
cout << '\n';
}
return 0;
}
이 문제를 해결하며 대학교 재학시절, 영상처리 관련 수업에서 코딩했던 것이 떠올랐다. 그때했던, 주로 행렬 계산 위주로 문제를 처리했던 과정에서 픽셀 단위로 생각하고 문제를 해결하는 과정이 떠올라, 두 번째 방법이 머릿속에 비교적 쉽게 들어왔다. 그리고 알고리즘이라는 것이, 문제를 해결하는 여러 방법이라는 사실을 다시금 깨닫게 되는 시간이었다.
