알고스팟 weird 문제

이번엔 '알고스팟 초보용 문제' 카테고리에 있으나 개인적인 두뇌 성능이 좋지 않아 장장 2년 가까운 세월동안 13번의 시도후에 정답 판정을 받아낸 WEIRD 문제에 대해서 이야기를 해보겠다.

문제 링크 : https://algospot.com/judge/problem/read/WEIRD

젠장..

문제를 한 문장으로 요약하면 'abundant하면서 semiperfect하지 않은 자연수를 이상한 숫자라고 하는데 어떤 숫자가 주어졌을때 이게 이상한 숫자인지 아닌지 판단해내라.' 라고 할 수 있다.

알고스팟 문제도 그렇고 링크 걸어놓은 위키피디아도 죄다 영어라서 읽기 귀찮기 때문에 여기에다 정리한다. 어떤 수가 Abundant 하다는것은 그 수의 진 약수(자기 자신보다 작은 약수)의 합이 그 수보다 큰 경우를 말한다. 12, 18, 20, 24, 30, 36, 40, 42, 48 등이 있다는데 12의 경우 {1, 2, 3, 4, 6} 을 다 더하면 16이 나오고, 12보다 크니까 abundant 하다.

또한, 어떤 수가 Semiperfect하다는 것은 진 약수를 원소로 가지는 집합의 부분집합의 합이 그 수와 같을때 그 수를 semiperfect 하다고 한다. 우리의 만만한 12는 또 semiperfect 하는데, {1, 2, 3, 4, 6}에서 4만 빼버리고 {1, 2, 3, 6}의 합을 구하면 12로 원래 수와 같아진다.

만만한 12는 안타깝게도 abundant 하지만 semiperfect하기 때문에 이상한 숫자가 아니다. (새벽에 정신놓고 있으면 이거 나중에 헷갈린다)

1. 쉬운부분 (Abundant)

Abundant한지 아닌지를 알아보는건 사실 쉽다. 진 약수를 구하고, 다 더해서, 큰지 아닌지만 비교하면 되니까.

// 직관적으로 n 까지 for문을 돌리자. 횟수 반으로 줄일수는 있겠지만..
for(int i = 2; i < n; i++){
    if( n % i == 0 ){
        divisors.insert(i);
        divSum += i;
    }
}
 
// 첫번째 조건 검증. abundant?
if(divSum <= n){
    cout<<"not weird"<<endl;
    continue;
} 

나눠지면? 약수고 아니면? 약수가 아니겠지. divisors는 std::set 컨테이너를 사용한다.

2. 어려운 부분 (Semiperfect)

semiperfect 한지 아닌지를 알아보는 루틴은 꽤나 시간복잡도가 높은 작업이다. 왜냐? 일단 semiperfect하지 않은 숫자임을 밝혀야 하기 때문인데, 다시 말하자면 부분집합이 만들어질 수 있는 모든 경우의 수에서 원소의 총 합이 원래의 수를 만족하는 진 약수의 부분집합을 찾을수 없음을 보여야 하기 때문이고, 그리고 부분집합의 갯수는 원소의 갯수 (진 약수의 갯수)에 지수비례 하다는 것이다. 제일 큰 문제는 이 문제를 처음 풀때 이 생각을 안 하고 있었다는 것이다.

첫번째로 만든 루틴은 모든 부분 집합을 전부 검사하는 방식이었다. 따져보자면 부분 집합의 갯수인 2^n (n은 진 약수의 갯수) 만큼 루프를 돌아야 했고. 최악의 경우랑 비슷한 정도로 최악인 케이스 하나에서 아마 진 약수의 갯수가 40개 정도가 나온걸로 기억한다. 울프람 알파에 쳐보니 대충 1조 넘는 숫자가 나온다. 1억 루프를 1초라고 가정했을때 10995초 정도 걸린다는것이다. 그것도 최악이랑 비슷한 경우의 문제 하나만 푸는데에. 이런식으로 풀라고 만든 문제가 아니었다. 초장에 바로 시간초과 나왔으면 깨닫는 시간이 조금이나마 단축됐을지도 모르겠지만. 안타깝게도 주먹구구식 구현으로 초반에 오답이 나와버리는 바람에 '이 알고리즘은 완벽하지만 뭔가 문제가 있어서 계산 결과가 틀린것이다'라는 환상에 빠져 버리게 되었고, 가망없는 로직 수정에 시간을 꽤나 투자하고 말았다. (제대로만 구현했으면 completeness라도 만족했을텐데 말이다)

