조합, 순열 알고리즘

1차 카테고리

알고리즘

2차 카테고리

combination

permutation

생성 일시

2025/01/06 01:53

최종 편집 일시

2025/01/08 06:27

발행여부

published

순열과 조합

•

순열(Permutation)

◦

nnn개의 원소 중에서 rrr개의 원소들을 나열하는 경우의 수

◦

공식으로 나타내면 nPr_nP_rn​Pr​로 나타낸다.

▪

nPr=n⋅(n−1) ⋯ (n−r+1)_nP_r = n \cdot (n-1) \ \cdots \ (n-r+1)n​Pr​=n⋅(n−1) ⋯ (n−r+1)

•

조합(Combination)

◦

nnn개의 원소 중에서 rrr개의 원소들을 고르는 경우의 수

◦

공식으로 나타내면 nCr_nC_rn​Cr​로 나타낸다.

▪

nCr=nPrr!=n⋅(n−1) ⋯ (n−r+1)r!_nC_r = \frac{_nP_r}{r!} = \frac{n \cdot (n-1) \ \cdots \ (n-r+1)}{r!}n​Cr​=r!n​Pr​​=r!n⋅(n−1) ⋯ (n−r+1)​

BOJ_10974_모든 순열_JS

function solution(input) {
	const check = Array(input + 1).fill(false);
	const result = [];
	const arr = [];

	function permutation(level) {
		if (level === input) {
			result.push(arr.join(' '));
		}

		for (let i = 1; i <= input; i += 1) {
			if (check[i] === true) {
				continue;
			}
			arr.push(i);
			check[i] = true;
			permutation(level + 1);
			arr.pop();
			check[i] = false;
		}
	}

	permutation(0);

	return result.join('\n');
}
JavaScript
복사

•

나열하는 것에 중점을 둔다. 따라서 방문한 노드를 제외하고 배열의 처음부터 탐색한다. 

•

따라서 for문의 i가 1부터 시작.

BOJ_6603_로또_JS(조합)

function solution(input) {
	const result = [];
	input.forEach((element) => {
		const [k, ...s] = element.split(' ').map(Number);

		const arr = [];

		const combination = (index, level) => {
			if (level === 6) {
				result.push(arr.join(' '));
				return;
			} else {
				for (let i = index; i < k; i += 1) {
					arr.push(s[i]);
					combination(i + 1, level + 1);
					arr.pop();
				}
			}
		};

		combination(0, 0);
		result.push('');
	});

	return result.join('\n');
}
JavaScript
복사

•

뽑는 것에 중점을 둔다. 따라서 for문의 i가 전달받은 배열의 다음 index 값으로 시작한다.