[백준/C++] 15649(N과 M (1)) (int를 string으로 / 순열 / next_permutation / 백트래킹)

https://www.acmicpc.net/problem/15649

 

---

 

내가 해냄 : `next_permutation()` 사용

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

int main()
{
    // N과 M을 입력받는다.
    int N, M;
    cin >> N >> M;

    // 1부터 N까지의 자연수를 담을 벡터 v를 선언하고 초기화한다.
    vector<int> v;
    for (int i = 0; i < N; i++)
        v.push_back(i + 1);

    // prev: 직전에 출력한 순열 문자열을 저장하는 변수
    // cur: 현재 출력할 순열 문자열을 저장하는 변수
    string prev = "", cur = "";

    // next_permutation()을 이용하여 N개의 수로 만들 수 있는 모든 순열을 생성한다.
    // N Permutation N
    do {
        // 현재 순열에서 앞에서 M개를 선택하여 문자열 cur을 만든다.
        for (int i = 0; i < M; i++)
            cur += to_string(v[i]) + ((i != M - 1) ? " " : ""); // 마지막 원소 뒤에는 공백을 붙이지 않음

        // 현재 생성한 문자열(cur)이 이전에 출력한 문자열(prev)과 다르면
        // 중복되지 않는 순열이므로 출력한다
        if (cur != prev)
        {
            cout << cur << "\n"; 
            prev = cur; // 이전 문자열(prev)을 현재 문자열(cur)로 갱신
        }

        // 다음 반복을 위해 cur를 초기화한다.
        cur = "";
    } while (next_permutation(v.begin(), v.end())); // 다음 순열이 존재하는 동안 반복

    return 0;
}

 

사용한 핵심 개념

// `next_permutation()`을 이용한 순열 생성

역할

• 주어진 수열을 사전순(lexicographical order)으로 다음 순열로 변환하는 함수다.
• 이를 반복적으로 호출하면 모든 순열을 사전순으로 탐색할 수 있다.

특징

• vector 또는 배열과 함께 사용되며, 사전순으로 정렬된 상태(= 오름차순 정렬이 된 상태)에서 시작해야 모든 순열을 탐색할 수 있다.
• 최후의 순열(내림차순 상태)까지 도달하면 `false`를 반환하며 종료된다.
• 사용 예시

vector<int> v = {1, 2, 3};
do {
    for (int num : v) cout << num << " ";
    cout << "\n";
} while (next_permutation(v.begin(), v.end()));

• 결과

 

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

// 벡터 초기화 및 활용 (`vector<int>` 사용)

역할

• 1부터 N까지의 자연수를 저장하는 벡터를 선언하고 초기화하는 역할을 한다.
• `push_back()`을 사용하여 1부터 N까지의 값을 순차적으로 삽입한다. 이를 통해 저절로 오름차순 정렬이 된 효과를 볼 수 있다.
• 구현 방식

vector<int> v;
for (int i = 0; i < N; i++) 
    v.push_back(i + 1);

• 작동 원리
  • `for` 루프를 활용하여 `v[0] = 1, v[1] = 2, ..., v[N-1] = N`과 같이 초기화된다.

 

// `prev`와 `cur`을 이용한 중복 제거

역할:

• `next_permutation()`을 사용하면 N개의 전체 순열을 생성하지만,
  앞 M개의 원소만 선택할 경우 일부 순열이 중복될 수 있다.
• 이를 방지하기 위해 직전 출력된 순열(prev)과 현재 순열(cur)을 비교하여 중복을 제거한다.

구현 방식

string prev = "", cur = "";
do {
    cur = "";
    for (int i = 0; i < M; i++)
        cur += to_string(v[i]) + ((i != M - 1) ? " " : "");
    
    if (cur != prev) { 
        cout << cur << "\n"; 
        prev = cur;
    }
} while (next_permutation(v.begin(), v.end()));

 

작동 원리

1. `cur` 문자열을 생성하여 현재 M개의 숫자를 저장한다.
2. `prev`와 `cur`을 비교하여 중복되지 않은 경우에만 출력한다.
3. `prev`를 `cur`로 갱신하여 다음 순열과 비교할 기준을 설정한다.

 

시간 복잡도 분석

해당 코드는 `next_permutation()`을 이용하여 N개의 수로 만들 수 있는 모든 순열을 탐색하며,
각 순열에서 M개의 원소만 선택하여 출력하는 구조이다.

1. `next_permutation()`의 호출 횟수
   • `next_permutation(v.begin(), v.end())`은 N개의 원소로 만들 수 있는 모든 순열을 순차적으로 생성한다.
   • 따라서 N개의 순열을 생성하는 데 걸리는 시간 복잡도는 O(N!)이다.
2. 출력 문자열 생성 및 비교 연산
   • `for` 루프를 통해 M개의 원소를 선택하여 `cur` 문자열을 구성하는 과정의 시간 복잡도는 O(M)이다.
   • `cur`과 `prev`를 비교하는 연산도 문자열 길이가 O(M)이므로 O(M)의 시간 복잡도를 갖는다.
   • 따라서, 한 번의 순열에 대해 수행하는 전체 연산의 시간 복잡도는 O(M)이다.
3. 총 시간 복잡도
   • `next_permutation()`이 O(N!)번 실행되며, 매 실행마다 O(M)의 연산을 수행하므로,
   • 전체 시간 복잡도는 O(N! * M)이 된다.

• 즉, N!이 급격하게 증가하므로 N이 커질수록 실행 시간이 매우 빠르게 증가하는 알고리즘이다.
  • `prev`와 `cur`을 이용한 중복 제거를 통해 불필요한 출력을 방지하지만, 최악의 경우 여전히 O(N! * M)이 된다.
  • 상당히 비효율적이다.

 

---

 

 

AI 피드백 : 백트래킹(Backtracking) 활용

#include <iostream>     // 표준 입출력
#include <vector>       // vector 컨테이너
#include <algorithm>    // sort(), next_permutation()
#include <numeric>      // iota() 사용을 위한 헤더

using namespace std;

int N, M;
vector<int> v;          // 1부터 N까지의 수 저장
vector<bool> used;      // 방문 여부 체크
vector<int> result;     // 현재 선택된 수열

// 백트래킹을 이용하여 중복 없이 M개의 원소를 선택한다.
void backtrack(int depth) {
    // M개 선택 완료 시 출력한다.
    if (depth == M) {
        for (int i = 0; i < M; i++)
            cout << result[i] << (i != M - 1 ? " " : "\n");
        return;
    }

    // 사용되지 않은 숫자를 하나씩 선택한다.
    for (int i = 0; i < N; i++) {
        if (!used[i]) {
            used[i] = true;          // 선택한 숫자를 방문 처리한다.
            result.push_back(v[i]);  // 현재 선택된 수열에 추가한다.

            backtrack(depth + 1);    // 다음 숫자를 선택한다.

            // 백트래킹: 이전 상태로 되돌린다.
            used[i] = false;
            result.pop_back();
        }
    }
}

int main() {
    // N과 M을 입력받는다.
    cin >> N >> M;

    // 1부터 N까지의 수를 벡터에 저장한다.
    v.resize(N);
    iota(v.begin(), v.end(), 1);

    // 방문 여부를 체크할 배열을 초기화한다.
    used.resize(N, false);

    // 백트래킹을 시작한다.
    backtrack(0);

    return 0;
}

주요 개선 포인트

// `next_permutation()`을 제거하고, 백트래킹을 이용하여 직접 순열을 생성했다

• 기존 코드에서는 모든 순열을 탐색한 후, 중복을 제거하는 방식을 사용했다.
• 개선된 코드에서는 아예 중복이 없는 순열을 처음부터 생성하므로 불필요한 비교 연산이 사라짐.

