[Baekjoon] 4779번: 칸토어 집합

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

4779번: 칸토어 집합

 

---

 

문제 해결 과정

착안

주어진 문제에서의 배열을 3등분하여 왼쪽, 가운데, 오른쪽 부분 배열로 나누고 이때 왼쪽과 오른쪽의 부분 배열에 대해서 같은 과정을 반복적으로 수행하여 최종 답을 얻을 수 있다. 즉, 부분 문제들의 해를 합하여 최종 해를 구할 수 있는 문제이므로 분할 정복(divide and conquer) 알고리즘을 구현하여 문제를 해결하고자 하였다.

 

인수로 전달되는 배열의 길이가 1이 될 때까지, 길이에 대해 3등분하여 왼쪽, 가운데, 오른쪽의 작은 부분 배열로 나누고, 왼쪽과 오른쪽 부분 배열에 대해서는 재귀를 통해 작업을 반복하여 문제를 해결하고자 하였다.

 

구현

문제를 해결하기 위해 입력받은 \(N\)의 값에 따라 \(3^N\) 길이의 문자열을 저장할 char 배열을 만들고, 분할 정복 알고리즘에 따라 최종적인 칸토어 집합(Cantor set)의 근사를 나타내는 문자열을 만든 뒤 해당 문자열을 출력하였다.

 

굳이 기존의 배열을 복사하여 부분 배열을 만들 필요는 없으므로 재귀를 통해 인수로 배열을 전달할 때, 전체 배열을 그대로 전달하되 부분 배열만을 다루기 위한 부분 배열의 왼쪽과 오른쪽 끝 index를 나타내는 p, q 변수를 이용해 문제를 해결하였다.

 

집합을 3등분하여 가운데 부분 집합을 비우는 과정이 계속될 수록 빈 공간이 길이가 더 많아지는 칸토어 집합의 특성상, 배열의 요소를 모두 공백 문자로(' ')로 초기화하고 이후 연산을 수행하면서 부분 배열이 길이가 1이 될 때만 '-' 문자로 바꾸는 방식이 연산량이 적을 것 같아 이러한 방법으로 구현해보았다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

void Cantor(char* set, int p, int q)
{
	if (p > q)
		return;

	if (p == q)
		set[p] = '-';
	else
	{
		int l = (q - p + 1) / 3 - 1;
		Cantor(set, p, p + l);
		Cantor(set, q - l, q);
	}
}

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

	int N;
	while (true)
	{
		cin >> N;
		if (cin.eof())
			return 0;

		int len = (int)pow(3, N);
		char* CantorSet = new char[len + 1];
		memset(CantorSet, ' ', sizeof(char) * len);
		CantorSet[len] = '\0';

		Cantor(CantorSet, 0, len - 1);

		cout << CantorSet << "\n";
		delete[] CantorSet;
	}
}

 

출력할 문자열을 전부 저장하지 않고 그때그때 '-' 문자 또는 ' ' 문자를 길이에 맞게 출력하여 해결할 수도 있는데, 이렇게 문제를 해결하는 경우에는 문자열을 저장할 배열을 사용하지 않으므로 메모리 측면에서는 더 유리하지만 반복적인 문자 출력으로 인해 실행 속도면에서 불리해지게 된다(특히 \(N\)의 값이 커질 수록). 실행 속도 저하를 감수하더라도 메모리 절약의 필요성이 있을 때에는 아래의 같이 Cantor 함수를 구현할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

void Cantor(int p, int q)
{
	if (p > q)
		return;

	if (p == q)
		cout << '-';				// 저장하지 않고 출력
	else
	{
		int l = (q - p + 1) / 3 - 1;
		Cantor(p, p + l);
        
		for (int i = 0; i < l + 1; i++)		// 저장하지 않고 출력
			cout << " ";
        
		Cantor(q - l, q);
	}
}

 

실행 결과

아래 결과: 문자열을 저장한 뒤 마지막에 출력하여 해결한 결과 / 위 결과: 문자열을 저장하지 않고 해결한 결과