알고리즘 [순열] 편

알고리즘 [순열]편

순열이란?

모든 조합을 구하는 방법이다
순서가 바뀌면 다른 것으로 취급하여 순서가 중요하다

[1,2,3]에서 2개를 뽑아서 순열을 구성한다면
[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]이 나온다.

즉, [1,2]와 [2,1]은 다른 것으로 판단한다.

중복순열

중복 순열은 자기 자신도 포함한다

[1,1],[2,2],[3,3]도 포함!

조합과의 차이점?

조합은 순서가 중요하지 않고 중복된 것을 빼고 판단한다

[1,2,3]에서 2개를 뽑아서 조합을 구성한다면
[1,2],[1,3],[2,3]이 나온다

순열 구하는 코드

그냥 외우기

function permutate(arr) {
  const result = [];

  const dfs = (i, arr) => {
    console.log('dfs 호출:', i, arr);
    // base condition
    if (i === arr.length) {
      console.log('배열 추가:', arr);
      return result.push([...arr]);
    }
    for (let j = i; j < arr.length; j++) {
      console.log('swap 전:', arr[i], arr[j], arr);
      //swap
      [arr[i], arr[j]] = [arr[j], arr[i]];
      console.log('swap 후:', arr[i], arr[j], arr);
      //dfs
      dfs(i + 1, arr);
      console.log('재귀 후 swap back 전:', arr[i], arr[j], arr);
      //swap back
      [arr[i], arr[j]] = [arr[j], arr[i]];
      console.log('swap back 후:', arr[i], arr[j], arr);
    }
  }

  dfs(0, arr);
  console.log('result:', result);
  return result;
}

permutate(['a', 'b', 'c']);

실행 순서

permutate(['a','b','c'])가 호출되면 다음과 같은 순서로 실행됩니다.

1. const result = []; 결과를 저장할 빈 배열 result을 선언합니다.
2. const dfs = (i, arr) => {...} 깊이 우선 탐색(DFS) 함수 dfs를 선언합니다.
3. dfs(0, arr); dfs 함수를 인덱스를 0으로 시작하도록 호출합니다.
4. if (i === arr.length){...} 재귀 호출을 중단하는 기저 조건을 만족하지 않으므로, 다음 코드가 실행됩니다.
5. for (let j=i; j<arr.length; j++){...} 현재 인덱스 i부터 배열의 끝까지 순회합니다.
6. [arr[i], arr[j]] = [arr[j], arr[i]]; 현재 인덱스 i와 j의 요소를 교환합니다. 첫 번째 반복에서는 ['a', 'b', 'c']에서 ['b', 'a', 'c']로 교환됩니다.
7. dfs(i + 1, arr); 다음 인덱스로 재귀 호출합니다. 인덱스 i가 0이므로, 다음 호출에서는 i가 1이 됩니다.
8. if (i === arr.length){...} 재귀 호출을 중단하는 기저 조건을 만족하지 않으므로, 다음 코드가 실행됩니다.
9. for (let j=i; j<arr.length; j++){...} 현재 인덱스 i부터 배열의 끝까지 순회합니다.
10. [arr[i], arr[j]] = [arr[j], arr[i]]; 현재 인덱스 i와 j의 요소를 교환합니다. 두 번째 반복에서는 ['a', 'b', 'c']에서 ['c', 'b', 'a']로 교환됩니다.
11. dfs(i + 1, arr); 다음 인덱스로 재귀 호출합니다. 인덱스 i가 1이므로, 다음 호출에서는 i가 2가 됩니다.
12. if (i === arr.length){...} 재귀 호출을 중단하는 기저 조건을 만족합니다. 현재 배열은 ['c', 'b', 'a']이므로, result 배열에 복제된 배열 ['c', 'b', 'a']를 추가합니다.
13. [arr[i], arr[j]] = [arr[j], arr[i]]; 현재 인덱스 i와 j의 요소를 다시 복구합니다. 마지막으로, 처음 배열 상태 ['a', 'b', 'c']으로 복구됩니다.
14. return result; result 배열을 반환합니다. 최종적으로, permutate(['a','b','c'])는 [['a', ''b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'b', 'a'], ['c', 'a', 'b']]를 반환합니다.

---

표로 정리한 출력 결과

아래는 permutate(['a','b','c']) 함수 실행 시, 해당 요소의 순열을 구하는 과정을 표와 함께 정리한 것입니다.

i	j	before swap	after swap	result
0	0	['a','b','c']	['a','b','c']
1	1	['a','b','c']	['a','b','c']
1	2	['a','b','c']	['a','c','b']	['a','c','b']
1	1	['a','c','b']	['a','c','b']
2	2	['a','c','b']	['a','c','b']
2	1	['a','c','b']	['c','a','b']	['c','a','b']
2	2	['c','a','b']	['c','a','b']
1	2	['c','a','b']	['c','b','a']	['c','b','a']
1	1	['c','b','a']	['c','b','a']
2	2	['c','b','a']	['c','b','a']
2	1	['c','b','a']	['b','c','a']	['b','c','a']
2	2	['b','c','a']	['b','c','a']

초기에는 i와 j 모두 0으로 시작합니다. i와 j는 순서대로 0부터 arr의 길이 - 1까지 증가합니다.

이 때, i와 j가 같을 때(i === j), arr[i]와 arr[j]를 바꿀 필요가 없으므로 그대로 진행됩니다.

만약, i와 j가 다를 경우(i !== j), arr[i]와 arr[j]를 서로 바꿔줍니다. 그리고 다음 순열을 구하기 위해 dfs(i + 1, arr)를 호출합니다.

이후, dfs(i + 1, arr) 호출이 끝나면 다시 arr[i]와 arr[j]를 바꿔 원래대로 복구합니다.

이 과정을 반복하면서 모든 순열을 찾고, 그 순열들을 result 배열에 저장합니다.

console.log 출력결과

dfs 호출: 0 [ 'a', 'b', 'c' ]
swap 전: a a,b,c
swap 후: b a,b,c
dfs 호출: 1 [ 'b', 'a', 'c' ]
swap 전: a a,a,c
swap 후: c a,a,c
배열 추가: [ 'a', 'c', 'b' ]
재귀 후 swap back 전: c a,c,a
swap back 후: a a,c,a
swap 전: c c,a,a
swap 후: a c,a,a
dfs 호출: 2 [ 'a', 'c', 'b' ]
swap 전: c c,b,a
swap 후: b c,b,a
dfs 호출: 2 [ 'b', 'c', 'a' ]
swap 전: c b,c,a
swap 후: a b,c,a
배열 추가: [ 'b', 'a', 'c' ]
재귀 후 swap back 전: a b,a,c
swap back 후: b b,a,c
swap back 전: b b,c,a
swap back 후: c b,c,a
swap 전: b b,c,a
swap 후: c c,b,a
dfs 호출: 1 [ 'c', 'b', 'a' ]
swap 전: b b,b,a
swap 후: a b,b,a
dfs 호출: 2 [ 'a', 'c', 'b' ]
swap 전: b a,c,a
swap 후: c a,c,a
재귀 후 swap back 전: c a,c,a
swap back 후: b a,c,a
swap 전: c b,c,a
swap 후: a b,c,a
dfs 호출: 2 [ 'a', 'b', 'c' ]
swap 전: b a,b,c
swap 후: c a,b,c
배열 추가: [ 'a', 'b', 'c' ]
재귀 후 swap back 전: c a,b,c