백준 알고리즘 중급 - 분할정복 (연습)

알듯 말듯한 분할 정복....

감을 잡을 것 같으면서도 못 잡겠다.

많이 헤맸던 챕터였다. 그만큼 꼭꼭 씹고 넘어가자.

정리 시작.

-

* 종이의 개수 (mid) : 종이가 모두 같은 수면 그 종이를 사용하고, 아니면 9개로 나눠서 앞의 조건을 다시 검사해준다. 

1780번: 종이의 개수

 

 - 모든 수가 같은가? -> yes : 해당 수 count +1 / no : 9개로 분할 (재귀)

#include <cstdio>
#include <vector>
using namespace std;
int a[2187][2187];
int c[3] = { 0, };

bool checkAll(int n, int x, int y) {
	int check = a[x][y];
	for (int i = x; i < x+n; i++) {
		for (int j = y; j < y+n; j++) {
			if (a[x][y] != a[i][j])
				return false;
		}
	}
	return true;
}

void go(int n, int x, int y) {
	if (checkAll(n, x, y)) {
		c[a[x][y] + 1] += 1;
	}
	else {
		int m = n / 3;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				go(m, x + m*i, y + m*j);
			}
		}
	}
}

int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &a[i][j]);
		}
	}

	go(n, 0, 0);
	printf("%d\n%d\n%d\n", c[0], c[1], c[2]);

	return 0;
}

 - 가장 기본적인 분할 정복 예시였다. 이제 쭉쭉 응용해보자.

 

* 하노이 탑 이동 순서 (mid) : 너무나도 유명한 하노이 탑 문제다.

11729번: 하노이 탑 이동 순서

- 장대를 1, 2, 3이라고 할 때, 1) n-1개를 1에서 2로 2) 1개를 1에서 3으로 3) n-1개를 2에서 3으로

- 개수는 원판이 n개일 때 2^n -1이다. 점화식으로 유도할 수 있다. 궁금하면 찾아보길.

#include <cstdio>
using namespace std;

void go(int n, int from, int to) {
	if (n == 0) return;
	go(n - 1, from, 6 - from - to);
	printf("%d %d\n", from, to);
	go(n - 1, 6 - from - to, to);
}

int main()
{
	int n;
	scanf("%d", &n);

	printf("%d\n", (1 << n) - 1);
	go(n - 1, 1, 2);
	printf("1 3\n");
	go(n - 1, 2, 3);

	return 0;
}

 

* 트리의 순회 (high) : 좀 어려워지기 시작했다. 인오더와 포스트오더를 알 때, 프리 오더를 구하면 된다.

2263번: 트리의 순회

 - 인오더 : L루R / 포스트오더 : LR루 / 프리오더 : 루LR

 - 가장 쉽게 알 수 있는 것은 포스트오더의 마지막 항이 루트라는 사실이다. 또한, 인오더에서 루트의 위치를 안다면 왼쪽 항과 오른쪽 항을 구분할 수 있다. 

 - 이를 이용해 포스트오더를 뒤에서부터 추적해나가면서, 동시에 인오더에서 루트의 위치를 파악해 왼쪽 항과 오른쪽 항을 구분해나가면 프리오더를 구할 수 있다.

#include <cstdio>
using namespace std;

int inorder[100000];
int postorder[100000];
int position[100001];

void go(int in_start, int in_end, int post_start, int post_end) {
	if (in_start > in_end || post_start > post_end) return;
	int pre = postorder[post_end];
	printf("%d ", pre);
	int p = position[pre];
	int left = p - in_start;
	go(in_start, p - 1, post_start, post_start + left - 1);
	go(p + 1, in_end, post_start + left, post_end - 1);
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &inorder[i]);
	for (int i = 0; i < n; i++) scanf("%d", &postorder[i]);
	for (int i = 0; i < n; i++) position[inorder[i]] = i;
	go(0, n - 1, 0, n - 1);
	printf("\n");
	return 0;
}

 - position 배열에는 해당하는 수가 인오더에서 어디에 위치하는지 기록한다. 포스트오더에서 루트를 구할 때마다 인오더의 위치를 추적하는 번거로움을 덜어주기 위함이다.

 - p에는 현재 포스트오더의 가장 마지막 항이 인오더에서 어떤 위치에 있는지를 기록하고, left는 p를 바탕으로 현재 왼쪽항이 몇개인지 구한다.

 - p와 left를 이용해 인오더, 포스트오더를 각각 L, R 순서로 탐색한다. 그럼 루LR 순서로 탐색하는 것이 되므로, 구하는대로 출력하면 프리오더가 된다.

 - 인덱스 하나만 삐끗해도 틀릴 수 있는 문제다. 적절하게 값을 구해서 누락되는 값이 없도록 함수를 설계해야 한다.

 