// 문자열 비교(prev vs cur) 방식 대신, `vector<bool> used`를 활용함

• 기존 코드에서는 이전 문자열(`prev`)과 현재 문자열(`cur`)을 비교하는 방식을 사용하여 중복을 제거했다.
• 개선된 코드에서는 이미 방문한 숫자를 `used[i]`로 체크하여 중복이 발생하지 않도록 차단했다

// 출력 최적화 (`cout` 활용)

• 기존 코드에서는 `cur` 문자열을 매번 생성하여 출력했다.
• 개선된 코드에서는 `cout`을 직접 활용하여 불필요한 문자열 연산을 줄였다.

// 시간 복잡도 개선

• 기존 코드: O(N! * M) → 모든 순열을 탐색한 후 필요한 경우만 출력
• 개선 코드: O(N! / (N-M)!) → 필요한 조합만 직접 탐색

 

추가로 사용한 개념

// 백트래킹 (Backtracking)

역할

• 가능한 모든 경우의 수를 탐색하면서 불필요한 탐색을 가지치기(Pruning)하여 최적화하는 기법이다.
• 방문 여부(`used` 배열)를 이용하여 이미 선택된 원소를 다시 선택하지 않도록 제한한다.

사용 예시

void backtrack(int depth) {
    if (depth == M) {  // M개 선택 완료 → 출력
        for (int i = 0; i < M; i++)
            cout << result[i] << (i != M - 1 ? " " : "\n");
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!used[i]) {  
            used[i] = true;          // 숫자 사용 처리
            result.push_back(v[i]);  // 현재 선택된 수열에 추가

            backtrack(depth + 1);    // 다음 숫자 선택

            used[i] = false;         // 백트래킹 (되돌리기)
            result.pop_back();
        }
    }
}

 

// vector<bool>을 이용한 방문 체크

역할

• 이미 선택한 원소인지 여부를 저장하여 중복된 선택을 방지한다.

사용 예시:

vector<bool> used(N, false); // 모든 원소를 처음에는 미사용 상태로 설정

if (!used[i]) {  // 사용되지 않은 원소만 선택
    used[i] = true;   // 사용 처리
    result.push_back(v[i]);

    backtrack(depth + 1);

    used[i] = false;  // 백트래킹: 원래대로 복구
}

기존 코드의 `prev`와 `cur`을 이용한 중복 비교보다 더 효율적인 방식이다.

 

• 기존 코드에서는 `cur`과 `prev`를 비교(O(M))해야 했지만, 백트래킹은 `used[]` 배열을 사용하여 선택한 원소인지 O(1) 연산으로 확인이 가능하다.
• 즉, 문자열 비교를 하지 않고 방문 여부를 빠르게 확인할 수 있어 성능이 향상된다.

 

 

// iota()를 이용한 벡터 초기화

역할:

• `iota()`를 사용하면 1부터 N까지의 숫자를 한 줄로 채울 수 있다.
• 기존 for 루프를 사용하는 것보다 더 간결한 코드 작성이 가능하다.

사용 예시:

 

v.resize(N);
iota(v.begin(), v.end(), 1);  // v = {1, 2, 3, ..., N}

`for` 루프 없이 `iota()` 한 줄로 벡터를 초기화할 수 있어 코드가 더 깔끔해진다.

 

// `cout`을 이용한 출력 최적화

역할

• `cout`을 활용하여 문자열 연산을 줄이고, 더 빠르게 출력할 수 있도록 개선한다.
• 삼항 연산자를 활용하여 출력 형식을 조정하고 마지막 숫자 뒤에는 공백을 붙이지 않는다.

기존 방식 (`prev`와 `cur`을 이용한 문자열 비교)

cur += to_string(v[i]) + ((i != M - 1) ? " " : "");

개선된 방식 (`cout` 활용)

cout << result[i] << (i != M - 1 ? " " : "\n");

