C++에서 주어진 길이의 모든 시퀀스 출력하기

문제 개요

이 문제에서는 두 개의 정수 k와 n이 주어지며, 1부터 n까지의 숫자를 사용해 정렬된 순서로 길이 k의 모든 시퀀스를 출력해야 합니다.

주제를 쉽게 이해하기 위해 먼저 예제를 살펴보겠습니다.

입력 : k = 2 ; n = 3
출력 :
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

즉, 이 문제는 위 예시처럼 가능한 모든 시퀀스를 오름차순으로 나열해 출력하는 것이 목표입니다.

방법 1: 자릿수 증가 방식 (반복문)

가장 간단한 해결 방법은 시퀀스의 각 자릿수를 최댓값 n에 도달할 때까지 하나씩 증가시키는 것입니다. 이는 계산 과정에서 올림(carry)이 발생하는 원리와 비슷합니다. 해결 과정을 단계별로 살펴보겠습니다.

알고리즘

1) 크기가 k인 배열을 생성하고 모든 요소를 1로 초기화합니다. 즉, {1, 1, ...(k개)} 형태입니다.
2) 배열이 {n, n, ..., n}이 될 때까지 3번과 4번 단계를 반복합니다.
3) 배열을 출력합니다.
4) 배열의 요소가 다음 값이 되도록 증가시킵니다. 예를 들어 {1, 1, 1}은 {1, 1, 2}로, {1, 3, 3}은 {2, 1, 1}로 변경됩니다. 이를 위해 배열의 마지막(k번째) 요소부터 검사하며, 해당 값이 n과 같으면 그 앞의(k-1번째) 요소를 확인하는 식으로 같은 조건을 반복 적용합니다.

예제 코드

다음 프로그램을 통해 개념을 더 명확하게 이해할 수 있습니다.

#include<iostream>
using namespace std;
void printSequence(int arr[], int size){
    for(int i = 0; i < size; i++)
        cout<<arr[i]<<"\t";
    cout<<endl;
    return;
}
int nextElement(int arr[], int k, int n){
    int s = k - 1;
    while (arr[s] == n)
        s--;
    if (s < 0)
        return 0;
    arr[s] = arr[s] + 1;
    for(int i = s + 1; i < k; i++)
        arr[i] = 1;
    return 1;
}
void generateSequence(int n, int k){
    int *arr = new int[k];
    for(int i = 0; i < k; i++)
        arr[i] = 1;
    while(1){
        printSequence(arr, k);
        if(nextElement(arr, k, n) == 0)
            break;
    }
    return;
}
int main(){
    int n = 3;
    int k = 2;
    cout<<"The sequence is :\n";
    generateSequence(n, k);
    return 0;
}

실행 결과

The sequence is :
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

방법 2: 재귀를 활용한 개선된 접근

위 방법은 이해하기 쉽지만, 재귀(recursion)를 활용하면 더 효율적이고 깔끔하게 구현할 수 있습니다.

이 방법은 재귀 호출과 추가 인덱스를 사용해 시퀀스의 오프셋, 즉 자릿수가 변경되는 위치를 관리합니다. 함수는 재귀적으로 호출되며, 현재 인덱스까지의 항목은 그대로 유지한 채 인덱스 이후의 항목들에 대해 재귀 호출을 이어갑니다. 덕분에 각 자릿수가 자연스럽게 1부터 n까지 오름차순으로 채워집니다.

예제 코드

#include<iostream>
using namespace std;
void printSequence (int arr[], int size){
    for (int i = 0; i < size; i++)
        cout << arr[i] << "\t";
    cout << endl;
    return;
}
void generateSequence (int arr[], int n, int k, int index){
    int i;
    if (k == 0){
        printSequence (arr, index);
    }
    if (k > 0){
        for (i = 1; i <= n; ++i){
            arr[index] = i;
            generateSequence (arr, n, k - 1, index + 1);
        }
    }
}
int main (){
    int n = 3;
    int k = 2;
    int *arr = new int[k];
    cout<<"The sequence is:\n";
    generateSequence (arr, n, k, 0);
    return 0;
}

실행 결과

The sequence is :
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

마무리

반복문 기반의 증가 방식은 직관적이지만 매 단계마다 뒤에서부터 자릿수를 검사해야 하는 반면, 재귀 방식은 각 자릿수를 한 번씩만 설정하므로 코드가 간결하고 흐름이 명확합니다. 두 방식 모두 생성해야 할 시퀀스의 총 개수가 n^k개이므로 시간 복잡도는 O(n^k)이지만, 구현의 명확성과 유지보수 측면에서는 재귀 방식이 더 유리합니다.