중복 없는 수열 만드는 알고리즘 ( C++로 만드는 숫자 야구 게임 )

이번 글은 지난번 숫자 야구 게임 만들기에서 이야기했던 중복 없는 수열 만드는 알고리즘입니다. 

2021.03.29 - [Program Language and Algorithm] - C++로 만드는 숫자 야구 게임 : 문제를 내는 알고리즘

C++로 만드는 숫자 야구 게임 : 문제를 내는 알고리즘

2021.03.30 - [Program Language and Algorithm] - C++로 만드는 숫자 야구 게임 : 문제를 푸는 알고리듬

C++로 만드는 숫자 야구 게임 : 문제를 푸는 알고리듬

 문제를 푸는 알고리듬을 만들때 답안이 될 수 있는 모든 수열을 만들고, 추론 결과와 대치되는 조합들을 삭제해서 문제를 푸는 알고리듬을 제안했었습니다. ( 여담으로 똑같은 코드포스 문제를 못 풀었었다는 슬픈 전설...ㅜ,.ㅜ ) 이때 이전글에서는 중복 반복문을 이용했고, 그 결과 3해 혹은 4개의 숫자 조합만 만들 수 있었죠.

 

For Loop

 이 글에서는 중복 없이 0-9의 숫자들을 n개 만큼 뽑은 수열을 만드는 알고리듬입니다. 먼저 이전 코드의 알고리듬을 살펴보겠습니다.

void makeCand(vector<vector<int>> &cand, int dL){
    for(int i = 0 ; 10 > i ; i++){
	for(int j = 0 ; 10 > j ; j++){
	    if(i == j){
		continue;
	    }
	    for(int k = 0 ; 10 > k ; k++){
		if(i == k || j == k){
		    continue;
		}
		if(3 == dL){
		    cand.push_back(vector<int>{i,j,k});
		}else{
		    for(int l = 0 ; 10 > l ; l++){
			if(i == l || j == l || k == l){
			    continue;
			}
			cand.push_back(vector<int>{i,j,k,l});
		    }
		    
		}
	    }
	}
    }
}

 간단한 구조입니다. 원하는 숫자의 개수(3 or 4)만큼 for문을 중첩시켜 중복을 검사하고, 수열을 업데이트합니다. 조금 더 보완하자면 push_back을 쓰는 대신 함수의 도입부에서 resize를 해주고, push_back 대신 cand[idx]를 사용하는 게 좋습니다. 이유는 vector는 push_back이 발생했을 때 확보한 메모리가 부족하면, 추가 메모리를 요구하며, 불필요한 리소스가 소모됩니다. 그러니 사전에 계산이 가능하다면, 미리 사용할 크기에 맞게 resize 해주는 것이 좋습니다.

 

큐

 다음 알고리듬은 자료구조가 추가됩니다. 여러 자료 구조들 중 쉬운 구조 중 하나인 queue입니다. 큐의 특성은 선입선출( First input First output, FIFO)입니다. 먼저 들어온 원소가 먼저 나가는 구조죠. 간단하게 생각하시면 식당에 줄 선 사람들을 생각하시면 됩니다. 각각의 사람은 큐의 원소입니다. 당연히 자리가 생기면 먼저 와서 줄을 선 사람이 먼저 식당에 들어가겠죠. 아래 그림을 통해 자세히 설명드리겠습니다.  

 편의상 오른쪽이 식당 입구이고, 오른쪽에 서있는 사람이 먼저 온 사람이며, 가장 늦게 온 사람은 왼쪽에 서게 됩니다. 처음엔 4명이 서있었는데 한 명이 추가됩니다.( push) 사람은 다섯이 되고, 새로운 사람은 왼쪽에 서죠. 그후 자리가 생겨서 가장 먼저온 사람이 식당에 들어 갑니다. (pop) 이 경우 오른쪽에 서있던 사람이 줄에서 빠져나갔습니다.  그 후 두사람이 줄에 추가 됩니다. ( push x2) 규칙에 맞춰 왼쪽에 서겠죠. 자리가 3자리가 남았네요. 세 사람이 줄에서 빠져 나갔습니다. (pop x3) 마지막으로 식당에 들어갔던 분(노란색)이 다시 드시고 싶으신가 바요. 다시 줄을 서서 왼쪽에 추가되었습니다. (push)

 

