[JavaScript] 다음 순열 (Next Permutation)

코딩테스트 문제를 풀고 알고리즘 정리합니다.

 

다음순열이란?

컴퓨터 과학에서, '다음 순열'이란 주어진 순열에서 사전순으로 다음에 오는 순열을 의미합니다.

예를 들어 [1,2,3]의 다음 순열은 [1,3,2]입니다.

[1,2,3]의 다음 순열을 끝까지 진행하면 아래 값처럼 진행 됩니다.

[1,2,3]

[1,3,2]

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

 

Javascript에서 다음 순열을 구하는 과정은 다음과 같습니다:

1. 배열의 끝에서부터 시작하여, 현재 원소가 이전 원소보다 큰 위치(i)를 찾습니다. 이 위치는 '다음 순열'에서 숫자가 바뀌어야 하는 첫 번째 위치입니다.
2. 다시 배열의 끝에서부터 시작하여, 위치 i의 원소보다 큰 첫 번째 원소의 위치(j)를 찾습니다.
3. 위치 i와 j의 원소를 서로 교환(swap)합니다.
4. 위치 i+1부터 끝까지의 원소들을 뒤집습니다.

이렇게 하면 '다음 순열'을 구할 수 있습니다.

아래는 이를 구현한 Javascript 코드입니다:

function nextPermutation(nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        let j = nums.length - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);
    }
    reverse(nums, i + 1);
}

function swap(nums, i, j) {
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

function reverse(nums, start) {
    let left = start, right = nums.length - 1;
    while (left < right) {
        swap(nums, left, right);
        left++;
        right--;
    }
}

 

'다음 순열' 알고리즘은 여러 문제들을 해결하는데 사용될 수 있습니다.

1. 순열 생성: 모든 가능한 순열을 생성해야 하는 문제에서 '다음 순열' 알고리즘은 매우 유용합니다. 각 순열을 한 번씩만 생성하며, 사전 순으로 모든 순열을 생성할 수 있습니다.
2. 순서의 최적화 문제: 여행 경로, 배송 경로 등과 같이 순서에 따라 결과가 달라지는 문제에서 '다음 순열' 알고리즘은 최적의 해를 찾는데 사용될 수 있습니다. 모든 가능한 순서를 찾아 비교함으로써 최적의 해를 찾을 수 있습니다.
3. 브루트 포스 알고리즘: '다음 순열' 알고리즘은 브루트 포스 알고리즘에도 사용될 수 있습니다. 브루트 포스 알고리즘은 모든 가능한 조합을 확인하는 방법으로, '다음 순열' 알고리즘을 이용하면 가능한 모든 조합을 사전 순으로 생성하고 확인할 수 있습니다.
4. 암호 해독: '다음 순열' 알고리즘은 암호를 해독하는 데도 사용될 수 있습니다. 가능한 모든 암호를 생성하여 시도해보는 방식으로 암호를 해독할 수 있습니다.

이런 방식으로 '다음 순열' 알고리즘이 다양한 문제 해결에 사용될 수 있지만 모든 가능한 경우를 확인하는 방식이므로, 경우의 수가 많을 때는 시간이 많이 걸릴 수 있어 이 점을 고려하여 알고리즘을 선택 할 필요가 있습니다.

 

사례가 궁금해서 찾아봤고, 다음 순열 알고리즘을 활용하여 해결한 사례 중 하나는 '여행하는 판매원 문제(Travelling Salesman Problem, TSP)' 였습니다.

 

여행하는 판매원 문제는 다음과 같습니다

판매원이 여러 도시를 방문하려고 합니다. 각 도시는 한 번만 방문해야 하며, 처음 출발한 도시로 돌아와야 합니다. 이 때, 판매원이 모든 도시를 방문하는데 필요한 최소 비용은 얼마인가요?

이 문제는 다음 순열 알고리즘을 사용하여 해결할 수 있습니다. 모든 도시들의 순열을 생성하고, 각 순열에 대해 총 이동 비용을 계산합니다. 그 중에서 가장 비용이 적게 드는 순열이 바로 최적의 해답이 됩니다.

단, 방문해야하는 도시 개수가 늘어난다면 다음순열을 대신 할 알고리즘을 선택해야합니다.