백준 15652: N과 M (4)

백트래킹 알고리즘을 이해하고 구현해보았습니다.

1. 문제 소개

문제 번호: 15652
문제명: N과 M (4)
난이도 (티어): Silver III
사용 언어: C++
실행 시간: 4 ms
메모리: 2020 KB
문제 요약:
1부터 N까지 자연수 중에서 중복을 허용하여 M개를 고른 수열을 모두 구하는 문제입니다. 이때, 고른 수열은 비내림차순이어야 합니다. (예: 1 1 2, 1 2 2, 2 2 2)

2. 접근 방법

이 문제는 "순열" 혹은 "조합"과 유사한 형태를 띠지만, "중복 허용"과 "비내림차순"이라는 조건이 붙어있습니다. 이러한 종류의 문제는 백트래킹(Backtracking) 알고리즘을 사용하여 해결하는 것이 일반적입니다.

어떤 알고리즘/자료구조를 사용했는지: 백트래킹 알고리즘과 std::vector를 사용하여 수열을 저장했습니다.
왜 이 방법을 선택했는지:
- 중복 허용: 같은 숫자를 여러 번 선택할 수 있습니다.
- 비내림차순: 현재 선택하는 숫자는 이전에 선택한 숫자보다 같거나 커야 합니다.
- 이러한 조건들을 만족하는 모든 경우의 수를 탐색해야 하므로, 모든 가능한 조합을 생성하고 조건을 검사하는 백트래킹 방식이 적합합니다. std::vector는 동적으로 크기가 변하는 수열을 다루기에 편리합니다.

3. 풀이 과정

백트래킹은 특정 상태에서 가능한 모든 경우를 탐색하다가, 조건에 맞지 않으면 되돌아가서 다른 경우를 탐색하는 방식입니다. "N과 M (4)" 문제에서는 다음과 같은 과정을 거칩니다.

재귀 함수 정의: dfs(int start) 와 같이 현재 탐색을 시작할 숫자를 인자로 받는 재귀 함수를 만듭니다. start 매개변수는 비내림차순 조건을 유지하기 위해 사용됩니다.
종료 조건: seq.size() == M 이라는 것은 M개의 숫자를 모두 골랐다는 의미입니다. 이 때, 현재까지 만들어진 수열 seq를 출력하고 함수를 종료합니다.
탐색 (순회): for (int i = start; i <= N; i++) 루프를 통해 start부터 N까지의 숫자 중 하나를 현재 단계에서 선택합니다.
- 선택: seq.push_back(i)를 통해 현재 숫자 i를 수열에 추가합니다.
- 재귀 호출: dfs(i)를 호출하여 다음 숫자를 선택합니다. 여기서 가장 중요한 부분은 다음 재귀 호출 시 start 대신 i를 넘겨준다는 점입니다. 이는 다음 숫자가 현재 선택한 숫자 i와 같거나 커야 한다는 비내림차순 조건을 만족시키기 위함이며, 동시에 중복을 허용합니다.
- 되돌아가기 (Backtrack): seq.pop_back()을 통해 현재 선택했던 숫자 i를 수열에서 제거합니다. 이는 이전 상태로 돌아가 다른 숫자를 선택해볼 기회를 제공합니다.

핵심 아이디어:
dfs(i) 호출 시 i를 그대로 넘겨주는 것이 중복 허용 및 비내림차순 조건을 동시에 만족시키는 핵심입니다.

주의할 점:

start 값을 제대로 설정하지 않으면 비내림차순 조건을 위반하거나, 불필요한 탐색이 발생할 수 있습니다.
seq.pop_back()을 잊지 않고 호출하여 백트래킹이 제대로 이루어지도록 해야 합니다.

4. 코드 설명

아래는 제공된 JSON 데이터에 포함된 C++ 코드입니다. 이 코드를 그대로 사용하며, 각 부분에 대한 설명을 덧붙이겠습니다.

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

int N, M;
vector<int> seq;

void dfs(int start) {
    // M개의 숫자를 모두 골랐다면, 수열을 출력하고 재귀를 종료합니다.
    if (seq.size() == M) {
        for (int x : seq) cout << x << ' ';
        cout << '\n';
        return;
    }

    // start부터 N까지의 숫자 중에서 다음 숫자를 선택합니다.
    // 'start'부터 시작하는 이유는 이전 숫자보다 작아지지 않도록 (비내림차순) 하기 위함입니다.
    for (int i = start; i <= N; i++) {
        seq.push_back(i); // 현재 숫자 i를 수열에 추가합니다.
        dfs(i);           // ★ 중복 허용 및 비내림차순 유지 → 다음 탐색 시작점을 현재 숫자 i로 지정합니다.
        seq.pop_back();   // 백트래킹: 현재 숫자 i를 수열에서 제거하여 이전 상태로 돌아갑니다.
    }
}

int main() {
    // N과 M 값을 입력받습니다.
    cin >> N >> M;
    // 1부터 시작하여 DFS 탐색을 시작합니다.
    dfs(1);
}

5. 복잡도 분석

시간 복잡도:
이 문제는 비복원 추출을 하는 조합과는 달리, 중복을 허용하며 순서가 있는 수열을 생성합니다. 각 자리마다 N가지의 선택지가 있고, M개의 자리가 있다고 단순하게 생각하면 O(N^M)이 될 수 있습니다.
하지만 비내림차순 조건 때문에 실제로는 이보다 적은 경우의 수만 탐색하게 됩니다. 좀 더 정확하게는, 중복을 허용하는 M개의 요소를 N개 중에서 선택하는 경우의 수는 H(N, M) = C(N+M-1, M)으로 계산될 수 있습니다. 백트래킹은 이러한 경우의 수들을 모두 생성하므로, 시간 복잡도는 대략 O(H(N, M)) 또는 O(C(N+M-1, M)) 입니다.
공간 복잡도:
재귀 호출 스택 깊이는 최대 M이 될 수 있으며, seq 벡터 또한 최대 M개의 요소를 저장하므로 공간 복잡도는 O(M) 입니다.

6. 배운 점

"N과 M (4)" 문제를 풀면서 백트래킹의 유연성을 다시 한번 느꼈습니다. 특히, dfs 함수 호출 시 start 매개변수의 역할을 통해 중복 허용과 **순서 조건(비내림차순)**을 동시에 만족시키는 방법을 효과적으로 구현할 수 있었습니다.

중복 허용: 다음 탐색에서 이전 선택과 같은 값을 다시 선택할 수 있도록 dfs(i)와 같이 현재 선택 값을 그대로 전달합니다.
순서 조건 (비내림차순): 다음 탐색에서 이전 선택 값 i보다 작거나 같은 값만 선택하도록 dfs(i) 호출 시 i를 start 값으로 넘겨줍니다.

이러한 백트래킹 기법은 다양한 조합, 순열, 부분집합 생성 문제에 응용될 수 있으므로, dfs 함수의 인자와 재귀 호출 방식을 잘 이해하는 것이 중요합니다.

이번 포스팅이 "N과 M (4)" 문제를 이해하는 데 도움이 되었기를 바랍니다. 다음 문제 풀이에서 또 만나요!