시간을 꽤나 쏟았지만 항상 오답을 내뱉는게 짜증나서 문제를 잊고 살다가, 어느날 군대에 있는 친구랑 통화도중에 이 문제가 언급되면서 다시 풀어보기로 했다. 두번째로 만든 루틴은 이 친구가 자기 나름대로 생각한 아이디어를 기반으로 구현했다. 아이디어는 이렇다. 만만한 12가 semiperfect 한지 아닌지 알아보기 위해서 우리는 진 약수의 합을 구한다. 16이다. 12가 semiperfect 하다는걸 보여주려면 16에서 약수의 일부분을 빼내서 12를 만들수 있음을 보이면 된다. 16에서 12가 되기 위해선 16-12 = 4. 4만큼을 빼야 한다. 4가 진 약수에 있으면? 바로 그 녀석만 빼버리면 semiperfect 함을 보일 수 있다. 몇가지 사칙 연산만으로 답을 구할 수 있는것이다. 만약에 4가 진 약수에 없다면? 진 약수 집합중에서 4보다 작은놈들의 부분 집합을 만들어서, 그 부분 집합에서 4가 나올 수 있는지 알아보면 될것이다. 4가 진 약수에 없지만 부분 집합중에서 4를 만들 수 있는 놈들이 존재한다? 그러면 그 친구들만 원래 집합에서 빼버리면 semiperfect 함을 보일 수 있는것이다. 게다가 전체적으로 봤을때 '어떤 집합의 부분집합의 합중에서 어떤 숫자를 만들 수 있느냐?' 에 대한 문제로 통일시켜 버릴 수 있으니 함수 하나만 만들어놓고 재귀로 돌리면 꽤나 적절한 시간 안에 답이 나올것 같았다. 그런 믿음을 기반으로 다음과 같은 코드를 작성했다. 

// 어떤 집합의 부분집합의 합이 어떤 자연수 n을 만들어 낼 수 있는가?

bool isSubsetSumMakesN(std::set<int>& aSet, int n){

	while(true){

		// 집합의 전체합 구함.
		int sum = 0;
		for(int e : aSet) {
			sum += e;
		}

		// 전체합이 n 보다도 작으면 의미 없음.
		if(sum < n){
			return false;
		}
		// 요소 하나만 빼서 되면? true.
		// 그 요소는 집합의 합에서 n을 뺀 숫자인데. 이것만 없으면 집합의 합은 바로 n이 된다.
		// 예를들어, {1,2,3,4,6} 집합에서 12를 만들어 내려면
		// 집합의 전체합인 16에서 원하는 숫자 12를 뺀 4를 바로 집합에서 지워버리면 되기 때문.
		int keyElement = (sum - n);
		if(aSet.find(keyElement) != aSet.end()) {
			return true;
		}

		// 안되면 그 '요소' 보다 크기가 작은 요소들로 이루어진 집합이
		// 다시 그 '요소'를 만들어 낼 수 있는지 검사
		set<int> subset;
		for(int e : aSet) {
			if(e <= keyElement){
				subset.insert(e);
			}
		}

		//cout<<"Set size " << aSet.size() <<endl;
		//cout<<"subset size " << subset.size() <<endl;
		//cout<<"N: "<<n<<" -> "<<keyElement<<endl;

		std::swap(aSet, subset);
		n = keyElement;
	}
}

알고스팟 페이지에 명시된 테스트 케이스뿐만 아니라 10000의 자릿수의 숫자들도 꽤나 빠르게 정답을 도출했기에 들뜬 마음으로 정답 제출을 했지만 결과는 시간초과였다.

두번째 방법은 검색해야할 부분 집합의 크기를 점점 줄여나간다. 줄여나가면서 결과적으로는 크기가 1인 부분 집합까지 내려가서 숫자를 만들 수 있는지를 판단한다. 문제는 검사할 숫자가 10만 단위 이상일 경우 부터는 부분 집합의 크기가 루프 한번에 1,2 개만 줄어들어도 다행이고 조금만 더 가면 아예 줄어들지도 않는다는것이다. 찾아야할 숫자의 크기는 작아졌지만 진 약수 집합은 거의 그대로라면? 500,000을 입력했더니만 처음 루프에서 집합 원소 41개중 하나만 탈락하고 그 다음 루프에서 250,000을 40개중에서 만족하는지 알아봐야 한다면? 문제의 크기를 크게 잘라 낼 수 없는 케이스가 존재 한다는 것을 나중에 깨달았다. 이렇게 두번째 방법도 시간초과로 끝.

