알고리즘 노트 연습 문제 모음집

제목

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

생각

코드

반복 버전

#include 
#include 
using namespace std;
int n;
vector<int> ans(11);
vector<bool> hashTable(11, false);
void DFS(int index) {
	if (index > n) {
		for (int i = 1; i <= n; ++i) {
			if (i != 1)
				putchar(' ');
			printf("%d", ans[i]);
		}
		putchar('
'); 
		return;
	}
	for (int i = 1; i <= n; ++i) {
		if (hashTable[i] == false) {
			ans[index] = i;
			hashTable[i] = true;
			DFS(index + 1);
			hashTable[i] = false;
		}
	}
} 
int main() {
	while(scanf("%d", &n) != EOF)
		DFS(1);
	return 0;
} 

교체 버전

#include 
#include 
#include 
using namespace std;
bool myNextPermutation(vector<int>& nums) {
	int pivot, pos;
	for (pivot = nums.size() - 1; pivot > 0 && nums[pivot - 1] >= nums[pivot]; --pivot)
		continue;
	if (pivot == 0)
		return false;
	--pivot;
	for (pos = pivot; pos < nums.size() - 1 && nums[pos + 1] >= nums[pivot]; ++pos)
		continue;
	swap(nums[pivot], nums[pos]); 
	reverse(nums.begin() + pivot + 1, nums.end());
	return true; 
} 
int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		vector<int> nums(n);
		for (int i = 1; i <= n; ++i)
			nums[i - 1] = i;
		do {
			for (int i = 0; i < n; ++i) {
				if (i > 0)
					putchar(' ');
				printf("%d", nums[i]); 
			}
			putchar('
'); 
		} while (myNextPermutation(nums)); 
	}
	return 0;
} 

라이브러리 함수next_permutation 버전

#include 
#include 
#include 
using namespace std;
int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		vector<int> nums(n);
		for (int i = 1; i <= n; ++i)
			nums[i - 1] = i;
		do {
			for (int i = 0; i < n; ++i) {
				if (i > 0)
					putchar(' ');
				printf("%d", nums[i]); 
			}
			putchar('
'); 
		} while (next_permutation(nums.begin(), nums.end())); 
	}
	return 0;
}