알고리즘을 학습하다가 순열, 조합, 부분집합이 비슷한 로직을 가지고 있으며 헷갈릴 수 있겠다는 생각이 들었다.
아직 다양한 문제유형은 풀지못했지만, 현재 학습한 범위까지 한번 정리를 하고자한다.
순열
1. 기본순열
순열이란?
: 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 말한다.
중요❗️
: 순서가 있음, 중복이 불가능
순열문제에서 중요한 것은 중복이 불가능하며 순서가 있다는 것이다.
순열문제는 DFS으로 작성한다.
-
재귀의 설정
순열 문제에서 각 재귀함수는 선택가능한 원소들을 하나씩 선택해 저장하고 다음 레벨의 재귀를 호출하는 방식으로 진행된다.
순열은 순서가 존재하므로 [a,b]와[b,a] 는 다른 경우로 인정된다.
그러므로 레벨의 시작에서 a로 시작하는 경우, b로 시작하는 경우 등 모든 경우의 수가 고려되어야 한다, 즉, for문을 돌려 모든 원소들을 한번씩 재귀호출해야한다. -
중복의 제거
순열에서 중요한것은 중복이 불가능하다는 것이다. 이미 이전 스택에 쌓여있는 재귀에서 사용한 원소는 사용하지 못하도록 해야한다.
이를 위해 임시 체크용 배열을 생성하여 이미 쌓여있는 스택에서 사용한 원소는 경우의수에서 제하도록한다(= 반복문에서 제외한다.) -
종료 조건
r개의 데이터를 선택할때 종료조건은 L과 r이 같아지는 순간이다.예시코드로 작성하면 다음과 같다.
문제 : [2,5,7]에서 2개를 일렬로 중복없이 뽑는 모든 경우를 나열하라.
순열
function main(m, arr) {
let answer = [];
let tmpAnswer = Array.from({ length: m }, () => 0);
let checkArr = Array.from({ length: arr.length }, () => false);
function permutation(D) {
if (D === m) {
answer.push(tmpAnswer.slice(0));
} else {
for (let i = 0; i < arr.length; i++) {
if (!checkArr[i]) {
tmpAnswer[D] = arr[i];
checkArr[i] = true;
permutation(D + 1);
checkArr[i] = false;
}
}
}
}
permutation(0);
return answer;
}
main(2, [2,5,7])
2. 중복 순열
중복순열이란?
: 서로 다른 n개의 원소에서 r개를 중복하여 선택 후 나열하는 것을 말한다.
중요❗️
: 순서가 있음, 중복이 가능
중복 순열문제와 일반 순열문제가 다른점은 중복이 가능하다는 것이다.
중복 순열문제는 일반순열문제에서 중복을 체크하는 로직만 제거하면 동일하다.
예시코드로 작성하면 다음과 같다.
문제 : [2,5,7]에서 2개를 일렬로 중복없이 뽑는 모든 경우를 나열하라.
function main(m, arr) {
let answer = [];
let tmpAnswer = Array.from({ length: m }, () => 0);
function permutation(D) {
if (D === m) {
answer.push(tmpAnswer.slice(0));
} else {
for (let i = 0; i < arr.length; i++) {
tmpAnswer[D] = arr[i];
permutation(D + 1);
}
}
}
permutation(0);
return answer;
}
console.log(main(2, [2, 5, 7]));
부분집합
부분집합이란?
어떠한 집합에 포함되는 원소들을 부분적으로 조합한 집합을 말한다.
중요❗️
: 순서가 구분되지않음. 중복이 불가능 , 선택하는 경우 선택하지 않는경우 2가지로 구분, 공집합이 포함됨
일반적으로 여러개의 원소가 주어지고, 갯수와 상관없이 최적의 원소만을 선택하라는 문제는 부분집합의 문제로 볼 수 있다. 예를들어 쪼갤 수 없는 동전문제라든가, 가방문제 모두 각각의 원소들을 포함할것인지, 안할것인지 결정하여 최적의 결과를 얻는 문제이므로 부분집합 문제라고 볼 수 있다.
부분집합 알고리즘은 일반적으로 이진트리로 나타낼 수 있다.
순서가 고려되지않으므로 첫번째 원소를 루트원소로 하여 각 원소를 선택하는 경우, 선택하지않는 경우의 자식노드로 뻗어가며 이진트리를 그린 후 조건에 따라 결정된 리프노드에 도달한다면 리프당 하나의 부분집합을 구할 수 있다.
부분집합이 조합과 다른점은 선택할 원소의 갯수가 지정되어져 있지 않다는 것이다. 조건에 따라 1개를 선택할수도, 100개가 선택될수도 있다. 일정 조건이 먼저 만족되지않는한(ex -원하는 조건을 만족하는 부분집합을 발견) 모든 부분집합을 구할때 까지 재귀를 진행한다.
예시코드로 작성하면 다음과 같다.
문제 : [2,5,7]의 부분집합을 구하라
function main(arr) {
let answer = [];
let n = arr.length;
let tmpArr = Array.from({ length: n }, () => false);
function subSet(D) {
if (D === n) {
let str = "";
for (let i = 0; i < arr.length; i++) {
if (tmpArr[i]) str += arr[i];
}
answer.push(str);
} else {
tmpArr[D] = true;
subSet(D + 1);
tmpArr[D] = false;
subSet(D + 1);
}
}
subSet(0);
return answer;
}
console.log(main([2, 5, 7]));조합
조합이란?
서로 다른 n개의 원소를 가지는 어떤 집합 에서 순서에 상관없이 r개의 원소를 선택하는 것이며, 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것 혹은 찾는 것과 같다.
중요❗️
: 순서가 구분되지않음. 중복이 불가능 , r개를 선택.
일반적으로 조합은 순열에서 순서를 고려하지 생각하면 쉽게 풀이가 가능하다.
만약 n개 원소중 r개를 뽑을때, 순서를 고려한다면 첫번째 원소가 첫번째 자리에 오는 경우를 모두 구한뒤 다시 두번째원소가 첫번째 자리에 오는 경우를 n-1개의 남은 원소들을 이용해 구해야한다.
반면 조합은 k번째 원소를 하나 뽑은 경우의 수를 구한다면 다시 1번째 원소를 뽑는 경우는 고려할 필요가 없다. 즉, 다음 차수부터는 k+1번째 원소만을 고려하면 된다. 결국 차수가 증가할수록 뽑을 수 있는 원소들도 한개씩 감소한다.
트리 형태로 생각한다면
- 레벨0에서 k번째 원소를 선택한다.
- 레벨1에서 k+1 부터 n까지 원소를 하나 선택한다.
- 레벨2에서 k+2부터n까지 원소를 하나 선택한다.
- 이러한 과정을 레벨이 r이 될때까지 반복한다.
- 레벨이 r이 된다면 r개의 원소를 가진 부분집합이 하나 생성된다.
- 다시 바로 이전 레벨로 돌아가 이전에 선택한 원소보다 인덱스가 큰 원소를 선택한다. 만약 전 레벨의 노드가 한번씩 선택되었다면 전전레벨로 돌아간다. 다시 레벨이 r이 될때까지 진행한다. 이러한 과정을 반복하면 모든 원소들이 중복되지않는 r개의 원소를 갖는 부분집합 형성이가능하다.
function main(n, m) {
let answer = [];
let tempAnswer = Array.from({ length: m }, () => 0);
function combination(D, k) {
if (D === m) {
answer.push(tempAnswer.join(" "));
} else {
for (let i = k; i <= n; i++) {
tempAnswer[D] = i;
combination(D + 1, i + 1);
}
}
}
combination(0, 1);
return answer;
}
console.log(main(4, 2)); 출처 :
[순열-나무위키]
[조합-나무위키 ]
