[백준/C++] 15651(N과 M (2)) (중복 순열 / 백 트래킹 / 재귀 / 완전 탐색 / ostringstream)

 

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

 

---

내가 해냄 : Back tracking 이용

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

int N, M;               // 자연수 N과 M을 저장하는 변수
vector<int> v;          // 1부터 N까지의 숫자를 저장할 벡터
vector<int> result;     // 선택한 숫자를 저장할 벡터

/*
    문제의 핵심:
    - 숫자를 중복해서 선택할 수 있기 때문에 방문 체크를 하지 않는다.
    - 사전 순 증가하는 순서로 출력해야 하므로 1부터 N까지의 숫자를 저장한 후 백트래킹을 수행한다.
*/

// 백트래킹을 활용하여 자기 자신을 포함하여 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++) {
        result.push_back(v[i]); // 현재 선택한 숫자를 result에 추가한다

        backtrack(depth + 1);   // 다음 숫자를 선택하기 위해 재귀함수를 호출한다

        // Backtracking : 선택한 숫자를 제거하여 이전 상태로 되돌아 간다
        result.pop_back();
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // N과 M을 입력받는다
    cin >> N >> M;

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

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

    return 0;
}

 

 

사용한 핵심 개념

// 중복을 허용하는 순열 (중복 순열, Multiset Permutation)

• 문제에서 같은 수를 여러 번 선택할 수 있으므로 일반적인 순열이 아닌 "중복을 허용하는 순열"을 만들어야 한다.
• 따라서, 방문 체크 (`visited[]`)를 하지 않고 모든 숫자를 선택할 수 있도록 한다.

사용 예시

for (int i = 0; i < N; i++) {
    result.push_back(v[i]); // 현재 숫자 선택
    backtrack(depth + 1);   // 다음 숫자 선택
    result.pop_back();      // 백트래킹
}

• 방문 체크를 하지 않고 모든 숫자를 다시 선택할 수 있도록 허용했다.
• `v[i]`를 여러 번 선택하여 중복된 숫자가 포함된 수열을 생성할 수 있다.

 

// 백트래킹 (Backtracking)

• 백트래킹은 모든 가능한 경우를 탐색하는 알고리즘 기법이다.
• 불필요한 경로를 미리 차단하여 탐색 속도를 최적화할 수 있다.
• 이번 문제에서는 M개의 숫자를 중복 선택할 수 있는 순열을 생성하는 과정에서 백트래킹을 사용했다.

사용 예시

 

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++) {
        result.push_back(v[i]); // 현재 숫자 선택
        backtrack(depth + 1);   // 다음 숫자 선택 (재귀 호출)
        result.pop_back();      // 백트래킹 (이전 상태로 복구)
    }
}

• 현재 `depth`가 M이면 완성된 수열이므로 출력한다.
• 1부터 N까지의 숫자를 선택하고, `depth+1` 단계로 넘어간다.
• `result.pop_back();`을 수행하여 이전 상태로 되돌린다.

 

---

 

AI 피드백 : 완전 탐색을 활용한 구현

#include <iostream>  // 표준 입출력 사용 (cin, cout)
#include <vector>    // 벡터 자료구조 사용 (vector<int>)
#include <sstream>   // 문자열 스트림 사용 (ostringstream)

using namespace std;

int N, M;           // 입력으로 주어지는 자연수 N과 M
ostringstream out;  // 출력을 버퍼에 저장하여 성능을 최적화하는 스트림 객체

int main() {
    ios_base::sync_with_stdio(0); // 입출력 속도 최적화 (C 스타일 입출력과 동기화 해제)
    cin.tie(0); cout.tie(0);      // 입력과 출력을 분리하여 속도를 더 향상시킴

    // 사용자 입력 받기: N(1~N까지 숫자 사용), M(길이가 M인 수열 생성)
    cin >> N >> M;

    // M자리 수열을 표현할 벡터 (모든 자리 초기값을 1로 설정)
    vector<int> indices(M, 1);

    while (true) {
        // 현재 선택된 숫자들을 출력 스트림(out)에 저장
        for (int i = 0; i < M; i++)
            out << indices[i] << (i != M - 1 ? " " : "\n"); // 마지막 숫자 뒤에는 개행 추가

        // 가장 오른쪽 자리부터 증가시키면서 새로운 조합 생성
        int pos = M - 1;  // 맨 끝자리(index M-1)부터 증가시키기 시작
        while (pos >= 0 && indices[pos] == N) 
            pos--;  // 현재 자리의 숫자가 N이면, 그 앞자리(pos-1)를 변경

        // pos가 -1이면 모든 조합을 생성했으므로 종료
        if (pos < 0) break;

        indices[pos]++; // 현재 자릿수 값 증가

        // 증가한 자리(pos) 뒤쪽의 모든 숫자를 1로 초기화
        for (int i = pos + 1; i < M; i++) 
            indices[i] = 1;
    }

    // 한 번에 모든 출력을 수행하여 속도 향상
    cout << out.str();
    
    return 0;
}

 

 

사용한 핵심 개념

// 완전 탐색 (Brute Force)