큐의 활용

 이런 방식으로 자료를 처리하는 자료 구조가 큐입니다. 그럼 중복 없는 수열을 만들 때는 어떻게 할까요? 제가 사용한 방식은 queue에 들어간 원소들을 각 위치 별로 하나씩 빼서 사용하는 구조입니다. 예제 코드를 통해 설명하죠.

void makeCand(vector<vector<int>> &cand, int dL){
    queue<int> iCand;

    for(int i = 0 ; 10 > i ; i++){
	iCand.push(i);
    }
    int candSize = 1;

    for(int i = 0 ; dL > i ; i++){
	candSize *= (10 - i);
    }

    cand.resize(candSize);

    int idx = 0;

    for(int i = 0 ; iCand.size() > i ; i++){
	int f = iCand.front();
	iCand.pop();

	for(int j = 0 ; iCand.size() > j ; j++){
	    int s = iCand.front();
	    iCand.pop();

	    for(int k = 0 ; iCand.size() > k ; k++){
		int t = iCand.front();
		iCand.pop();

		if(3 == dL){
		    cand[idx++] = vector<int>{f,s,t};
		}else{
		    for(int l = 0 ; iCand.size() > l ; l++){
			int fo = iCand.front();
			iCand.pop();

			cand[idx++] = vector<int>{f,s,t,fo};

			iCand.push(fo);
		    }
		}
		iCand.push(t);
	    }
	    iCand.push(s);
	}
	iCand.push(f);
    }
}

 먼저 사용할 큐를 만들어 줍니다. 큐에는 0-9까지의 숫자들을 채워줍니다. 처음 예제에서 지적한 vector의 push_back 함수 사용에 대한 리소스 소모를 줄이기 위해 먼저 필요한 용량을 계산해서 크기를 지정해 줍니다. 그 후 중복 for문에서 큐의 원소를 하나씩 빼면서 계산합니다.

 dL이 3이라고 가정할 때, 처음 구동 시 f = 0, s = 1 가되어 k루프에 도달합니다. 이때 큐에는 2-9까지의 원소가 들어 있죠. 큐는 선입선출 구조이니 처음 루프에서 t = 2가 되었다가 루프가 끝날 때 큐에는 3-9 이후에 2가 들어가게 됩니다. ( 위 큐 설명에서 마지막 손님 같이 구동함. ) 그다음 루프에서 t 는 3이 되겠죠. 이런식으로 9까지 돌고 나면, 큐는 2-9로 정렬 되어 k루프가 완전히 끝나게 됩니다. 그럼 j 루프의 iCand.push(s) 로 인해 큐는 2-9 다음에 1이 들어 간 상태로 끝나죠. 그 후 다음 j루프가 되어 s는 2가 되고, 큐는 3-9 다음에 1이 들어간 상태로 k루프에 들어 가게 됩니다. 이 순회가 모두 끝나면 자연스럽게 모든 경우의 수가 들어간 수열이 만들어지는 것이죠.

 

큐 방식의 재귀 호출

 그런데 코드상으로 볼 때 처음 코드보다 복잡해 지기만 했을 뿐 더 나은 구조라고 하긴 힘듭니다. 또한 여전히 4 이상의 dL에는 적용할 수 없습니다. 엉터리 같죠. 여기서 추가로 소프트웨어 엔지니어링 기술로 재귀 호출을 적용합니다. (처음 코드에도 적용 가능함.)

void makeCandQueue(vector<vector<int>> &cand, queue<int> &iCand, vector<int> &cCand, int idx, int dL){
    if(idx == dL){
	cand.push_back(cCand);
	return;
    }

    for(int i = 0 ; iCand.size() > i ; i++){
	cCand[idx] = iCand.front();
	iCand.pop();

	makeCandQueue(cand, iCand, cCand, idx+1, dL);

	iCand.push(cCand[idx]);
    }
}
void makeCand(vector<vector<int>> &cand, int dL){
    queue<int> iCand;
    vector<int> cCand(dL, 0);

    for(int i = 0 ; 10 > i ; i++){
	iCand.push(i);
    }

    makeCandQueue(cand, iCand, cCand, 0, dL);
}

 반복되는 for 루프를 재귀 호출로 변환하면 이렇게 가독성이 크게 상승합니다. 함수는 전체 수열 cand와 이용 중인 큐 iCand, 작성 중인 수열 cCand, cCand의 idx 그리고 dL을 넘겨받습니다. idx가 dL과 같으면 수열을 추가하고 종료하며, 다르면 큐의 원소를 순회하며, 함수를 호출합니다.

 