마지막으로, 알고리즘 수업시간에 사용한 책을 목차만 그냥 읽다 보니 아예 "Chapter 5. Backtracking"의 하위 절로 "5.4 The Sum-of-Subsets Problem"이 아예 있더라. 필기한걸 대충 보니 시험공부 했었던게 기억이 났다. 'Branch-and-bound'기법 처럼 트리 순회할때 노드마다 무슨짓을 해도 정답에 도달할 수 없는 가망 없는 노드는 쳐내고 순회하면서 답이 나오는지 아닌지 따져보는 방법이었다. 

그림1. 상태 공간 트리 순회 (N = 13)

그림1처럼 집합의 각 원소 마다 더할것인지 말것인지에 대한 경우의 수를 하나의 노드로 생각하고, 가망없는 노드는 지워버리면서, 트리 순회를 할것이다. 이때 각 노드들은 어떤 원소를 더해서 어떤 값이 나왔는지를 나타낸다.

가망 있는 노드인지 없는 노드인지 생각해보는건 간단하다. 현재 노드에서의 합과 남아있는 원소중에 제일 작은 값을 더한게 찾고자 하는 숫자보다 크면 이 노드로부터 파생되는 모든 경우의 수는 전부 답을 찾을 수 없을 테니 제외한다. 또한 현재 노드에서의 합과 남아있는 원소들의 전체 합을 더했을때 찾고자 하는 숫자보다 작은 경우도 앞으로 절대 정답에 다가갈 수 없으니 제외한다.

// min은 남아있는 원소들중 가장 작은값, total은 남아있는 원소들의 합.
bool isPromising(int N, int min, int total){

	if( sum + min > N || sum + total < N )
		return false;

	return true;
}

부분집합의 상태공간트리를 순회하면서 집어넣을 노드마다 이 함수를 불러준다. 결과가 true면 집어넣고, false이면 그냥 날려버리면 된다.

// 어떤 집합의 부분집합의 합이 어떤 자연수 n을 만들어 낼 수 있는가?
bool isSubsetSumMakesNv2(std::set<int> universal, int N){

	// 트리의 노드를 나타낼 구조체.
	// 딱히 구조체 까지 안 만들어도 구현할 수 있지만 (멤버변수가 int 하나다)
	// 노드로 표현하는게 좀 더 직관적이라 만듬.

	struct Node{
		Node():sum(0){}

		void addElement(int element){
			sum += element;
		}
		bool isPromising(int N, int min, int total){

			if( sum + min > N || sum + total < N )
				return false;

			return true;
		}

		int sum;
	};

	// 상태공간 트리를 순회할때 사용할 컨테이너다. 
	// Stack을 쓰면 DFS, Queue는 BFS, Priority Queue를 쓰면 best-1st가 되겠지
	stack<node*> traverseContainer; 
	vector<int> setToVector(universal.rbegin(), universal.rend());

	{
		// 트리의 root 노드를 넣어준다.
		traverseContainer.push(new Node());
	}

	// 집합의 원소를 차례로 순회한다.
	for(int element : setToVector) {

		// 전체 집합에서 현재 원소를 빼면서 남아있는 원소들의 집합을 만든다.
		universal.erase(element);
		
		// 남아있는 원소들의 집합의 총합, 최소값.
		int universalTotal = SumofSet(universal);
		int universalMin = (universal.empty() ? 0 : *universal.begin());

		stack<node*> newQueue;

		while(traverseContainer.empty() == false) {

			Node* node1 = traverseContainer.top();
			traverseContainer.pop();
			Node* node2 = new Node(*node1);

			node1->addElement(element);

			//  답이 나왔으면? 
			if(node1->sum == N)
				return true;
			
			// 원소를 추가하는 경우의 수
			if(node1->isPromising(N, universalMin, universalTotal)){
				newQueue.push(node1);
			}else{
				delete node1;
			}

			// 추가 하지 않는 경우의 수
			if(node2->isPromising(N, universalMin, universalTotal)){
				newQueue.push(node2);
			}else{
				delete node2;
			}

		}

		// 그냥 = 연산자 보다 이게 훨씬 빠르다
		std::swap(traverseContainer, newQueue);
	}

	return false;
}

이런식으로 구현했다. 오래도 걸렸다. 저기서 좀 더 최적화 시킬 여지는 많지만 일단은 풀었으니 여기까지. 전체 코드는 gist에