순열 & 다음 순열

Source: Dev.to

소개

순열은 문제 해결 및 자료 구조(PS/DSA)에서 기본적인 개념입니다.
재귀, 백트래킹, 조합론, 그래프 탐색, 면접 문제, 그리고 최적화/상태 탐색 작업에 등장합니다. 순열을 깊이 이해하면 Next Permutation 문제를 간단하고 직관적으로 풀 수 있습니다.

순열은 요소들의 순서가 있는 배열입니다.

• n*개의 서로 다른 요소에 대해, 순열의 총 개수는 n! 입니다.

예시

배열에 대해:

[1, 2, 3]

모든 순열:

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

순서가 중요합니다 ([1,2] ≠ [2,1]). 순열을 탐색한다는 것은 가능한 모든 상태를 탐색한다는 의미입니다.

왜 순열이 PS / DSA에서 중요한가

순열은 다음을 훈련시킵니다:

• 재귀
• 백트래킹
• 상태 복원
• 깊이 우선 탐색
• 선택–탐색–취소 패턴

많은 고급 문제들이 순열을 기반으로 합니다:

• N‑퀸
• 스도쿠
• 부분집합 및 조합
• K번째 순열
• 단어 배열

백트래킹 템플릿

1. Choose – 요소를 교환하거나 사용된 것으로 표시합니다.
2. Explore – 재귀 호출.
3. Unchoose – 교환을 되돌리거나 표시를 해제합니다 (백트래킹).

고전적인 제자리 백트래킹 알고리즘:

function permute(nums) {
  const result = [];

  function backtrack(index) {
    if (index === nums.length) {
      result.push([...nums]);
      return;
    }

    for (let i = index; i  a - b);
  const result = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i  0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

[1,1,2]에 대한 결과:

[1,1,2]
[1,2,1]
[2,1,1]

다음 순열

목표: 사전 순(lexicographical) 순서에서 Q > P가 되도록 하는 가장 작은 순열 Q를 찾는다.

사전 순

[1,2,3]에 대한 순열은 다음과 같다:

123
132
213
231
312
321

다음 순열은 단순히 다음 행이다.

알고리즘 개요

function nextPermutation(nums) {
  // 1. Find the pivot
  let i = nums.length - 2;
  while (i >= 0 && nums[i] = 0 && nums[i] >= nums[i + 1]) {
    i--;
  }

  if (i >= 0) {
    // 2. Find successor
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) {
      j--;
    }
    // 3. Swap
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  // 4. Reverse suffix
  reverse(nums, i + 1);
}

function reverse(arr, start) {
  let l = start,
      r = arr.length - 1;
  while (l < r) {
    [arr[l], arr[r]] = [arr[r], arr[l]];
    l++;
    r--;
  }
}

중복 값이 있어도 사전 순 비교가 자연스럽게 처리하므로 알고리즘은 올바르게 동작한다.

예시

• [1,1,2] → [1,2,1] → [2,1,1] → 다시 호출하면 [1,1,2] 로 돌아간다.
• [3,2,1] (가장 큰 순열) → 피벗을 찾지 못함 → 전체 배열을 뒤집어 [1,2,3] (가장 작은 순열) 로 만든다.

비교 표

일반적인 함정: 백트래킹을 잊는 경우

전체 순열을 생성할 때, 이전 상태를 복원하지 못하면(스와프를 되돌리거나 마크를 해제하지 않음) 잘못된 결과나 중복된 순열이 발생합니다. 백트래킹 단계는 각 분기를 독립적으로 탐색하기 위해 필수적입니다.

Summary

• Permutations은 재귀와 백트래킹을 통해 모든 상태를 탐색하는 방법을 가르칩니다.
• Backtracking은 choose → explore → unchoose 패턴을 강조하며, 이는 많은 조합 문제에서 필수적입니다.
• Next Permutation은 사전 순서에서 한 단계 앞으로 이동하기 위한 최소한의 탐욕적 변화를 보여주며, O(1) 추가 공간을 사용합니다.

두 기술 모두 문제 해결자의 무기고에서 필수적인 도구입니다. 👍