기록을

문제 링크는 다음과 같다.

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

N과 M (1)과 약간의 차이가 있다.

수열 자체가 증가수열이면 된다.

이를 위해서는 기존에 재귀를 돌리던 루프의 시작 인덱스를 바로 직전 자리의 숫자 + 1로 해주면 된다.

직전 자리의 숫자는 어짜피 사용 중이기 때문에 그다음 숫자로 해주면 되는 것이다.

주의할 것은, 가장 처음 즉 이전 자리수가 존재하지 않는 경우인데, 그 경우에는 N의 시작 값인 1로 값을 정해주면 된다.

#include<iostream>
using namespace std;
int N, M;
void func(int* arr, bool* used, int k) {
	//base condition
	if (k == M) {
		for (int i = 1; i <= k; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	int init;
	if (k == 0) init = 1;
	else
		init = arr[k] + 1;

	for (int i = init; i <= N; i++) {
		if (!used[i]) {
			arr[k + 1] = i;
			used[i] = true;
			func(arr, used, k + 1);
			used[i] = false;
		}
	}
}
int main(void) {
	
	cin >> N >> M;
	
	int arr[10]; //길이 8이 최댄데 1 - indexed
	bool used[10]; // 1~9

	for (int i = 1; i <= 9; i++) {
		arr[i] = 0;
		used[i] = false;
	}
	
	func(arr, used, 0);// 0번째 자리까지 다 정해졌다. 이번에 1번째 자리 정할 차례다
	return 0;
}

문제 링크는 다음과 같다.

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

문제 설명

1부터 N까지 자연수를 사용해서 길이 M의 수열을 만들면 된다.

숫자는 중복해서 사용할 수 없다. 그리고 수열의 출력은 오름차순으로 이루어져야한다.

중복이 없다는 조건을 만족시키기 위해서 특정 숫자가 사용되었는지 관리하기 위해서 isused 배열을 사용한다.

그리고 수열이 되는 숫자는 arr 배열에 저장된다.

재귀함수로 구현을 할 것이고, base condition은 수열의 길이 k = M이 되는 경우이다.

이때 수열이 완성되었으므로 출력을 해준다.

재귀함수를 빠져나온 이후에는 그 숫자가 사용중인 것이 아니게 되기 때문에 isused를 다시 false로 만들어주는 것이 중요하다.

arr값은 어짜피 이어서 덮어씌워질것이기때문에 고려하지 않아도 된다.

이 문제는 next_permutation을 활용해서도 구현이 가능할 것이다.

#include<iostream>
using namespace std;
int N, M;
void func(int* arr, bool* isused, int k) {
	if (k == M) {
		for (int i = 1; i <= M; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!isused[i]) {
			arr[k + 1] = i;
			isused[i] = true;
			func(arr, isused, k + 1);
			isused[i] = false;
		}
	}
}

int main(void) {
	int arr[10];
	bool isused[10];
	for (int i = 1; i <= 9; i++) {
		arr[i] = 0;
		isused[i] = false;
	}

	int k = 0;

	cin >> N >> M;
	
	func(arr, isused, k);

	return 0;
}

문제 링크는 다음과 같다.

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

별 찍기 10번 문제와 굉장히 유사한 문제이다.

10번을 확실하게 이해했다면 11번은 무난하게 풀 수 있을 것이다.

n = 6인 경우는, n = 3인 경우의 삼각형 세 개가 반복되고,

n = 12인 경우는, n = 6인 경우의 삼각형 세개가 반복돼서 찍힌다. 

즉 n인 경우는 3개의 n-1인 경우로 이루어진다는 것을 알 수 있다.

따라서 알고리즘을 구현할 때도, 세 단계로 나눠서 재귀함수를 구현해주면 되겠다.

문제를 파악하면서 알 수 있듯이, base condition은 n = 3인 경우라는 것을 알 수 있다.

여러 가지 방법이 있겠지만, 생각의 편의성을 위해서 1 - indexed로 풀이를 진행했다.

최대 크기의 char 배열을 미리 잡아두었다.

base condition을 확인할 때 크기 정보를 사용하기 때문에(3인 경우 탈출) 크기를 인자로 갖고 있어야 한다.

또한 어느 좌표에 별을 찍을 것인지 확인이 필요하기 때문에 row와 col을 추가적으로 인자로 받는다.

그리고 공백인 부분에 대해서는 따로 신경을 쓰지 않고, 별을 모두 찍은 이후에 일괄적으로 공백에 대한 처리를 해주었다.

고등학교 수학에서 흔히 프렉탈이라고 불렀던 문제 유형과 생각의 흐름이 비슷한 것 같다는 느낌을 받았다.

#include<iostream>
using namespace std;
char arr[3073][6145];
void func(int n, int r, int c) {
	//base condition
	if (n == 3) {
		arr[r][c] = '*';
		arr[r + 1][c - 1] = '*';
		arr[r + 1][c + 1] = '*';
		for (int i = c-2; i <= c+2; i++)
			arr[r + 2][i] = '*';
		return;
	}
	
	func(n / 2, r, c);
	func(n / 2, r + n / 2, c - n / 2);
	func(n / 2, r + n / 2, c + n / 2);
	
}
int main(void) {
	
	int N;
	cin >> N;

	//1-indexed;

	func(N,1, N); //n, row, col
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 2 * N - 1; j++) {
			if (arr[i][j] != '*')
				arr[i][j] = ' ';
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 2 * N - 1; j++) {
			cout << arr[i][j];
		}
		cout << '\n';
	}
	return 0;

}

