기록을

문제 링크는 다음과 같다.

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

수열에 오름차순이라는 조건이 존재하기 때문에 수열을 만들기 전에 입력받은 수들을 오름차순 정렬해준다.

또한 증가수열로 나타내야 하기 때문에 특정 자리의 숫자로는, 이 전 자리의 숫자보다 큰 숫자만 올 수 있다.

즉 길이 3인 수열을 만들어야 하는데, 첫 번째 숫자를 3으로 정해놨다고 하자.

3 _ _

이런 상태인데, 2번째 자리에 올 수 있는 숫자는 3보다 큰 숫자라는 뜻이다.

따라서 arr[k - 1] < num[i] 이 조건을 추가해서 구현해주면 된다.

물론 다음 재귀로 들어가기 전에 전역변수를 둬서 i를 저장해두거나, 재귀 함수의 인자로 몇 번째 index의 숫자를 사용했는지 관리해주는 방법도 있다.

func(1)은 이제 첫번째 자리의 숫자를 정해야 한다는 의미이다.

따라서 base condition은 이제 M+1번째 자리의 숫자를 정할 타이밍 일 것이다. 이때가 M번째 숫자까지 결정되었다는 의미이기 때문이다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> num[i];
	sort(num + 1, num + N + 1);
	
	func(1);
	return 0;
}

문제 링크

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

사용할 수 있는 수들을 입력으로 받는다.

수열들을 오름차순으로 뽑아내야 한다.

사용되는 숫자들을 사전에 오름차순으로 정렬해두면 된다.

재귀함수의 인자는 숫자의 번호라고 생각하면 되겠다. 즉 k가 1인경우는, 첫번째 숫자를 결정할 차례라는 뜻이다.

길이를 M으로 입력받기 때문에, k가 M+1이 되면 M+1번째 숫자를 결정할 차례라는 의미이므로 이미 M번째 까지는 결정이 되었다는 의미이다.

따라서 k == M+1인 경우를 base condition으로 설정해주면 된다.

또한 재귀를 빠져나온 이후에는, 숫자를 사용중이 아닌 것이 되기때문에, isused값을 다시 false로 바꿔줘야한다.

만약 k를 전역변수로 두고 코딩을 한다면 k또한 재귀를 들어가기전에는 증가, 재귀에서 빠져 나온 이후에는 감소를 해줘야 할 것이다.

#include<iostream>
#include<algorithm>
using namespace std;
int N, M;
int arr[10], num[10];
bool isused[10];

void func(int k) {
	if (k == M + 1) {
		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] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}

}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> num[i];
	}
	sort(num + 1, num + N + 1);

	func(1);

	return 0;
}

문제 링크

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

중복을 허용하면서 감소하지 않는 수열로 만들어야 한다.

따라서 재귀를 이전 자리에 쓰인 숫자부터 진행하면 된다. 

첫번째 자리의 숫자를 정할 때, 이전에 쓰인 숫자가 없기 때문에, 이 경우에만 st를 1로 정해주면 된다.

#include<iostream>
using namespace std;
int N, M;
int arr[9];
void func(int k) {
	if (k > M) {
		for (int i = 1; i <= M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	int st = 1;
	if (k != 1) st = arr[k - 1];
	for (int i = st ; i <= N; i++) {
		
		arr[k] = i;
		func(k + 1);
	}
}
int main(void) {
	cin >> N >> M;
	func(1);
	return 0;
}

문제는 아래와 같다.

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

이번에는 숫자를 중복해서 사용할 수 있다.

이전까지는 숫자의 중복을 제한하기 위해서 isused배열을 사용했다. 숫자가 arr배열을 이루는 데에 사용되고 있다면 true 값을 가지도록 하고 그렇지 않은 경우 false 값을 가지도록 하였다.

이번에는 이것이 필요하지 않다.

또한 문제를 풀이하는 과정에 있어서, 배열을 인자로 넘기지 않고 전역변수로 사용해도 좋다.

k값도 마찬가지이다. k값을 인자로 넘기지 않으려면, 재귀에 들어가기 전에 k값을 증가시키고,

재귀에서 탈출한 이후에는 k값을 줄여줘야한다.

또한 k를 0부터 시작할지 1부터 시작할지도 편한 데로 선택하면 되겠다.

나 같은 경우에는 k를 0부터 시작하는 경우, ~까지는 수열이 만들어져 있다는 의미로 보았다.

1부터 시작하는 경우에는, 이번에는 ~번째 자리의 숫자를 채울 차례다라는 의미로 생각하면 되겠다.

당연하게도 의미가 다르기 때문에 base condition의 조건도 달라져야 한다.

전자의 경우 k==m인 경우가 기저 조건이고, 후자의 경우 k > m 인 경우를 기저 조건이라고 보면 된다.

//전역변수 활용
#include<iostream>
using namespace std;
int arr[8], N, M; //1 indexed
//int k = 0;
void func(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++) {
		arr[k] = i;
		func(k + 1);
	}
}
int main(void) {
	cin >> N >> M;
	func(1); 
	return 0;
}

문제 링크는 다음과 같다.

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;

}