C++로 정확히 K개의 역전(Inversion)을 가진 순열 개수 구하기

문제 개요

배열에서 두 원소의 쌍 a[i], a[j]가 a[i] > a[j]이면서 i < j를 만족할 때, 이를 역전(inversion)이라고 부릅니다. 이 문제에서는 두 수 N과 K가 주어지며, 첫 N개의 자연수(1부터 N까지)로 만들 수 있는 모든 순열 중에서 정확히 K개의 역전을 가진 순열이 몇 개인지 구해야 합니다.

예시를 통해 살펴보겠습니다.

입력: N = 4, K = 1
출력: 3
설명: 첫 4개 수의 전체 순열은 1234, 1243, 1324, 2134입니다.
이중 역전이 1개인 순열은 1243, 1324, 2134로 총 3개입니다.

입력: N = 3, K = 2
출력: 3
설명: 첫 3개 수의 전체 순열은 123, 132, 213, 231, 312, 321입니다.
이중 역전이 2개인 순열은 231, 312, 321로 총 3개입니다.

방법 1: 브루트 포스(Brute Force)

가장 직관적인 방법은 브루트 포스 접근법입니다. 먼저 첫 N개의 수로 만들 수 있는 모든 순열을 생성한 뒤, 각 순열마다 역전의 개수를 일일이 세어 K와 같은지 확인합니다. 조건을 만족하면 결과 카운터를 증가시키는 방식입니다.

이 방법은 구현이 간단하지만, 순열의 개수가 N!로 폭발적으로 증가하기 때문에 N이 조금만 커져도 실행 시간이 기하급수적으로 늘어나 실용성이 떨어집니다.

방법 2: 재귀와 메모이제이션을 활용한 효율적 접근

더 효율적인 방법은 문제를 작은 단위로 나누어 해결하는 것입니다. 핵심 아이디어는 다음과 같습니다.

N-1개의 수로 만든 순열에 가장 큰 수인 N번째 수를 삽입한다고 생각해 보겠습니다. 새 숫자를 삽입하는 위치에 따라 추가되는 역전의 개수가 달라집니다. 예를 들어, 새 숫자를 뒤에서 3번째 위치에 삽입하면 역전이 3개 추가됩니다. 따라서 역전이 (K − 3)개인 (N − 1)개 수의 순열들에 새 숫자를 해당 위치에 삽입하면, 전체 역전 개수가 정확히 K가 됩니다.

이 논리를 다른 삽입 위치에도 동일하게 적용하면 다음과 같은 재귀 관계식을 얻을 수 있습니다.

find_permutations(N, K) = Σ find_permutations(N − 1, K − i), (단, 0 ≤ i ≤ min(K, N − 1))

여기에 메모이제이션(memoization)을 적용해 이미 계산한 값을 저장하면, 시간 복잡도를 O(N × K)로 크게 줄일 수 있습니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
const int X = 100;
int arr[X][X]; // 메모이제이션용 배열

// 재귀 함수
int find_permutations(int N_numbers, int K_inversion){
    if (N_numbers == 0){
        return 0; // N이 0이면 0 반환
    }
    if (K_inversion == 0)
        return 1; // K가 0이면 역전 없는 순열 1개
    if (arr[N_numbers][K_inversion] != 0)
        return arr[N_numbers][K_inversion]; // 이미 계산된 값 반환
    int result = 0;
    for (int i = 0; i <= K_inversion; i++){
        if (i <= N_numbers - 1)
            result += find_permutations(N_numbers - 1, K_inversion - i);
    }
    arr[N_numbers][K_inversion] = result;
    return result;
}

// 메인 함수
int main(){
    int N, K;
    cin >> N; // 사용자 입력 받기
    cin >> K;
    cout << find_permutations(N, K);
    return 0;
}

실행 결과

입력: N = 4, K = 3
출력: 6

N = 4, K = 3으로 실행하면 역전이 정확히 3개인 순열이 6개임을 확인할 수 있습니다.

마무리

이 글에서는 정확히 K개의 역전을 가진 순열의 개수를 구하는 문제를 O(N × K)의 시간 복잡도로 해결하는 방법을 살펴보았습니다. 단순히 모든 순열을 검사하는 브루트 포스 방식과, 재귀 관계식에 메모이제이션을 적용한 효율적인 동적 계획법 방식을 모두 다루었으며, 전체 C++ 구현 코드도 함께 확인했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다. 이 글이 여러분의 알고리즘 학습에 도움이 되기를 바랍니다.