문제 링크이다.

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

현재까지의 별 찍기 시리즈 중에서 가장 쓸만한 문제라고 생각한다. 10번까지 문제들 중에서 말이다.

n = 3일 때, n = 9일 때... 이렇게 차례로 생각해보자.

n = 3일 때, 9개의 칸중에서 가운데의 한 칸을 제외하고 나머지의 칸들에 별이 찍히게 된다.

즉 가운데가 빈다는 뜻이다.

n = 9인 경우와, 예시로 보여준 n = 27인 경우에도, 가운데가 크게 비어있는 것을 알 수 있다.

일단 이러한 패턴이 반복된다는 것을 알 수 있다.

그리고, n = 9인 상황을 그려내기 위해서는 n = 3인 상황을 9번(공백이 찍히는 것도 포함) 수행한다는 것을 알 수 있다.

즉 재귀를 활용해야겠다는 촉을 잡을 수 있다.

이전에 보았던 Z라는 재귀를 활용한 문제와 유사한 패턴이다.

때문에 유사한 방식을 사용해서 풀이를 진행했다.

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

char arr[2188][2188] = { ' ', };

void func(int len, int row, int col) {
	if (len == 3) {
		int cur = 0;
		for (int i = row; i < row + len; i++) {
			for (int j = col; j < col + len; j++) {
				if (cur == 4) {
					cur++;
					continue;
				}
				arr[i][j] = '*';
				cur++;
			}
		}
		return;
	}
	func(len / 3, row, col);
	func(len / 3, row, col + len / 3);
	func(len / 3, row, col + len / 3 * 2);
	func(len / 3, row + len / 3, col);
	//func(len / 3, row + len / 3, col + len / 3, ' ');
	func(len / 3, row + len / 3, col + len / 3 * 2);
	func(len / 3, row + len / 3 * 2, col);
	func(len / 3, row + len / 3 * 2, col + len / 3);
	func(len / 3, row + len / 3 * 2, col + len / 3 * 2);

}
int main(void) {
	
	//cout << pow(3, 7);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	func(n, 0, 0);
	
	//별이 아닌 부분 공백으로 채워줘야한다.
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] != '*')
				arr[i][j] = ' ';
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << arr[i][j];
		}
		cout << '\n';
	}
	return 0;
}

입력값의 범위에 맞게 최대 배열의 크기를 잡기 위해서 먼저 3의 7승의 값을 확인했었다.

재귀를 하면서 변하는 값들인 n과, row, col을 인자로 넘겨주었다. 

