(4장-1) 순열(Permutation)알고리즘이란?

순열(Permutation)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. n개의 원소의 순서를 뒤섞는 순열의 개수는 n의 계승 n!와 같다.

 

 

안녕하세요. 지칸입니다.

 

오늘 설명할 알고리즘은 순열입니다.

삼성 SW역량테스트에서 자주 사용되는 알고리즘 중 하나로 "n개의 후보를 어떤 순서로 배치할 때 효율이 좋은가" 같은 문제 등에 쓰입니다. 전체 후보를 전부 사용하며 순서가 중요하다는 걸 잊으면 안 됩니다.

 

1) 순열이란?

2) 구현하기

3) STL 순열

 

저의 결론) STL을 적극활용하자. 

---

1) 순열이란?

예를 들어보면 {1,2,3} 집합이 있을 때 나열할 수 있는 모든 경우의 수는 6개입니다.

• {1,2,3}
• {1,3,2}
• {2,1,3}
• {2,3,1}
• {3,1,2}
• {3,2,1}

문제에서는 총개수보다는 가능한 경우를 나열하는 게 필요할 때가 있습니다. 

---

2) 구현하기

아래 코드에서는 재귀 함수를 사용하여 순열을 구현하고 있습니다.

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

vector<int> swap(vector<int> arr, int a, int b) {
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
	return arr;
}

void print(vector<int> arr) {
	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}

void perm(vector<int> arr, int depth, int n, int k) {
	if (depth == k) {
		print(arr); 
        // 순열을 통해 무엇을 하려고 하는지에 따라 달라지는 부분, 여기에 원하는 함수 입력
		return;
	}
	for (int i = depth; i < n; i++) {
		arr=swap(arr, i, depth);
		perm(arr, depth + 1, n, k);
		arr=swap(arr, i, depth);
	}
}

int main() {
	vector<int> arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	
	perm(arr, 0, 3, 3);
	return 0;
}

arr 배열에 후보들이 들어가고 swap 함수를 사용하여 배열 내의 순서를 섞어주는 방식입니다. 앞전에 배웠던 DFS방식처럼 한쪽으로 쭉 탐색 후 다음 스테이지로 넘어가는 방식입니다. 되돌아 가는 과정이 있기 때문에 perm 함수 뒤로 swap 함수가 존재합니다. 바꾸고자 하는 배열의 인덱스를 잘 따라가 보시기 바랍니다.

순열 순서

print함수가 위치하는 부분이 하나의 배열 순이 완성될 때 도달하는 곳이기 때문에 어떤 원하는 행동의 함수를 삽입해주시면 됩니다. 저는 단순 프린트 함수를 넣어서 나열되는 모든 경우의 수를 확인할 수 있었습니다.

---

3) STL 순열

재귀 함수라는 걸 사용하면 직관적으로 이해하기가 어려울 것으로 생각됩니다. 만약 c++를 사용하고 계시다면 걱정 마세요. 우리는 STL 라이브러리를 사용하여 정말 손쉽게 사용할 수 있습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void print(vector<int> arr) {
	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}
void main() {
	vector<int> arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	
	print(arr);
	while (next_permutation(arr.begin(),arr.end())) {
		print(arr);
	}
	return;
}

똑같은 예제로 {1,2,3} 배열이 있을 때 동일한 결과를 출력한다는 걸 알 수 있습니다.

algorithm 라이브러리를 추가하여 next_permutation(배열 첫 번째 인자, 배열 마지막 인자)를 사용하면 내부에서 순서를 직접 배열에 접근하여 바꾸고 true를 리턴합니다. 더 이상 경우의 수가 없다면 false를 리턴하여 while문을 종료하게 됩니다.

while문 내부에서 어떤 동작을 하고 싶은지 작성하면 됩니다.

 

맨 처음 프린트하는 동작이 깨끗하지 않으니 do~while문을 사용할 수 있겠네요.