[Gold V] <2447> "별 찍기 - 10"
별찍기 문제집 링크: https://www.acmicpc.net/workbook/view/20
문제집: 별 찍기 (시리즈)
www.acmicpc.net
[Gold V] <2447> "별 찍기 - 10" 문제 링크: https://www.acmicpc.net/problem/2447
2447번: 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이
www.acmicpc.net
최근에 별찍기 문제집을 풀고 있었어요!
그런데 10번 문제가 시간이 오래 걸렸어요.. ㅠㅠ
그런데 풀고보니 Gold 문제였다?!(뿌듯)
아무튼 본론으로 와서..
오랜만에 만나는 재귀 형태네요..
재귀를 공부할 떄 하노이의 탑을 완벽히 이해하는데 이틀이 걸렸던 기억이 나요.. ㅎㄷㄷ
아무튼!
제가 짠 알고리즘은 이렇습니다!
#include <iostream>
#include <vector>
using namespace std;
void square(vector<vector<char>> &res, int num, int y, int x, char c)
{
if(num == 1)
{
res[y][x] = c;
}
else
{
// for loop를 할때마다 num/3을 더해주면서 입력값이 3의 배수인 걸 이용하여
// 무조건 9번 루프를 돌 수 있게 한다.(이 패턴의 근본은 9조각으로 나누는 것)
// 해당 값이 9칸의 패턴으로 나누는 기준 좌표가 된다.
// 결국 9 X 9 X 9 = 729(27 X 27) 이 되는 것이다.
// 여기서 i는 매개변수의 y, j는 매개변수의 x로 시작한다.
// 결국 해당 기준값부터 시작을 하므로 벡터의 주소 전부를 한번씩 방문한다.
// 만약 num이 1이면 해당 주소에 매개변수 c로 채우는데
// 여기서 count 변수를 사용하여 9번의 루프 중 5번째 의 경우는
// square() 함수의 매개변수 c에 공백으로 바꿔줌으로써 해당 주소에는 공백으로 채워진다.
int count = 0;
for ( int i = y; i < y + num; i += num/3 )
{
for ( int j = x; j < x + num; j += num/3 )
{
if ( count == 4 )
{
square(res, num/3, i, j, ' ');
}
else
{
square(res, num/3, i, j, c);
}
count++;
}
}
}
}
int main()
{
int num;
cin >> num;
vector<vector<char>> res(num, vector<char>(num));
square(res, num, 0, 0, '*');
//res 출력
for(int j = 0; j < num; j++)
{
for(char i : res[j])
{
cout << i;
}
cout << endl;
}
}
저는 동적 배열인 vector.h를 사용했어요!
num의 input 값이 27이라는 가정 하에 과정을 설명할께요!
square() 함수에 num을 num/3 으로 입력해주며 i, j는 다음과 같이 변한다.
num이 27(이)면 i, j 는 다음과 같다.
"0, 0" -> "0, 9" -> "0, 18"
"9, 0" -> "9, 9" -> "9, 18"
"18, 0" -> "18, 9" -> "18, 18"
총 9번 루프가 돌아가는데 이때마다 해당 i, j 값을 매개변수 y, x 값에 넣어주고 함수 자신을 호출한다.
그럼 num은 "num / 3 = 9" 으로 들어가면서 아래처럼 loop를 한다.
"0, 0" 일 때 9번
"0, 9" 일 때 9번
"0, 18" 일 때 9번
...
"18, 18" 일 때 9번
총 81번을 실행을 하는데, 여기서 또 81번의 실행마다 "num / 3 = 3" 으로 들어가면서 아래처럼 loop를 한다.
"0, 0" 일 때 9번
"0, 3" 일 때 9번
"0, 6" 일 때 9번
...
"6, 6" 일 때 9번
결국 총 729번을 실행하게 된다.
여기서는 729번의 실행마다 "num / 3 = 1" 으로 들어가지만 num이 1이므로
해당 좌표값으로 받은 매개변수 y, x로 해당 좌표에 매개변수 c를 넣는다.
고로 num이 27이면, 729번을 행하는데 이는 27 x 27 과 같다.
그리고 해당 기준 좌표를 통해 모든 좌표에 한번씩 방문하게 된다.
좀더 직관적인 과정을 적었어요!
<[27] 첫 번째>
27일 때 i, j = "0, 0"으로 다음 재귀의 i, j의 시작값으로 들어간다.
<[27] 첫번째의 [9] 첫 번째>
9일 때 i, j = "0, 0"으로 다음 재귀의 i, j의 시작값으로 들어간다.
<[27] 첫번째의 [9] 첫번째의 [3] 첫 번째>
3일 때 i, j = "0, 0"으로 다음 재귀의 i, j의 시작값으로 들어간다.
1일 때 전 재귀에서 받은 i, j 값 즉 y, x 값의 좌표에 매개변수로 받은 c로 채우고 전 재귀로 복귀.
<[27] 첫번째의 [9] 첫번째의 [3] 두 번째>
3일 때 i, j = "0, 1"로 다음 재귀의 i, j의 시작값으로 들어간다.
1일 때 전 재귀에서 받은 i, j 값 즉 y, x 값의 좌표에 매개변수로 받은 c로 채우고 전 재귀로 복귀.
<[27] 첫번째의 [9] 첫번째의 [3] 세 번째>
3일 때 i, j = "0, 2"로 다음 재귀의 i, j의 시작값으로 들어간다.
1일 때 전 재귀에서 받은 i, j 값 즉 y, x 값의 좌표에 매개변수로 받은 c로 채우고 전 재귀로 복귀.
...
<[27] 첫번째의 [9] 첫번째의 [3] 아홉 번째>
3일 때 i, j = "2, 2"로 다음 재귀의 i, j의 시작값으로 들어간다.
1일 때 전 재귀에서 받은 i, j 값 즉 y, x 값의 좌표에 매개변수로 받은 c로 채우고 전 재귀로 복귀.
<[27] 첫번째의 [9] 두 번째>
9일 때 i, j = "0, 3"으로 다음 재귀의 i, j의 시작값으로 들어간다.
<[27] 첫번째의 [9] 두 번째의 [3] 첫 번째>
3일 때 i, j = "0, 3"으로 다음 재귀의 i, j의 시작값으로 들어간다.
1일 때 전 재귀에서 받은 i, j 값 즉 y, x 값의 좌표에 매개변수로 받은 c로 채우고 전 재귀로 복귀.
<[27] 첫번째의 [9] 두 번째의 [3] 두 번째>
3일 때 i, j = "0, 4"으로 다음 재귀의 i, j의 시작값으로 들어간다.
1일 때 전 재귀에서 받은 i, j 값 즉 y, x 값의 좌표에 매개변수로 받은 c로 채우고 전 재귀로 복귀.
<[27] 첫번째의 [9] 두 번째의 [3] 세 번째>
3일 때 i, j = "0, 5"으로 다음 재귀의 i, j의 시작값으로 들어간다.
1일 때 전 재귀에서 받은 i, j 값 즉 y, x 값의 좌표에 매개변수로 받은 c로 채우고 전 재귀로 복귀.
<[27] 첫번째의 [9] 두 번째의 [3] 네 번째>
3일 때 i, j = "1, 3"으로 다음 재귀의 i, j의 시작값으로 들어간다.
1일 때 전 재귀에서 받은 i, j 값 즉 y, x 값의 좌표에 매개변수로 받은 c로 채우고 전 재귀로 복귀.
...
<[27] 첫번째의 [9] 두 번째의 [3] 아홉 번째>
3일 때 i, j = "2, 5"로 다음 재귀의 i, j의 시작값으로 들어간다.
1일 때 전 재귀에서 받은 i, j 값 즉 y, x 값의 좌표에 매개변수로 받은 c로 채우고 전 재귀로 복귀.
...
(이하 생략)
마무리!
위 처럼 3의 루프를 9번 반복했다면 전 재귀인 9의 루프로 돌아가서 9의 다음 루프를 실행한다.
또 9의 루프를 9번 반복했다면 전 27의 루프로 돌아가서 27의 다음 루프를 실행한다.
여기서 알아야 할 핵심 내용은 i와 j가 매개변수 y와 x로 받은 값으로 시작한다는 것이다.
이렇게 한다면 27을 9개의 조각으로 나누고 나눈 기준좌표를 매개변수로 주면서
해당 좌표에서부터 패턴을 그리기 시작하는 것이다.
<출력 결과>
(원래 단위는 별이지만 가독성을 위해서 string에 "▩"를 사용했어요!)
어우... 전 이 알고리즘을 만드는데 거진 8시간을 투자한 것 같아요..
오랜만에 만난 재귀라 머리가 잘 안굴러갔지만 끈기를 통해 결과를 얻을 수 있었네요 ㅎㅎ
메모리: 6772 KB, 시간: 228 ms
제 코드는 매개변수가 많아서 메모리를 많이썼어요.. 실행 속도는 나름 괜찮네요!
첫 이 알고리즘을 짰을 때 너무 감격스럽고 기분이 좋았는데..
(아니 이게 뭐지..)
다른 사람들의 코드를 보았는데 자존감이 팍 떨어졌어요..
내 알고리즘보다 간단하고 메모리도 적게쓰고 심지어 속도까지 빠르네요..
뭐 그래도 재귀함수인데 성능을 바라는건 모순이지 않을까..? 싶기도 하구..
그래도 눈물을 머금고 다른사람들은 어떻게 짰는지 참고하고
다음엔 더 최적화된 코드를 짜기위해 노력을 해보려고 해요!
그래도 결과가 나온 것 만으로도 나름 만족하네요..
아무튼 첫 코딩문제 포스트는 여기서 마칠게요!
내 인생 목표를 향해!
다들 공부 화이팅 하세요!
읽어주셔서 감사합니다!