n = 3일 때를 base condition으로 두었다. 5번째 별이 찍힐 차례일 때 별을 찍지 않고 넘어가도록 처리를 해주었다.

앞서 언급했듯이, 재귀의 큰 흐름은 총 9단계에 거쳐서 진행된다. 그중 5번째에서 아무것도 찍지 않으면 된다.

아무것도 찍지 않았을 때 WA를 받아서, 혹시나 하는 마음으로 별이 아닌 곳에 공백을 찍어주는 작업을 했더니 정답처리를 받았다.

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

#include<iostream>
using namespace std;
int main(void) {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 2*n - 1 ; j++) {
			if (j < i) cout << ' ';
			else if (j >= i && j <= 2 * n - i)
				cout << '*';
		}
		cout << '\n';
	}
			
	return 0;
}

문제 링크

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

뒷부분 공백을 출력하려고 하면 출력형식이 잘못되었다고 결과가 나온다.

#include<iostream>
using namespace std;
int main(void) {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 2*n - 1 ; j++) {
			if (j > n - i && j < n + i)
				cout << "*";
			else if (j <= n - i) //앞부분의 공백
				cout << ' ';
			//뒷부분 공백 출력하려고 하면 출력형식 잘못되었다고 나옴
		}
		cout << '\n';
	}
			
	return 0;
}

문제 링크

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

#include<iostream>
using namespace std;
int main(void) {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n ; j++) {
			if (j >= i)
				cout << '*';
			else
				cout << ' ';
		}
		cout << '\n';
	}
			
	return 0;
}

문제 링크

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

#include<iostream>
using namespace std;
int main(void) {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; i + j <= n + 1; j++) {
			cout << '*';
		}
		cout << '\n';
	}
			
	return 0;
}

문제 링크

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

별들을 오른쪽 정렬해서 찍어내는 문제이다.

어떤 조건에서 공백을 출력할 것인지, 어떤 조건에서 별을 출력할 것인지 고민해보면 된다.

1-indexed 설정에서 , i + j > n인 경우에 별을 찍고, 나머지는 공백을 찍어주면 된다.

#include<iostream>
using namespace std;
int main(void) {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i + j > n) cout << '*';
			else
				cout << ' ';
		}
		cout << '\n';
	}
			
	return 0;
}

문제 링크

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

재귀라는 아이디어는 쉽게 얻을 수 있었다.

구체적인 구현을 하는 데에는 시간이 꽤 걸렸다.

문제 제목처럼, 2차원 배열 모양의 평면을 반복적인 Z 모양으로 탐색하는 것이다.

재귀 함수를 구현할 때, base condition(탈출 조건)을 2*2 즉 한 변의 길이가 2일 때로 설정하면 된다.

그리고 순회하면서 0부터 쭉 순회 순서를 카운트 해줘야하기 때문에 전역 변수로 cnt를 두었다.

그림을 보면 n = 2일 때는 n = 1일 때의 상황이 네 번 반복된다.

또한 n = 3일 때는, n = 2일 때의 상황이 네 번 반복된다는 것을 알 수 있다.

따라서 base condition이 아닌 n을 처리하기 위해서는 4번의 n - 1을 처리하는 과정이 필요하다는 것을 알 수 있다.

2의 n승 형태로 인자가 들어가기 때문에 1<<n을 사용했다.

#include<iostream>
using namespace std;
int cnt = 0;
int n, r, c;
void func(int len, int row, int col) {
	//base condition: n = 2일 때
	if (len == 2) {
		if (row == r && col == c) {
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		if (row == r && col + 1 == c)
		{
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		if (row + 1 == r && col == c)
		{
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		if (row + 1== r && col + 1 == c)
		{
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		return;
		
	}
	func(len / 2, row, col);
	func(len / 2, row, col + len / 2);
	func(len / 2, row + len / 2, col);
	func(len / 2, row + len / 2, col + len / 2);

}
int main(void) {

	
	cin >> n >> r >> c;
	func(1 << n, 0, 0);

	return 0;
}