프론트 개발자를 위한 여정

모든 영역을 안내하는 개발자

Algorithm

[알고리즘] 순열과 백트래킹 비교(permutation, backtracking) / 부분 수율 / 전체 순열

ji-frontdev 2024. 11. 24. 01:27
반응형

 

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을 사용하는 것이 적합합니다.
  • 두 함수 모두 입력 배열의 크기가 커질수록 성능에 영향을 받으므로, 크기가 큰 입력에서는 최적화된 알고리즘이나 데이터 구조를 사용하는 것이 필요합니다.
반응형