📍 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(a.k.a. 종만북)>으로 공부한 내용을 정리한 게시글입니다.
📍 ChatGPT에게 추천 받은 분할 정복 문제 3개

분할 정복

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산

• divide : 문제를 더 작은 문제로 분할하는 과정
• merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정
• base case : 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

✔️ 분할 정복을 이용하면 같은 작업을 더 빠르게 처리 가능

1992 쿼드트리

분류 : 분할 정복, 재귀

#include <iostream>
using namespace std;

char arr[65][65];
string quad = "";

void quadtree(int a, int b, int n) {
	bool endflag = 0;
	if (n == 1) {
		quad += arr[a][b];
	}
	else {
		for (int i = a; i < a + n; i++) {
			for (int j = b; j < b + n; j++) {
				if (arr[a][b] != arr[i][j]) {
					endflag = 1;
					break;
				}
			}
			if (endflag) break;
		}
		if (endflag) {
			quad += "(";
			quadtree(a, b, n / 2);
			quadtree(a, b + n / 2, n / 2);
			quadtree(a + n / 2, b, n / 2);
			quadtree(a + n / 2, b + n / 2, n / 2);
			quad += ")";
		}
		else {
			quad += arr[a][b];
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}

	quadtree(0, 0, N);
	cout << quad;
}

📍 cin, cout 입출력 빠르게

ios::sync_with_stdio(false);
cin.tie(NULL);

ios::sync_with_stdio(false)
cin, cout은 stdio.h와 동기화 -> iostream의 버퍼와 stdio.h의 버퍼를 같이 씀
➡️ sync_with_stdio(false) 로 두 버퍼를 독립적으로 사용

sync_with_stdio(false)를 쓸 때 유의할 점

• C의 입출력 방식(printf, scanf, getchar, ...)과 동시 사용 불가
• 멀티쓰레드 불가

cin.tie(NULL)
cin과 cout의 상호 연결을 해제

2630 색종이 만들기

분류 : 분할 정복, 재귀

#include <iostream>
using namespace std;

int sqr[130][130];
int w = 0, bl = 0;

void square(int a, int b, int n) {
	if (n == 1) {
		if (sqr[a][b] == 1) ++bl;
		else ++w;
	}
	else {
		bool endflag = 0;
		for (int i = a; i < a + n; i++) {
			for (int j = b; j < b + n; j++) {
				if (sqr[a][b] != sqr[i][j]) {
					endflag = 1;
					break;
				}
			}
			if (endflag) break;
		}
		if (endflag) {
			square(a, b, n / 2);
			square(a, b + n / 2, n / 2);
			square(a + n / 2, b, n / 2);
			square(a + n / 2, b + n / 2, n / 2);
		}
		else {
			if (sqr[a][b] == 1) ++bl;
			else ++w;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> sqr[i][j];
		}
	}
	square(0, 0, N);
	cout << w << '\n' << bl;
}

쿼드 트리와 알고리즘 동일

10815 숫자 카드

분류 : 자료 구조, 정렬, 이분 탐색

#include <iostream>
#include <algorithm>
using namespace std;

int card[500002];
int num[500002];
int ans[500002];

int find(int a, int b, int findNum) {
	if (a > b) return 0;
	if (card[(a + b) / 2] == findNum) {
		return 1;
	}
	else if (card[(a + b) / 2] < findNum) {
		return find((a + b) / 2 + 1, b, findNum);
	}
	else {
		return find(a, (a + b) / 2 - 1, findNum);
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> card[i];
	}
	sort(card, card + N);

	cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> num[i];
		cout << find(0, N, num[i]) << " ";
	}
}