백트래킹_순열 생성 (Permutation Generation)

순열(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. 재귀 호출: 그 원소를 추가한 후, 나머지 원소들 중에서 다시 순열을 만든다.
3. 기저 조건: 현재까지 만든 순열의 길이가 원소의 개수와 같으면, 해당 순열을 결과로 저장한다.
4. 백트래킹: 재귀 호출이 완료되면, 마지막으로 추가한 원소를 제거하여 이전 상태로 되돌아가고, 다른 경로를 탐색한다.

 

백트래킹을 이용한 순열 생성 구현

def generate_permutations(nums):
    def backtrack(current_permutation, used):
        # 모든 원소를 사용한 경우, 순열을 저장
        if len(current_permutation) == len(nums):
            result.append(list(current_permutation))
            return

        # 가능한 모든 원소를 탐색
        for i in range(len(nums)):
            if used[i]:  # 이미 사용한 원소는 패스
                continue

            # 현재 원소를 순열에 추가
            current_permutation.append(nums[i])
            used[i] = True  # 현재 원소를 사용했음을 표시

            # 재귀적으로 나머지 원소들에 대해 순열 생성
            backtrack(current_permutation, used)

            # 백트래킹: 원래 상태로 되돌리기
            current_permutation.pop()
            used[i] = False

    result = []
    used = [False] * len(nums)  # 원소 사용 여부를 기록
    backtrack([], used)  # 빈 순열로 시작
    return result

# 테스트
nums = [1, 2, 3]
print(generate_permutations(nums))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

코드 설명

1. generate_permutations(nums) 함수:
   • 이 함수는 입력 리스트 nums의 모든 순열을 생성한다. 결과를 저장할 리스트 result를 선언하고, 백트래킹 함수 backtrack을 호출하여 순열을 생성한다.
2. backtrack(current_permutation, used) 함수:
   • current_permutation: 현재까지 생성된 순열을 저장하는 리스트이다.
   • used: 각 원소가 현재 순열에서 사용되었는지 여부를 기록하는 리스트이다.
   • 기저 조건: 현재까지 만든 순열의 길이가 원소의 개수와 같으면, 즉 모든 원소를 한 번씩 사용한 경우, 해당 순열을 result에 추가한다.
   • 재귀적 호출: 사용되지 않은 원소를 찾아 현재 순열에 추가하고, 나머지 원소들에 대해 재귀 호출을 통해 순열을 생성한다.
   • 백트래킹: 재귀 호출이 끝난 후에는 마지막으로 추가한 원소를 제거(current_permutation.pop())하고, 그 원소를 다른 경로에서 다시 사용할 수 있도록 used[i] 값을 False로 되돌린다.
3. used 리스트:
   • used[i]는 원소 nums[i]가 현재 순열에서 사용되었는지 여부를 나타낸다. 이미 사용된 원소는 다시 사용할 수 없으므로 continue를 통해 건너뛴다.

 

백트래킹 순열 생성의 동작 과정

1. 초기 상태: current_permutation = []에서 시작하고, 모든 원소가 아직 사용되지 않았다 (used = [False, False, False]).
2. 첫 번째 재귀 호출:
   • 첫 번째 원소 1을 선택하여 current_permutation = [1]이 되고, used = [True, False, False]로 갱신된다.
   • 재귀 호출을 통해 나머지 원소들 중에서 순열을 생성한다.
3. 두 번째 재귀 호출:
   • 첫 번째 원소 1을 사용했으므로, 두 번째 원소 2를 선택하여 current_permutation = [1, 2]가 된다. used = [True, True, False]로 갱신된다.
   • 마지막 남은 원소 3을 선택하여 current_permutation = [1, 2, 3]이 된다.
   • 이 상태에서 모든 원소를 사용했으므로, 순열 [1, 2, 3]을 저장한다.
4. 백트래킹:
   • 순열 [1, 2, 3]을 저장한 후, 백트래킹을 통해 3을 제거하고 current_permutation = [1, 2]로 돌아간다.
   • 그다음에는 다른 경로를 탐색할 수 있도록 used[2]를 False로 갱신한다.
5. 다른 경로 탐색:
   • 이번에는 원소 3을 먼저 선택하는 경로를 탐색합니다. 이 과정을 반복하여 모든 순열을 탐색한다.

 

시간 복잡도

순열 생성에서 모든 원소를 사용하여 순서를 고려한 배열을 만들기 때문에, 각 원소는 한 번씩 모든 위치에 올 수 있다. 주어진 집합의 원소 수가 n개라면, 순열의 개수는 n!개이다.

• 시간 복잡도: O(n!)
  • 순열의 개수는 n!개이며, 각각의 순열을 생성하는데 n개의 원소를 한 번씩 탐색해야 하므로, 시간 복잡도는 O(n!)이다.
• 공간 복잡도: O(n) (재귀 깊이 및 사용 리스트)
  • 재귀 호출의 깊이는 n이므로, 스택 메모리는 O(n)입니다. 또한, used 리스트와 current_permutation 리스트가 각각 O(n)의 공간을 사용한다.

 

백트래킹 순열 생성의 장점

1. 효율적인 탐색: 백트래킹을 통해 모든 가능한 경로를 탐색하며, 중복을 방지하고 필요한 경로만 탐색할 수 있다.
2. 간결한 구현: 재귀적 호출과 백트래킹을 통해 문제를 직관적이고 간결하게 해결할 수 있다.
3. 확장 가능성: 이 방식은 다양한 문제(순열 생성, 조합, 부분 집합 생성 등)에 응용될 수 있다.

 

• 순열 생성은 주어진 집합의 원소들을 순서를 고려하여 모든 가능한 배열을 생성하는 문제이다.
• 백트래킹을 사용하여 사용된 원소를 추적하고, 각 원소를 선택할 때마다 재귀적으로 나머지 원소들을 탐색하는 방식으로 순열을 생성한다.
• 시간 복잡도는 O(n!)이며, 백트래킹을 통해 효율적으로 순열을 생성할 수 있다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms