(백준/C++) 4779번_칸토어 집합

4779번: 칸토어 집합 (acmicpc.net) 문제는 분할 정복(divide and conquer)과 재귀(recursion)에 대한 문제입니다.

분할 정복이란, 큰 문제를 작은 문제로 나누고 그 결과를 조합해 원래 문제를 해결하는 방법입니다.

칸토어 집합 이해하기

우선 칸토어 집합이란 간단히 말해서 길이가 1인 선분에서 1/3부터 2/3까지의 1/3만큼 지우는 것입니다.

그리고 나머지 부분에 대해서도 같은 동작을 반복해서 만들어지는 집합이 칸토어 집합입니다.

---

풀이 과정

이 문제는 칸토어 집합에서의 동작에 해당하는 부분을 재귀적으로 반복하는 문제입니다.

1. 1/3부터 2/3까지의 문자를 공백으로 지워버리고
2. 나머지 부분(0~1/3 부분과 2/3~1 부분)에 대해 같은 동작을 재귀 호출하는 문제입니다.

하지만, 분할 정복(divide and conquer)에 대한 접근법을 통해 차례차레 생각해 보겠습니다.

1. 기저 사례 설정 (Base case)

세 부분으로 나눈 후 중간 부분을 제거하는 과정을 재귀적으로 반복하되, 선분의 길이가 0이 되면 더 이상 선분을 제거하지 않는 것으로 기저 사례를 설정합니다.

기저 사례(Base case)

기저 사례(Base case)란, 재귀 함수가 더 이상 자신을 호출하지 않고 값을 직접 반환하는 조건을 의미합니다.
즉, 재귀 호출을 중단하는 조건이며, 재귀 함수가 무한히 반복되는 것을 방지합니다.

2. 분할(Divide)

선분을 처음부터 1/3까지, 1/3부터 2/3까지, 그리고 2/3부터 끝까지로 세 부분으로 나눕니다.

3. 정복(Conquer)

세 부분 중에서 가운데 부분을 제거하고, 나머지 두 부분에 대해서도 같은 과정을 재귀적으로 반복합니다.

4. 병합(Combine)

이 문제에서 병합 단계는 따로 없습니다. 왜냐하면 각 선분이 독립적으로 처리되고, 각 선분을 별도로 조합할 필요가 없기 때문입니다.

이런 과정을 통해 문제를 해결할 수 있습니다. 저는 이번 문제를 풀면서 string 라이브러리의 함수를 연습하는 겸 string 라이브러리의 replace 함수를 활용해보았습니다.

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

void CantorSet(string& str, int s, int e)
{
	int size = static_cast<int>((e - s) * 0.33333334);
	if (size == 0) return; //기저 사례 처리

	int a = s + size;
	int b = s + 2 * size;

	str.replace(a, size, size, ' '); //가운데 부분 제거

  //나머지 두 부분에 대해 같은 과정 반복
	CantorSet(str, s, a);
	CantorSet(str, b, e);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	while(cin >> N)
	{
		string str;
		str.append(pow(3, N), '-');

		CantorSet(str, 0, str.length());

		cout << str << '\n';
	}
}

string 라이브러리의 replace()의 시그니처중 replace(size_t pos, size_t len, size_t n, char c)는 pos 위치에서부터 len 만큼의 문자를 n개의 c문자로 바꿔주는 함수입니다.

이번 문제에서는 replace를 쓰기 좋은 문제여서 string으로 풀면서 연습해보는 것도 좋을 것 같습니다.