For loop의 재귀 호출

 이런 방식의 개선은 처음 코드에도 가능합니다. 단 처음 코드의 중복 검사 문을 위한 for 루프가 추가됩니다. 아래 코드와 같죠.

void makeCandForLoop(vector<vector<int>> &cand, vector<int> &cCand, int idx, int dL){
    if(idx == dL){
	cand.push_back(cCand);
	return;
    }

    for(int i = 0 ; 10 > i ; i++){
	bool flag = true;
	for(int j = 0 ; idx > j ; j++){
	    if(i == cCand[j]){
		flag = false;
		break;;
	    }
	}
	if(flag){
	    cCand[idx] = i;

	    makeCandForLoop(cand, cCand, idx+1, dL);
	}
    }

}

void makeCand(vector<vector<int>> &cand, int dL){
    vector<int> cCand(dL, 0);

    makeCandForLoop(cand, cCand, 0, dL);
}

 깊이 우선 탐색

 다음으로 알고리듬 콘테스트에 많이 참여한 사람들이 연상할만한 코드를 작성했습니다. 깊이 우선 탐색(depth-first search, DFS)을 이용한 알고리듬입니다. 향후 깊이 우선 탐색을 다룬 글을 쓰게 될 수도 있겠네요. 일단 코드를 보시죠.

void makeCandDFS( vector<vector<int>> &cand, vector<int> &iCand, vector<bool> &visited, int idx, int dL){
    if(idx == dL){
	cand.push_back(iCand);
	return;
    }

    for(int i = 0 ; 10 > i ; i++){
	if(visited[i]){
	    visited[i] = false;

	    iCand[idx] = i;
	    makeCandDFS( cand, iCand, visited, idx+1, dL);

	    visited[i] = true;
	}
    }

}

void makeCand(vector<vector<int>> &cand, int dL){
    vector<bool> visited(10, true);
    vector<int> cCand(dL, 0);

    makeCandDFS(cand, cCand, visited, 0, dL);
}

 만들고 보니 깊이 우선 탐색의 구조에 맞추긴 했으나, 위 코드에서 원소의 사용 여부를 메모이제이션 한 효과 정도입니다. 실제로 깊이 우선 탐색의 이점을 논하려면 더 복잡한 구조가 필요하겠네요. 아무래도 이 설명은 나중으로 미루겠습니다.

 

표준 함수 활용

 마지막으로 하나만 더 추가하였습니다. 사실 전 글을 쓰기 전에 모든 코드를 8-90 프로 만들어서 테스트해보고 작성 중에 조금씩 수정하지만. 이번 코드는 갑자기 이렇게 하면 어떨까 해서 만들어 본 코드입니다. 그래서 가독성이 별로 안 좋습니다.

void makeCandPerm(vector<vector<int>> &cand, vector<int> &cCand, int idx, int dL){
    if(idx == dL){
	do{
	    cand.push_back(cCand);
	}while(next_permutation(cCand.begin(), cCand.end()));
	return;
    }

    for(int i = cCand[idx-1]+1 ; (10-dL+idx) >= i ; i++){
	cCand[idx] = i;

	makeCandPerm(cand, cCand, idx+1, dL);
    }
}
void makeCand(vector<vector<int>> &cand, int dL){
    vector<int> cCand(dL, 0);

    for(int i = 0 ; 11 - dL > i ; i++){
	cCand[0] = i;
	makeCandPerm(cand, cCand, 1, dL);
    }
}

 c++의 제공 함수 중에는 next_permutation 함수가 있습니다.  이 함수는 입력으로 사용된 수열을 각각의 조합으로 만들어 출력하는 함수입니다. 그러니, 0, 1, 2를 입력으로 넣으면, 만들수 있는 조합 6가지를 순회 하고, 0, 0, 1을 넣으면 3가지를 순회 하는 함수 입니다.  (알고리듬 경진대회에서 많이 사용됩니다.)

 위 코드에서는 next_permuation 함수를 사용해 보았습니다. 0, 1, 2부터 7,8,9까지(dL이 3일 때) 순차적으로 조합을 만들고 next_permutation을 이용해 수열을 완성합니다. (더 깔끔하게 만들고 싶었으나, 즉흥적인 코드가 머 다 그렇죠 머...)

 사실 다른 코드들과 비교했을 때 딱히 좋은 코드라고 하긴 어렵습니다. 그냥 생각나서 해본 거니 이해 부탁드릴게요.

 

그럼 이상으로 마치겠습니다. 감사합니다.