이것 저것 &

문제링크:https://www.acmicpc.net/problem/10830

접근방식

1. B가 100,000,000,000 이므로 매번 곱해주는 형식으로는 무조건 시간초과

2. 행렬을 1번 곱하고 그값들로 또 1번 곱하게 되면 기존 행렬을 4번 곱한 것과 같은 형태이다.

즉 행렬곱셉은 제곱연산이 가능한 형태!! 

그러면 dp나 분할정복을 통해서 제곱으로 계산해주는 형태를 생각하게 됨.

3. 제곱값들을 한번씩만 사용해주면 되기 때문에 분할정복을 선택함 

문제풀이 

1. 아래처럼 분할정복 호출을 구현하는데, 직관적인 코드이다.

ex) b 가 10일 때, (행x행) 하나 생성하고 b는 5로

     b 가 5일 때, (행x행) 을 결과값으로 넣고 그리고 (행x행)X(행x행) 을 생성

     b 가 2일 때,  ((행x행)X(행x행)) X ((행x행)X(행x행)) 생성

     b 가 1일 때,  (행x행) 인 결과값에 ((행x행)X(행x행)) X ((행x행)X(행x행)) 를 곱해줌으로써 (행x행) X ((행x행)X(행x행)) X ((행x행)X(행x행)) 으로 10번 행이 곱해지게끔 만들어주는 방식이다. 

이러한 식 도출은 딱히 방식이 있다기 보다는 문제를 많이 풀어보면서 노하우를 습득하는 방법밖에 없는 것 같다.... 

while (b) {
		if (b % 2 == 1) {
			solved(result, arr);
		}
		solved(arr, arr);
		b /= 2;

	}

2. 행렬 곱셈은 원래 아는 방식 그대로 구현

다만, result 초기값을 단위행렬로 구성하는 것을 주의 

정답코드입니다.

#include <iostream>
using namespace std;

long long n, b;
int arr[5][5];
int result[5][5];
int temp[5][5];

void solved(int v1[5][5], int v2[5][5]) {
	

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			temp[i][j] = 0;
			for (int k = 0; k < n; k++)
				temp[i][j] += (v1[i][k] * v2[k][j]);
			temp[i][j] %= 1000;
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) 
			v1[i][j] = temp[i][j];
		
			
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> b;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
		result[i][i] = 1;
	}
	while (b) {
		if (b % 2 == 1) {
			solved(result, arr);
		}
		solved(arr, arr);
		b /= 2;

	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cout << result[i][j] << ' ';
		cout << endl;
	}

	return 0;
}

문제링크: https://www.acmicpc.net/problem/4256

접근방식

1. 두 가지 순회방법을 통해서 남은 한가지 순회방법을 찾을 수 있다.

전위는 root노드 - root기준 왼쪽 자식노드 - root기준 오른쪽 자식노드 순으로 표시되고

중위는 root기준 왼쪽 자식노드 - root노드 - root기준 오른쪽 자식노드 순으로 표시된다.

-> 그렇다면 후위순회 함수를 구현하며 노드 값을 출력하며 결과를 도출할 수 있다. 

2. 전위 순회함수로 탐색을 하며 root값에 해당하는 중위순회값을 매개변수로 전달하며 진행

3. 재귀함수, 분할정복으로 구현하였다.

문제풀이 

1. 분할정복으로 구현 

2. 전위순회를 기준으로 root 노드를 출력하는 형태

아래는 정답 코드입니다.

#include <iostream>
using namespace std;

int t;
int n;
int pre[1000] = { 0, };
int ino[1000] = { 0, };

void solved(int pl, int pr, int il, int ir) {
	if ((pr - pl) == 0) {
		cout << pre[pl] << ' ';
		return;
	}

	for (int i = 0; i <= pr - pl; i++) {
		if (pre[pl] == ino[il + i]) {
			solved(pl + 1, pl + i, il, il + i - 1);
			solved(pl + i + 1, pr, il + i + 1, ir);
			cout << pre[pl] << ' ';
			return;
		}

	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> t;

	while (t--) {
		cin >> n;

		for (int i = 0; i < n; i++)
			cin >> pre[i];
		for (int i = 0; i < n; i++)
			cin >> ino[i];

		solved(0, n - 1, 0, n - 1);
		cout << "\n";
	}

	cout << "\n";
	return 0;
}