Published on

순열 알고리즘

Authors
  • avatar
    Name
    piano cat
    Twitter

순열 언제 사용될까

순열은 n개의 개수가 주어지고 완전 탐색하여 모든 경우의 수를 계산하는 방법이다. O(n!)의 시간복잡도 소모

풀이는 백트래킹과 DFS를 활용하여 풀이한다.

예제

입력 [a,b,c]

출력 [[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]]

모든 경우의 수를 트리구조로 나열한다고 생각하자

그래고 백트래킹 문제풀이의 패턴을 미리 파악하면

  • 반복: 주어진 인풋 엘리먼트들에게 반복문 돌리기
  • 선택: 탐색타겟을 설정하고 엘리먼트 순서교체
  • 탐색: DFS 탐색실행
  • 선택취소: 선택과정 다시 복구

이와 같은 형태를 가지고 있음을 알수 있다.

그럼 이제 코드로 알아보자

function permutate(arr) {
  const result = []

  //DFS
  const dfs = (i, arr) => {
    // base condition
    if (i === arr.length) {
      return result.push([...arr])
    }

    for (let j = i; j < arr.length; j++) {
      //swap
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
      //dfs
      dfs(i + 1, arr)
      //swap back
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
    }
  }
  dfs(0, arr)
  return result
}
console.log(permutate(['a', 'b', 'c']))

위 코드를 자세히 분석해보면

  1. permute 함수는 두 개의 매개변수를 받는다:

    • arr: 순열을 생성할 원본 배열
    • i: 현재 순열을 생성하기 위해 고려해야 하는 시작 인덱스

  2. 함수를 호출할 때 i는 0으로 설정하여 배열의 전체 범위를 고려하도록 한다.

  3. 함수 내부에서, 기저 조건(base case)으로 i === arr.length를 확인다. 이는 시작 인덱스와 마지막 인덱스가 같아졌을 때, 즉 배열의 모든 요소를 고려했을 때를 의미한다. 이 경우 현재 배열이 하나의 완성된 순열이므로 출력하고 함수를 종료한다.

  4. for 루프는 i부터 arr.length까지 반복하며, 현재 인덱스(i)의 요소와 j번째 요소를 교환한다. 이렇게 교환하는 과정을 통해 배열의 요소들이 새로운 순서로 정렬된다.

  5. 요소를 교환한 후, permute 함수를 재귀적으로 호출합니다. 이 때 i + 1을 넘겨주어 다음 요소를 고려하도록 한다. 재귀 호출이 반환되면, 즉 하위 단계의 순열 생성이 완료되면, 요소의 위치를 다시 원래대로 돌려놓는다(backtrack). 이 과정을 통해 다른 경우의 수를 고려할 수 있도록 원본 배열의 상태를 유지한다.

  6. 이 과정을 i부터 arr.length까지 모든 인덱스에 대해 반복함으로써, 배열의 모든 가능한 순열을 생성할 수 있다.

재귀적인 순열 생성에서 핵심은 각 단계에서 배열의 요소를 교환한 후에 다음 단계로 넘어가고, 모든 하위 호출이 종료된 후에는 교환했던 요소를 원래대로 되돌리는 것이다. 이러한 과정을 통해 배열의 모든 요소들이 다양한 위치에서 사용되어 모든 가능한 순열을 탐색할 수 있다.

번외

위의 순열 알고리즘은 n개의 요소가 주어지고 n개수 만큼의 경우의 수를 구하는 것이라면,

n개의 요소에서 발생할수 있는 모든 경우의 수는 어떻게 구할수 있을까?

예를들면 [a,b,c] 에서 [a], [b], [c], [a,b] ... 처럼 탐색해야하면 어떻게 해야할까

이는 비슷하게 재귀를 사용해서 각 단계에서 한 요소를 추가하거나 추가하지 않는 선택을 통해 모든 가능한 조합을 생성하는 조합으로 풀이 할 수 있다.

Discuss on Twitter • View on GitHub