기록을

문제 링크는 다음과 같다.

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;
}

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

중학교 수학 문제에 등장했던 하노이의 탑이다.

재귀를 이용한다. 5개의 링을 옮기는 과정 속에는 4개의 링을 옮기는 과정이 포함된다.

4개의 링을 옮기는 과정 속에는 3개의 링을 옮기는 과정이 포함된다.

이런식으로 끄적이며 생각해보면 재귀라는 아이디어를 얻을 수 있을 것이다.

예를 들어서, 첫번째 자리에 있던 모든 링들을 세번째 자리로 옮긴다고 하자.

이를 위해서는 가장 아래에 깔려있는 가장 큰 링을 빼내야 한다. 이를 위해서는 그것 위에 있는 n - 1 개의 링을 모두 임시적으로 다른 곳에 옮길 필요가 있다.

주의할 것은, 2의 20승을 계산할 때, pow함수의 출력이 의도한대로 나오지 않는다는 것이다. 이를 위해서 1 << n 연산을 이용한다.

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

void hanoi(int src, int dst, int n) {
	if (n == 1) {
		cout << src << ' ' << dst << '\n';
		return;
	}
	int temp = 6 - src - dst;
	hanoi(src, temp, n - 1); //1 ~ n-1 링을 중간지점에 옮긴다
	cout << src << ' ' << dst << '\n'; //가장 커다란 링을 목적지로 옮긴다.
	hanoi(temp, dst, n - 1); //중간지점에 있던 n - 1 개의 링들을 목적지로 옮긴다.
}

int main(void) {
	int n;
	cin >> n; //옮기는 링의 개수
	//cout << pow(2, n) - 1 << '\n';// 이렇게 쓰면 틀림 n = 20일때 output이 이상해짐
	cout << (1 << n) - 1 << '\n'; // 2의 n승 -1
	hanoi(1, 3, n);

	return 0;
}

재귀로 풀이를 진행할 때는

1. base condition을 명확히 정의한다.

2. 재귀 식을 찾는다.

n개를 옮기려면, n - 1을 다른곳으로 옮긴 이후에 하나 옮기고 다시 n - 1을 목적지로 옮겨야해.. 와 같은

이 때, 이전 과정이 올바르게 작동할 것이라는 가정을 하고, 현재의 함수가 올바르게 결과를 내놓을지 판단한다.

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

A^B mod m을 연산하는 프로그램을 작성하는 문제이다.

수의 범위가 20억까지 가능하기 때문에 long long 타입을 활용한 것 이외에 재귀를 진행할 때도 아이디어가 하나 필요했다.

B가 홀수냐 짝수냐에 따라서 경우를 나눠줬다.

재귀의 base condition은 B가 0일 때 1을 반환하는 것이 된다.

또한 overflow를 방지하기 위해 계산하는 중간중간에 modular 연산을 수행해줄 필요가 있다.

XYmodM = (XmodM * YmodM) mod M 인 것을 이용하면 되겠다.

지수가 홀수인 경우, 계산 이후에 a를 한 번 더 곱해줘야 하고, 이 과정에서 modular 연산을 한번 더 수행해줘야 한다.

#include<iostream>
using namespace std;
typedef long long ll;

ll POW(ll a, ll b, ll m){
    if(b == 0) return 1;
    ll val = POW(a, b/2, m);
    val = val * val % m;
    
    //b가 짝수, 홀수인 경우 나눠서 처리
    if(b % 2 == 0) return val;
    else
        return (val * a) % m;
    
}

int main(void){
    int a, b, m;
    cin >> a >> b >> m;
    cout << POW(a, b, m);
    return 0;
}