[PS] 순열과 조합 구현하기

📌 순열과 조합

---

순열은 주어진 원소들의 순서에 따라 결과가 달라지는 특정한 배열의 형태를 말한다.

{ 1 , 2 , 3 } != { 1 , 3 , 2 }

조합은 주어진 원소들의 순서와 상관없는 배열의 형태를 말한다.

{ 1 , 2 , 3 } == { 1 , 3 , 2 }

순열과 조합은 수학에서 기본적인 개념이기 때문에 자세하게 설명하지 않고 진행합니다.

📌 조합 구현

---

c++ 에서 제공하는 STL 에서 permutation 을 이용하여 순열과 조합을 구현할 수 있지만, 재귀를 이용하여 구현하는 방법에 대해서 알아보도록 하겠습니다.

void dfs(int idx, int cnt)
{
	if (cnt == k)
	{
		printCombination();
        return;
	}
	else
	{
		for (int i = idx; i < 26; i++)
		{
			if (alpha[i] == true)continue;
			alpha[i] = true;
			dfs(i, cnt + 1);
			alpha[i] = false;
		}
	}
}

📌 순열 구현

---

vector<int> v;

void dfs(int idx, int cnt)
{
	if (cnt == k)
	{
		printPermutation();
        return;
	}
	else
	{
		for (int i = idx; i < 26; i++)
		{
			if (alpha[i] == true)continue;
			alpha[i] = true;
            v.push(arr[i]);
			dfs(i, cnt + 1);
            v.pop_back();
			alpha[i] = false;
		}
	}
}

📌 마무리

---

순열과 조합을 STL 없이 구현하는 방법에 대해 알아보았습니다. 구현 방식 자체는 비슷하지만, 순서를 체크할 것 인지 아닌 지에 따라 약간의 차이가 있습니다. 알고리즘 문제에서 등장할 수 있는 개념이기 때문에 알아두면 좋습니다. 🔥