출력 최적화로 불필요한 문자열 연산을 줄이고 실행 속도를 높인다.

 

 

---

 

 

(위) AI 피드백 코드 / (아래) 내가 작성한 코드

 

이론적으로 보면 백트래킹을 활용한 코드(AI 피드백 코드)가 O(N! / (N-M)!)이므로 더 효율적이어야 한다.
반면, `next_permutation()`을 활용한 코드는 O(N! * M)이므로 더 느릴 것이라고 예상할 수 있다.

 

하지만, 실제 실행 결과는 `next_permutation()`을 활용한 코드가 더 빠르게 실행되었다.
이는 다음과 같은 이유일 것이라 예상된다.

 

`next_permutation()`의 내부 최적화

C++ 표준 라이브러리에서 제공하는 `next_permutation()`은 매우 효율적으로 구현된 알고리즘이다.

• `next_permutation()`은 사전순으로 정렬된 배열에서 다음 순열을 구하는 최적화된 연산을 수행한다.
• 일반적인 백트래킹 방식보다 빠르게 순열을 생성할 수 있다.
• 내부적으로 `swap` 연산과 빠른 비교 연산을 사용하여 최적화가 되어 있기 때문에, 백트래킹보다 실행 속도가 빠를 수 있다.

즉, C++ STL의 최적화된 next_permutation()이 백트래킹의 순열 생성보다 실제 실행에서 더 빠르게 동작할 수 있다.

 

재귀 함수 호출의 오버헤드

백트래킹 방식은 재귀 함수 호출을 반복적으로 수행해야 한다.
재귀 호출 과정에서 함수 호출 스택이 쌓이고 해제되는 과정이 반복되기 때문에 실행 속도에 영향을 미칠 수 있다.

• `backtrack(depth + 1)`을 호출할 때마다 스택 프레임이 새로 생성되며, 함수가 종료될 때마다 스택 프레임이 해제된다.
• 즉, 재귀 호출이 많아질수록 함수 호출 오버헤드가 커지고 실행 속도가 느려질 가능성이 있다.

반면, `next_permutation()`은 재귀 호출 없이 순열을 반복적으로 생성하는 방식이므로, 함수 호출 오버헤드가 적다.

 

문자열 연산 vs 벡터 연산

AI 피드백 코드에서는 cout을 사용할 때 벡터에서 값을 가져와 직접 출력하는 방식이다.

for (int i = 0; i < M; i++)
    cout << result[i] << (i != M - 1 ? " " : "\n");

이 과정은 벡터에서 값을 가져와 바로 출력하기 때문에 메모리 복사 오버헤드가 적다.

반면, `next_permutation()`을 사용하는 기존 코드에서는 문자열을 생성하고 비교하는 과정이 추가된다.

cur += to_string(v[i]) + ((i != M - 1) ? " " : "");

하지만, STL에서는 문자열 연산도 내부적으로 최적화되어 있으며,
단순히 cur != prev 비교하는 것이 백트래킹에서 벡터 연산을 수행하는 것보다 빠를 수 있다.

➡ STL의 문자열 비교 연산(O(M))이 재귀 호출을 통한 벡터 조작보다 더 빠를 수도 있음.

 

입출력 최적화 영향

• `cout`은 기본적으로 버퍼링을 사용하지만,
  재귀 호출이 많아지면 입출력 연산이 더 느려질 가능성이 있다
• `next_permutation()`을 활용한 코드는 반복문 기반이므로 입출력 버퍼를 더 효율적으로 활용할 수 있다.
• 백트래킹 코드에서도 출력을 모아두었다가 한 번에 출력하는 방식을 사용하면 속도가 더 빨라질 가능성이 있다.
  • 이 가능성을 염두하여 AI 피드백 코드의 `main()` 함수에 ` ios_base::sync_with_stdio(false);`를 추가하고 실행해보았는데 똑같이 24초가 걸렸다.