본문으로 건너뛰기

1. 순열(Permutation)의 기본 개념​

1.1 순열이란?​

  • 순열은 n개의 원소 중에서 r개를 선택하여 순서대로 나열하는 것을 말합니다.

수학적 표현​

  • 기호: nPr 또는 P(n,r)
  • 공식: nPr = n!/(n-r)!
    • (n-r)!로 나누는 이유는 선택하지 않은 원소들의 순서는 고려하지 않기 때문입니다.

예시로 이해하기​

3개의 숫자 [1,2,3]으로 만들 수 있는 모든 순열:

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
중요 포인트
  • 순서가 중요합니다 ([1,2,3]과 [1,3,2]는 다른 순열)
  • n개를 모두 사용하는 순열의 개수는 n!개
  • 순열은 사전순으로 나열할 수 있습니다

2. Next Permutation 알고리즘​

2.1 알고리즘의 원리​

왜 Next Permutation이 필요한가?​

  • 모든 순열을 저장하지 않고도 순서대로 생성할 수 있습니다
  • 메모리를 효율적으로 사용할 수 있습니다
  • 특정 순열의 '다음' 순열을 O(n) 시간에 찾을 수 있습니다

사전순 배열의 특성​

예를 들어 [1,2,3,4]로 만들 수 있는 순열들의 일부를 보겠습니다:

...
[1,4,3,2]
[2,1,3,4] <- 더 큰 순열
[2,1,4,3]
...

중요한 관찰:

  1. 뒤에서부터 보면, 숫자가 감소하는 부분(내림차순)이 있습니다
  2. 내림차순이 깨지는 지점이 '교체 포인트'가 됩니다
  3. 이 지점을 기준으로 다음 순열이 만들어집니다

2.2 내림차순을 찾는 이유​

순열에서 숫자가 내림차순으로 정렬된 부분은 해당 부분에서 만들 수 있는 가장 큰 순열을 의미합니다.

예시로 이해해봅시다. [6,2,1,5,4,3,0] 에서:

6,2,1,[5,4,3,0]
    ↑  ↑
    A  B
  • A: 내림차순이 깨지는 지점 (1)
  • B: 내림차순 시작 지점 (5,4,3,0은 내림차순)

이게 중요한 이유는:

  1. 내림차순 부분은 이미 해당 숫자들로 만들 수 있는 가장 큰 순열입니다
  2. 더 큰 순열을 만들려면, 내림차순이 깨지는 지점(A)의 숫자를 교체해야 합니다
  3. A의 숫자보다 크면서 가장 작은 숫자와 교체해야 '다음' 순열이 됩니다

2.3 알고리즘 단계별 설명​

[6,2,1,5,4,3,0] 예시로 진행과정을 보겠습니다:

  1. 내림차순 찾기
6,2,1,[5,4,3,0]
  • 뒤에서부터 내림차순 찾기: [5,4,3,0]
  • 1이 내림차순이 깨지는 지점
  1. 교체할 숫자 찾기
6,2,1,5,4,3,0
    ↑     ↑
    1과 3을 교체
  • 1보다 크면서 가장 작은 수인 3을 찾음
  • 1과 3을 교체
  1. 재정렬
6,2,3,5,4,1,0  -> 교체 후
6,2,3,0,1,4,5  -> 최종 결과
  • 교체한 위치(3) 이후의 숫자들을 오름차순으로 정렬
  • 이렇게 하면 사전순으로 다음에 오는 가장 작은 순열이 됨

2.4 Python 구현​

def next_permutation(arr):
    # 1. 뒤에서부터 내림차순이 깨지는 지점 찾기
    i = len(arr) - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1
    
    if i == -1:  # 전체가 내림차순이면 마지막 순열
        return False
    
    # 2. arr[i]보다 크면서 가장 작은 수 찾기
    j = len(arr) - 1
    while arr[j] <= arr[i]:
        j -= 1
        
    # 3. 두 수 교체
    arr[i], arr[j] = arr[j], arr[i]
    
    # 4. i+1부터 끝까지 뒤집기
    left = i + 1
    right = len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
        
    return True

# 사용 예시
arr = [6,2,1,5,4,3,0]
print("현재 순열:", arr)
next_permutation(arr)
print("다음 순열:", arr)
시간 복잡도
  • 한 번의 next_permutation 호출: O(n)
  • 뒤집기 연산: O(n)
  • 전체 메모리: O(1) (추가 메모리 불필요)

3. 조합(Combination)​

3.1 조합의 수학적 정의​

조합은 n개 중에서 r개를 선택하는 것을 의미하며, 순서는 고려하지 않습니다.

수식 표현​

  • 기호: nCr 또는 C(n,r)
  • 공식: nCr = n!/((n-r)! × r!)