* Z (mid) : Z 모양대로 재귀적으로 2^n * 2^n 배열을 탐색한다고 할 때, 해당하는 위치를 몇 번째 방문하는지 구하는 문제다.

1074번: Z

 - n이 1일 때 -> 방문 횟수에 2*x+y를 더한다.

 - n이 1이 아닐 때 -> 배열을 4등분 했을 때, 위치에 따라 2^2(n-1)을 적절히 더해주고, 좌표를 이동해준다. 다음 영역으로 이동할 때마다 2^(n-1) * 2^(n-1) 칸을 지나오기 때문이다.

#include <cstdio>
using namespace std;

int pow2(int n) {
	return 1 << n;
}

int go(int n, int x, int y) {
	if (n == 1) {
		return 2 * x + y;
	}
	else {
		if (x < pow2(n - 1)) {
			if (y < pow2(n - 1)) {
				return go(n - 1, x, y);
			}
			else {
				return go(n - 1, x, y - pow2(n - 1)) + pow2(2 * (n - 1));
			}
		}
		else {
			if (y < pow2(n - 1)) {
				return go(n - 1, x - pow2(n - 1), y) + pow2(2 * (n - 1)) * 2;
			}
			else {
				return go(n - 1, x - pow2(n - 1), y - pow2(n - 1)) 
					+ pow2(2 * (n - 1)) * 3;
			}
		}
	}
}

int main()
{
	int n, r, c;
	scanf("%d %d %d", &n, &r, &c);

	printf("%d\n", go(n, r, c));

	return 0;
}

 - 분할 정복의 정석에 가까운 문제였다. 재귀를 통해 2^n * 2^n을 2*2으로 땡겨오면서, 이동한 거리만큼을 더해주는 방식이다. 접근 방법에 따라 다양한 풀이가 나올 수 있다. 다양한 시도를 하면서 나한테 맞는 과정을 찾아가보자.

 

* 사분면 (high) : 사분면의 사분면의 사분면...의 자릿수가 주어질 때, 주어진 조건만큼 이동한 뒤에 자릿수가 어떻게 변하는지 구하는 문제다.

1891번: 사분면

 - 자릿수의 길이가 n이고 (0,0)부터 출발한다고 했을 때, 앞에서부터 차례대로 자릿수를 분석해간다고 해보자. 자릿수가 1일 때는 y 좌표에 n/2를 더해준다. 2일 때는 그대로 있으면 될 것이고, 3일 때는 x 좌표에 n/2를 더해준다. 4일 때는 x와 y좌표에 모두 n/2를 더해준다.

 - 재귀를 통해 값을 구하면 자릿수를 좌표상의 점으로 표현할 수 있다. 이 점에서 주어진 이동거리만큼 이동을 해본다. 가능한 절대값이 2^50까지이므로, 2^50까지의 수를 미리 구해놓는 것도 좋은 방법이다.

 - y의 이동방식이 좌표상의 크기 변화와 반대 양상을 띄고 있으므로 부호를 바꿔줘야 한다. 문제를 잘 읽었는지 확인하는 단계인 것 같다. 무턱대고 x, y를 x좌표, y좌표에 더하는 순간 망한다. x는 왼쪽, 오른쪽으로 이동하는 것을 나타냄으로 y좌표에, y는 x좌표에 더해줘야 한다.

 - 이동한 좌표가 범위를 벗어나면 -1을 출력하고, 벗어나지 않는다면 좌표를 다시 자릿수로 변환해줘야 한다. 이는 아까와 반대로 현재 자릿값 (p,q)에서 가장 큰 사분면부터 작은 사분면까지 좁혀 들어가면서 생각해주면 된다.

#include <iostream>
#include <string>
using namespace std;
pair<long long, long long> go(string &a, int index, long long x, long long y, long long size) {
	if (size == 1) {
		return make_pair(x, y);
	}
	else {
		if (a[index] == '1') {
			return go(a, index + 1, x, y + size / 2, size / 2);
		}
		else if (a[index] == '2') {
			return go(a, index + 1, x, y, size / 2);
		}
		else if (a[index] == '3') {
			return go(a, index + 1, x + size / 2, y, size / 2);
		}
		else {
			return go(a, index + 1, x + size / 2, y + size / 2, size / 2);
		}
	}
	return make_pair(0, 0);
}

string gogo(long long r, long long c, long long size, long long x, long long y) {
	if (size == 1) {
		return "";
	}
	else {
		if (x < r + size / 2 && y < c + size / 2) {
			return "2" + gogo(r, c, size / 2, x, y);
		}
		else if (x < r + size / 2 && y >= c + size / 2) {
			return "1" + gogo(r, c + size / 2, size / 2, x, y);
		}
		else if (x >= r + size / 2 && y < c + size / 2) {
			return "3" + gogo(r + size / 2, c, size / 2, x, y);
		}
		else {
			return "4" + gogo(r + size / 2, c + size / 2, size / 2, x, y);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	long long two[51];
	two[0] = 1;
	for (int i = 1; i <= 50; i++) two[i] = two[i - 1] * 2LL;
	int d;
	string a;
	cin >> d >> a;
	long long size = two[a.size()];
	auto p = go(a, 0, 0, 0, size);
	
	long long x, y;
	cin >> x >> y;
	y = -y;
	p.first += y;
	p.second += x;

	if (0 <= p.first && p.first < size && 0 <= p.second && p.second < size) {
		cout << gogo(0, 0, size, p.first, p.second);
	}
	else {
		cout << -1;
	}
	cout << '\n';

	return 0;
}

 - 재귀 센스가 꽤나 필요한 문제였다. 코드만 보면 머리 아프지만, 어떤 방식으로 탐색을 해가는지 그림을 그려보면서 서 차근차근 생각해보면서 이해하자.

 

* 별 찍기 - 10 (mid) : 재귀엔 정말 다양한 방법이 있다는 것을 깨달은 문제였다. 조건에 맞게 별을 출력하면 된다.

2447번: 별 찍기 - 10

- n은 3의 거듭제곱이고 3^8까지 가능하다. n이 3일 때, 가운데만 빈칸이 생기는 모양이 된다. n이 3보다 클 때는 가운데 n/3 * n/3 크기 만큼 빈칸이 생기는 모양이 된다.

- 빈칸을 다 찍고 별을 찍어도 되고, 별을 다 찍고 빈칸을 찍어도 된다. 빈칸이 더 적으니, 별을 다 찍고 빈칸을 찍는 방법을 택했다. (0,0)부터 시작해서 n이 3이면 현재 위치가 (x,y)일 때 (x+1,y+1)에 빈칸을 넣어준다. n이 3보다 크다면 가운데 n/3 * n/3 만큼 빈칸을 넣어주고, 9등분하여 재귀 이동을 해주는데, 이때 가운데는 빈칸이므로 건너 뛰어준다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
const char STAR = '*';
const char BLANK = ' ';

void go(vector<vector<char> > &a, int n, int x, int y) {
	if (n == 3) {
		a[x + 1][y + 1] = BLANK;
		return;
	}
	int m = n / 3;
	for (int i = x + m; i < x + m * 2; i++) {
		for (int j = y + m; j < y + m * 2; j++) {
			a[i][j] = BLANK;
		}
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == 1 && j == 1) continue;
			go(a, m, x + m*i, y + m*j);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<vector<char> > a(n, vector<char>(n, STAR));
	go(a, n, 0, 0);
	for (int i = 0; i < n; i++) {
		cout << string(a[i].begin(), a[i].end()) << '\n';
	}
	return 0;
}

- 출력을 할 때 string(begin, end)와 같은 편한 방법이 있었다. 잘 써먹어보자.

 

* 별 찍기 - 11 (mid) : 정답 코드가 너무 복잡해서 열받았는데, 질문란을 찾아보다 겨우 구원 받은 문제다.

2448번: 별 찍기 - 11

- 코드를 설명도 안 하고 넘어가길래.. 쉽다고 생각했다. 결과적으로 그리 어렵게 풀리는 문제는 아니었는데, 정답 코드가 쓸데 없이 복잡했다. 이해도 잘 안 되는데 코드까지 어려우니 미칠 것 같았는데, 질문 게시판을 뒤지다가 좋은 요령을 발견해 겨우 이해했다.

- 앞의 문제처럼 빈칸 도배와 별 도배 두 갈래 길에 놓이는데, 이 문제는 빈칸이 훨씬 많다. 빈칸을 다 깔아놓고 별을 그리는 방식으로 진행했다. 앞의 문제와 달리 가로가 n이면 세로는 2*n-1인데, 어차피 빈칸이니 그냥 2n으로 처리했다.

- 아까처럼 (0,0)에서 출발하는 것이니 삼각형의 꼭지점을 가리키는 것이 아니라 삼각형을 딱 맞게 포함한 직사각형의 가장 왼쪽 끝을 가리킨다고 생각하면 된다. n이 3일 때 삼각형 모양을 그려주고, n이 3보다 클 때는 높이가 n인 삼각형 내부의 높이가 n/2인 3개의 삼각형을 포함하고 있는 각각의 직사각형 맨끝으로 이동하도록 재귀를 짜준다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
const char STAR = '*';
const char BLANK = ' ';

void go(vector<vector<char> > &a, int n, int x, int y) {
	if (n == 3) {
		a[x][y + 2] = STAR;
		a[x + 1][y + 1] = a[x+1][y + 3] = STAR;
		for (int i = 0; i < 5; i++) a[x + 2][y + i] = STAR;
	}
	else {
		go(a, n / 2, x, y + n / 2);
		go(a, n / 2, x + n / 2, y);
		go(a, n / 2, x + n / 2, y + n);

	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<vector<char> > a(n, vector<char>(n*2, BLANK));
	go(a, n, 0, 0);
	for (int i = 0; i < n; i++) {
		cout << string(a[i].begin(), a[i].end()) << '\n';
	}
	return 0;
}

- 같은 문제를 푼 것이 맞나 싶을 정도로 강의에서 제공하는 정답 코드는 복잡하기 그지 없더라... 항상 정답 코드를 보면 명쾌했는데, 이번 코드는 처음으로 좀 아쉬웠다..

 

* 버블 소트 (mid) : 버블 소트를 할 때 swap이 몇번 발생하는지 구하는 문제였다. 풀이보다는 발상 자체가 까다로웠다.

1517번: 버블 소트

- n개의 정수를 소팅해야 하는데 n의 범위가 50만이기에 n^2은 어림도 없다.

- 여기서는 머지 소트를 이용해야 했다. 머지 소트는 수열을 쪼갠 뒤에 순서대로 합치면서 소팅을 한다. 이 과정에서 왼쪽에 수가 있는 상황에서 오른쪽에 있는 항이 먼저 합쳐진다면 아직 남아 있는 왼쪽 항의 개수만큼 swap한 것임을 알 수 있다. a[i] > a[j]인데 i<j인 경우다. inversion이라고 한단다. (테넷 또 보고 싶다)

#include <iostream>
#include <vector>
using namespace std;
vector<int> a, b;
long long go(int low, int high) {
	if (low == high) {
		return 0;
	}
	int mid = (low + high) / 2;
	long long ans = go(low, mid) + go(mid + 1, high);
	int i = low, j = mid + 1, k = 0;
	while (i <= mid || j <= high) {
		if (i <= mid && (j > high || a[i] <= a[j])) {
			b[k++] = a[i++];
		}
		else {
			ans += (long long)mid - i + 1;
			b[k++] = a[j++];
		}
	}
	for (int i = low; i <= high; i++) {
		a[i] = b[i - low];
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	int t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		a.push_back(t);
		b.push_back(0);
	}
	cout << go(0, n - 1) << '\n';
	return 0;
}

- inversion인 경우만 카운트 해줘서 ans에 더하고 재귀 호출로 모든 ans 값을 더해주면 된다.

- 오른쪽에서 합쳐질 때, 왼쪽에 항이 존재하는 만큼 swap이 이루어진다는 사실을 알아야 풀 수 있어서 까다로웠다.

-

재귀는 정말 어렵다. 미치겠다.

다음은 도전인데.. 또 얼마나 절지 모르겠다.

여기서 시행착오를 많이 겪었으니까.. 도전 파트에서는 이런저런 시도라도 많이 해보길..

정리 끝!