Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 배우는 교란 순열(Derangement) 개수 세기 — 완전 탐색부터 재귀 풀이까지

교란 순열(Derangement)은 N개의 숫자 중 어떤 숫자도 자기 자신의 원래 위치에 있지 않도록 배열한 순열을 말합니다. 예를 들어 { 1, 2, 3 }의 교란 순열 중 하나는 { 2, 3, 1 }입니다. 이 배열에서 어떤 요소도 원래 인덱스(0, 1, 2)에 위치하지 않기 때문입니다.

이 글에서는 재귀(Recursion)를 활용해 N개의 숫자에 대해 가능한 교란 순열의 개수를 구하는 방법을 알아보겠습니다.

교란 순열의 기본 규칙

요소 개수별 교란 순열의 개수를 살펴보면 다음과 같은 패턴을 발견할 수 있습니다.

  • N = 0 : 정렬할 요소가 없으므로 1가지 (빈 경우) → 반환값 1
  • N = 1 : 요소가 하나뿐이라 자리를 바꿀 수 없음 → 반환값 0
  • N = 2 : 두 요소의 위치를 맞바꾸는 한 가지 방법, { 1, 2 } → { 2, 1 } → 반환값 1
  • N = 3 : { 2, 3, 1 }, { 3, 1, 2 }의 2가지 → 반환값 2
  • N = 4 : 총 9가지
  • N ≥ 3 일반화 : permutation(N) = (N − 1) × ( permutation(N−1) + permutation(N−2) )

재귀적 접근의 핵심 아이디어

배열의 각 요소를 관점에서 보면 다음과 같이 설명할 수 있습니다.

  • 인덱스 0의 요소는 자신을 제외한 (N − 1)개의 위치 중 한 곳으로 이동할 수 있습니다.
  • 인덱스 i의 요소가 인덱스 0으로 이동하는 경우, arr[i]와 arr[0]의 자리가 서로 바뀌므로 나머지 (N − 2)개의 요소만 계산하면 됩니다.
  • 인덱스 i의 요소가 인덱스 0으로 이동하지 않는 경우, 남은 (N − 1)개의 요소에 대해 (N − 2)가지 선택지가 존재합니다.

C++로 배우는 교란 순열(Derangement) 개수 세기 — 완전 탐색부터 재귀 풀이까지

입력 / 출력 예시

예시 1

Arr[] = { 1, 2 }
No. of derangements : 1

설명 — 1과 2의 원래 위치는 각각 인덱스 0과 1입니다. 둘 다 원래 위치에 있으면 안 되므로 유일한 방법은 두 위치를 맞바꾸는 것, 즉 { 2, 1 }입니다.

예시 2

Arr[] = { 1, 2, 3 }
No. of derangements : 2

설명 — 1, 2, 3의 원래 위치는 각각 인덱스 0, 1, 2입니다.

  • 1은 인덱스 1 또는 2에 배치 가능
  • 2는 인덱스 0 또는 2에 배치 가능
  • 3은 인덱스 0 또는 1에 배치 가능

조건을 만족하는 결과는 { 2, 3, 1 }과 { 3, 1, 2 }의 2가지입니다.

프로그램의 풀이 전략

  • 정수형 변수 Num이 현재 요소의 개수를 저장합니다.
  • 재귀 함수 derangements(int N)는 요소 개수 N을 입력받아 해당 크기의 교란 순열 개수를 반환합니다.
  • N = 0, 1, 2인 경우는 이미 계산된 값(1, 0, 1)을 그대로 반환하는 베이스 케이스(Base Case)로 처리합니다.
  • N > 2일 때는 다음 공식을 이용해 재귀 호출을 수행합니다.
    (N − 1) × ( derangements(N − 1) + derangements(N − 2) )

재귀 호출이 거슬러 올라가는 백트래킹 단계에서 각 결과값이 누적되어 최종 개수가 계산됩니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

int derangements(int N){
    if (N == 0)
        return 1;
    if (N == 1)
        return 0;
    if (N == 2)
        return 1;
    return (N - 1) * (derangements(N - 1) + derangements(N - 2));
}

int main(){
    int Numbers = 5;
    cout << "Number of Derangements : " << derangements(Numbers);
}

실행 결과

Number of Derangements : 44

마무리 및 성능 개선 팁

위 코드는 재귀를 통해 교란 순열의 개수를 직관적으로 구합니다. 다만 동일한 하위 문제가 반복 계산되므로 시간 복잡도는 지수적으로 증가할 수 있습니다. 실무에서는 메모이제이션(Memoization)이나 동적 계획법(DP)을 적용해 O(N) 시간 복잡도로 최적화하는 것이 좋습니다. 또한 N이 커질 경우 값이 매우 빠르게 증가하므로, 오버플로우를 방지하기 위해 모듈러 연산(예: 10⁹ + 7)을 함께 사용하는 것도 고려해볼 만합니다.