• 모든 경우의 수를 전부 탐색하는 방식으로, 가능한 모든 선택지를 하나씩 나열하며 답을 찾는다.
• 이 문제에서는 `N^M`개의 경우의 수가 존재하며, 모든 경우를 직접 생성하여 출력하는 방식을 사용한다.
• 백트래킹을 사용하면 불필요한 탐색을 줄일 수 있지만, 이 코드에서는 반복문을 활용하여 단순하게 모든 경우의 수를 직접 생성하는 방식을 선택했다.

예제 (N=3, M=2)

입력값이 `N = 3`, `M = 2`라면, 가능한 모든 조합은:

 

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

이 조합을 순서대로 생성하는 것이 완전 탐색의 핵심이다.

 

• 코드에서 완전 탐색을 구현한 부분

while (true) {  // 모든 경우를 생성할 때까지 반복
    for (int i = 0; i < M; i++)
        out << indices[i] << (i != M - 1 ? " " : "\n");

    int pos = M - 1;
    while (pos >= 0 && indices[pos] == N) pos--;  // 더 증가할 수 있는 자리 찾기

    if (pos < 0) break;  // 모든 조합을 다 만들었으면 종료

    indices[pos]++;  // 증가할 수 있는 자리 증가
    for (int i = pos + 1; i < M; i++) indices[i] = 1;  // 이후 자리 초기화
}

조건을 만족하는지 확인하는 과정 없이 무조건 모든 경우를 출력하기 때문에 완전 탐색이 이루어지고 있다고 볼 수 있다.

 

 

// 사전순 탐색 (Lexicographic Order)

• 가장 작은 숫자부터 시작해서 사전순으로 증가하는 순서로 탐색하는 방법이다.
• 문제에서 사전순 증가 형태로 출력해야 하므로, 작은 수부터 증가하면서 새로운 조합을 만든다.
• `indices` 배열을 1부터 시작하고, 오른쪽 자리부터 숫자를 증가시키는 방식으로 구현한다.

예제 (N=3, M=2)

1. `{1,1}` → `{1,2}` → `{1,3}`
2. `{2,1}` → `{2,2}` → `{2,3}`
3. `{3,1}` → `{3,2}` → `{3,3}`

모든 조합이 사전순(오름차순)으로 정렬되어 탐색된다.

 

• 코드에서 사전순 탐색을 구현한 부분

for (int i = pos + 1; i < M; i++) indices[i] = 1;  // 증가한 자리 뒤를 1로 초기화

• 출력 순서가 작은 수에서 큰 수로 변한다.
• 반복문을 활용하여 증가된 자리 이후의 값들은 가장 작은 값(1)으로 다시 초기화되어 별도의 정렬 없이 사전순 정렬을 유지한다

 

// 자리값 조정 (Position Update)

• 숫자를 증가시키면서 모든 조합을 만들되, 오른쪽 자리부터 증가시키는 방식을 사용한다.
• 마지막 숫자가 N에 도달하면, 그 앞자리를 증가시키고 뒷자리는 다시 1로 초기화한다.

자리 증가 과정 (N=3, M=2)

1. `{1,1}` → `{1,2}` → `{1,3}` : 오른쪽 자리(두 번째 숫자)만 증가한다
2. `{2,1}` → `{2,2}` → `{2,3}` : 첫 번째 숫자를 증가시키고 두 번째 숫자는 1부터 다시 시작한다
3. `{3,1}` → `{3,2}` → `{3,3}` : 첫 번째 숫자가 N까지 도달하면 탐색을 종료한다

코드에서 자리값 조정을 구현한 부분

int pos = M - 1;
while (pos >= 0 && indices[pos] == N) pos--;  // 더 증가할 수 있는 자리 찾기

if (pos < 0) break;  // 모든 조합을 다 만들었으면 종료

indices[pos]++;  // 증가할 수 있는 자리 증가
for (int i = pos + 1; i < M; i++) indices[i] = 1;  // 이후 자리 초기화

오른쪽 자리부터 확인하여 N이면 앞자리를 증가시키고 뒤의 숫자를 초기화하여 증가 가능 여부를 판단한다.

 

 

// ostringstream를 활용한 입출력 최적화

`cout`을 여러 번 호출하는 것의 문제점

• `cout`을 사용하면 데이터가 한 번 출력될 때마다 버퍼를 flush(비우는 작업) 하게 된다.
• 즉, `cout`을 여러 번 호출하면 매번 버퍼를 비우면서 출력을 수행하므로 실행 속도가 느려진다.

 

예제 (비효율적인 출력)

for (int i = 0; i < M; i++) {
    cout << indices[i];  
    if (i != M - 1) cout << " ";
    else cout << "\n";
}

• 위 코드에서는 `cout`이 최소 M번 호출된다.
• 버퍼를 자주 flush하기 때문에 출력 성능이 저하된다.

 

`ostringstream`을 사용한 해결 방법

• `ostringstream`은 출력을 버퍼(메모리)에 저장해 두었다가, 한 번에 `cout`을 통해 출력할 수 있도록 도와준다.
• 출력 횟수를 최소화하여 성능을 향상시킨다.

 

