프로그래밍 끄적끄적

문제를 읽어보면 알겠지만 3x2k의 수만큼 별을 찍어내려간다고 합니다. 3, 6, 12... 이런식으로 내려가게 됩니다. 처음에는 기본적인 별찍기 문제와 동일하게 생각해서 해당 좌측에 공백문자를 출력한 후 별을 찍는 방식의 for문을 생각했었는데 도저히 규칙을 생각해낼 수가 없었습니다. 그래서 생각해낸 방법이 바로 공백의 문자를 가지고 있는 문자열을 생성하고 그 위에 입력받은 N의 값만큼 별모양을 찍어내면 되는 것 입니다.

그러려면 일단 아래와 같은 별 한 세트를 찍는 함수를 만들었습니다. 좌측에 보이는 별을 한세트로 봤습니다. 왜냐하면 가장 작은 수가 3줄을 찍어내는 것이기 때문입니다.

이제 두번째로 직면한 문제는 정확한 위치에 별을 찍는것이 문제인데, 이것은 시작점의 좌표만 정해주면 규칙적으로 찍어내면 됩니다. 이를 구현하기 위해서는 재귀호출함수를 활용해야하는데, 재귀 함수를 모르시는 분이 있을 수도 있어서 간략하게 설명하고 넘어가겠습니다.

* 재귀 호출 함수(Recursive call)

함수 안에서 함수 자기 자신을 호출하는 방식을 재귀 호출(Recursive call)이라고 합니다. 재귀 호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용하게 쓰입니다. 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많습니다. 재귀 함수의 경우 하나의 함수가 끝나기 전에 본인 자신을 호출하기 때문에 스택(Stack)에 계속 함수를 호출하여 공간을 차지하게 됩니다. 그렇기 때문에 반드시 재귀 함수를 종료하는 시점을 만들어주는 구문이 필요합니다. 그렇지 않으면 제한된 메모리 용량을 초과해 스택 오버플로우(Stack overflow)현상이 발생하게 됩니다.

이 재귀 호출 함수를 활용하여 문제를 풀어보도록 하겠습니다. 가장 먼저 N이 늘어나는 규칙을 보면 2의 배수 씩 늘어나는 것을 볼 수 있습니다. 여기서 첫번째 3을 입력했을때 가장 위에 위치하는 별은 3번째에 찍히게 됩니다. 두번째 N인 6이 들어왔을 경우, 가장 최상단에 찍히는 별은 6번째 찍히게 됩니다. 그 다음줄에 찍히는 두개의 삼각형 별은 3번째와 8번째에 삼각형의 가장 위의 별이 찍히게 됩니다. 즉, 가장 위의 삼각형을 그리는 함수, 아래의 두개의 삼각형을 그리는 함수를 재귀 호출 함수를 활용하여 3개를 작성하면 됩니다. 여기서 종료 구문은 삼각형의 모양을 그리고 나서 함수를 종료하게 만들면 됩니다. 가장 작은 단위는 N이 3일때이므로 입력받은 N을 2씩 나눠가며 재귀 호출을 하면 됩니다. 삼각형이 추가되는 모형을 보면 N이 6일때는 3의 아래에 삼각형을 두개씩 추가하는 모습이고, 12일때는 6에 6을 아래에 두개 더 추가하는 모습입니다. 플로우 차트로 표현해보면 아래와 같은 모습이지 않을까 싶습니다. 재귀 호출 함수기때문에 직관적으로 표현하긴 어렵지만 대강 표현하게 된다면 저렇게 될 것입니다.

위의 플로우 차트만으로는 설명이 조금 부족하지만 이해를 돕기 위해서 첨부했습니다. 재귀 함수는 N의 값과 x좌표와 y좌표가 계속 업데이트 되면서 새로운 자기 자신 함수를 호출합니다.

재귀 호출 함수를 활용하여 풀이대로 진행을 하게 되면 문제가 원하는 결과 값을 얻을 수 있습니다. 마지막으로 코드와 실행 결과를 보고 포스팅을 마치도록 하겠습니다.

#include <iostream>
#include <memory.h>
char space[3072][6144];		// 별을 찍을 공간 생성 k값이 최대 10까지인 것을 고려하여 배열 크기 생성)

void star(int N, int x, int y) {
	if (N == 3) {
		space[y][x] = '*';
		space[y + 1][x - 1] = '*';
		space[y + 1][x + 1] = '*';
		space[y + 2][x - 2] = '*';
		space[y + 2][x - 1] = '*';
		space[y + 2][x] = '*';
		space[y + 2][x + 1] = '*';
		space[y + 2][x + 2] = '*';
		return;
	}		// 별 한세트를 찍는 구문
	
	star(N / 2, x, y);		// 벌의 윗부분을 찍는 재귀 호출
	star(N / 2,x - (N / 2), y + (N / 2));	// 별의 좌하단 삼각형을 찍는 재귀 호출
	star(N / 2, x + (N / 2), y + (N / 2));	// 별의 우하단 삼각형을 찍는 재귀 호출
}
int main() {
	int N;
	int i, j;

	scanf("%d", &N);

	memset(space, ' ', sizeof(space));		// for문보다 memset으로 배열을 초기화 해주면 시간을 단축 할 수 있다고 한다.

	star(N, N - 1, 0);		// 입력받은 N을 넣어 함수 실행

	for (i = 0; i < N; i++) {
		for (j = 0; j < N * 2; j++) {
			printf("%c", space[i][j]);
		}
		printf("\n");
	}			// 별이 그려진 배열 출력
}