반응형
permutation: 크기가 제한된 부분 순열을 구하는 함수.
backtrack: 전체 원소를 포함하는 순열을 구하는 함수.
- 동작의 범위 차이:
- permutation: 고정된 크기의 조합만 포함.
- backtrack: 배열의 모든 순열을 포함.
- 사용 상황:
- permutation: 특정 크기의 부분 조합을 구해야 할 때 사용.
- backtrack: 전체 순열을 구하거나 탐색이 필요한 경우 사용.
비교표
함수 | 시간복잡도 | 공간복잡도 | 목적 |
permutation | O(n²) | O(n²) | 크기가 제한된 순열 (예: 2개) |
backtrack | O(n * n!) | O(n * n!) | 전체 순열 (길이 n) |
- 순열 생성 범위:
- permutation은 특정 크기의 순열(여기서는 2개)을 제한적으로 생성하기 때문에, 시간복잡도와 공간복잡도가 비교적 낮습니다.
- backtrack은 전체 순열을 생성하므로, 시간이 오래 걸리고 더 많은 메모리를 사용합니다.
- 시간복잡도:
- permutation은 크기가 제한되므로 탐색 범위가 좁아 시간복잡도가 **O(n²)**로 낮습니다.
- backtrack은 모든 경우를 탐색하므로 시간복잡도가 **O(n * n!)**로 높습니다.
- 공간복잡도:
- 두 함수 모두 새로운 배열을 생성하며, 호출 스택 깊이가 재귀 호출 횟수에 따라 달라집니다.
- backtrack은 더 많은 경우를 탐색하기 때문에 더 많은 메모리를 사용합니다.
핵심 차이점
1. permutation 함수의 의도
- 이 함수는 특정 크기의 순열을 구하는 데 목적이 있습니다.
- selected.length === 2 조건은 명시적으로 선택된 원소가 2개일 때만 결과에 추가하도록 제한을 두고 있습니다.
- 따라서 배열의 모든 가능한 경우를 탐색하더라도, 결과에는 크기가 2인 순열만 포함됩니다.
2. backtrack 함수의 의도
- 이 함수는 **전체 순열(모든 원소를 포함하는 순열)**을 구하는 데 목적이 있습니다.
- remaining.length === 1 조건을 사용하여 모든 원소가 선택된 경우를 처리합니다.
- 이 함수는 남은 원소가 모두 선택될 때까지 탐색하며, 최종적으로 크기가 arr.length인 순열들을 생성합니다.
코드 비교
permutation 함수
function permutation(arr, selected, result) {
if (selected.length === 2) { // 크기 2인 순열만 구함
result.push([...selected]);
return;
}
for (let i = 0; i < arr.length; i++) {
selected.push(arr[i]);
permutation(arr.slice(0, i).concat(arr.slice(i + 1)), selected, result);
selected.pop();
}
}
예시:
입력: arr = ['A', 'B', 'C']
- 결과: [['A', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'C'], ['C', 'A'], ['C', 'B']]
설명
- 이 함수는 2개를 선택한 뒤에야 결과에 추가합니다(selected.length === 2).
- 모든 가능한 경우를 탐색하지만, 최종 결과는 크기가 고정된 순열만 포함합니다.
backtrack 함수
function backtrack(path, remaining, result) {
if (remaining.length === 1) { // 전체 순열을 구함
result.push([...path]);
return;
}
for (let i = 0; i < remaining.length; i++) {
const newPath = [...path, remaining[i]];
const newRemaining = remaining.slice(0, i).concat(remaining.slice(i + 1));
backtrack(newPath, newRemaining, result);
}
}
예시:
입력: arr = ['A', 'B', 'C']
- 결과: [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A'], ['C', 'A', 'B'], ['C', 'B', 'A']]
설명
- 이 함수는 모든 원소를 포함하는 순열을 구합니다.
- 결과에는 배열의 모든 가능한 순열이 포함됩니다.
결론
- 제약된 순열을 구하려면 permutation이 적합하며, 효율적입니다.
- 전체 순열을 구하려면 backtrack을 사용하는 것이 적합합니다.
- 두 함수 모두 입력 배열의 크기가 커질수록 성능에 영향을 받으므로, 크기가 큰 입력에서는 최적화된 알고리즘이나 데이터 구조를 사용하는 것이 필요합니다.
반응형
'Algorithm' 카테고리의 다른 글
[algorithm 공부] DFS/BFS 쉬운 개념 js 구현 방법 (0) | 2025.01.06 |
---|---|
알고리즘 문제에서 자주 쓰이는 Math 함수 완벽 정리 (0) | 2024.11.27 |
JS Array prototype 함수의 시간 복잡도 비교(indexOf, concat ...) (0) | 2024.11.23 |
[알고리즘] 경우의 수(순열 / 조합) JS (0) | 2024.11.22 |