예제 (`ostringstream`을 활용한 출력 최적화)

ostringstream out; // 출력 버퍼 선언

for (int i = 0; i < M; i++) {
    out << indices[i];  
    if (i != M - 1) out << " ";
    else out << "\n"; 
}

// 한 번에 출력 (여기서만 cout을 사용)
cout << out.str();

• 버퍼에 모든 출력 내용을 저장한 후, `cout`을 단 한 번 호출하여 출력한다.
• 출력 연산이 많을 때 성능이 크게 향상된다

 

---

 

백트래킹 (Backtracking) vs. 완전 탐색 (Brute Force)

(위) 완전 탐색 이용 / (아래) 백 트래킹 이

실행 결과에서 위는 완전 탐색을 이용한 코드의 결과이고, 아래는 백 트래킹으로 푼 코드의 결과이고, 위는 완전 탐색을 이용한 코드의 결과이다.

 

두 가지 접근법(백트래킹 vs. 완전 탐색)의 성능 차이가 크지 않은 이유는 입력 크기가 상대적으로 작기 때문이다.

그러나 입력 크기가 커질수록, 두 방식의 차이가 더욱 두드러지게 나타난다고 한다.

 

 

실행 결과 분석

// 메모리 사용량

• 백트래킹 (2020 KB)이 완전 탐색 (29844 KB)보다 훨씬 적은 메모리를 사용함.
• 완전 탐색은 모든 경우를 직접 메모리에 저장하거나 탐색해야 하므로, 메모리 소비가 더 큼.

// 실행 시간

• 백트래킹 (296 ms)이 완전 탐색 (240 ms)보다 약간 더 느리지만, 차이가 크지 않음.
• 백트래킹이 불필요한 탐색을 줄여 최적화할 수 있지만, 이번 경우에는 탐색 공간이 작아 최적화 효과가 크지 않았음.

 

언제 어떤 방식을 사용해야 할까?

// 백트래킹이 유용한 경우

1. 탐색 공간이 큰 경우 (N이 크고 M이 클 때)
   • 예제에서는 N, M이 상대적으로 작아서 완전 탐색도 효율적이었지만, N = 10, M = 5 이상이 되면 완전 탐색은 기하급수적으로 시간이 증가하게 된다.
   • 백트래킹은 탐색 중 불필요한 경우를 가지치기(Pruning)하면서 탐색 공간을 줄일 수 있다.
2. 순열(Permutation)이나 조합(Combination)을 구할 때
   • 특정 조건을 만족하는 경우만 선택해야 하는 경우 (예: 중복 없이 M개 선택)
     • 완전 탐색은 모든 경우를 탐색하기 때문에 불필요한 탐색이 많아질 수 있다.
3. DFS(깊이 우선 탐색, Depth-First Search)와 결합할 때
   • 그래프 탐색에서 특정 조건을 만족하는 경로를 찾을 때 (예: 미로 탐색)
     • 백트래킹을 사용하면 불필요한 경로를 미리 배제하여 성능을 개선할 수 있다

// 완전 탐색이 유용한 경우

1. 탐색 공간이 작고 단순한 경우 (N, M이 작을 때)
   
   • 작은 경우의 수를 탐색하는 문제에서는 완전 탐색이 더 직관적이고 빠를 수 있다.
     • 이 문제에서는 N과 M이 작아 완전 탐색도 충분히 빠르게 실행될 수 있었다.
     •  
2. 모든 경우를 반드시 탐색해야 하는 경우
   • 가지치기를 하더라도 모든 경우를 탐색해야 정답을 구할 수 있는 경우
     • 이 문제처럼 M개를 선택하는 모든 가능한 조합을 순서대로 출력해야 하는 문제라면 완전 탐색이 적합하다.
3. 구현이 쉬운 경우
   • 백트래킹을 적용할 수 있지만, 완전 탐색으로도 시간 내 해결 가능하다면 구현이 더 쉬운 완전 탐색이 유리하다.
     • 이 문제의 경우 반복문을 통해 해결하는 방식이 복잡하지 않기 때문에 완전 탐색도 실용적이었다.

 

방식	개념	장점	단점	언제 유용한가
백트래킹	가능한 모든 경우를 탐색하되, 불필요한 탐색을 가지치기(Pruning)하여 최적화	* 메모리 사용이 적다 * 탐색 공간을 줄여 속도가 빠를 가능성이 높다	일부 경우에는 백트래킹을 활용해도 최적화 효과가 크지 않을 수 있다	탐색 공간이 크고, 가지치기가 가능한 경우 (예: 순열, 조합 문제)
완전 탐색	모든 경우의 수를 전부 생성하여 확인	* 구현이 쉽고 직관적이다  * 모든 경우를 고려하므로 실수 가능성이 적다	* 탐색 공간이 크면 비효율적이다 * 메모리 사용량이 많다	탐색 공간이 작거나, 모든 경우를 반드시 탐색해야 하는 문제 (예: 조합 생성)

 

즉, 문제의 입력 크기와 요구 사항에 따라 적절한 탐색 방법을 선택하여 풀면 된다