백준: N과 M〈1〉(15649번)

알고리즘 문제 해결 과정을 기록합니다

September 23, 2025 · 2 min read

#알고리즘 #문제해결

문제 개요 #

Source: 백준 링크
Difficulty: Silver 3
Key Concept: 백트래킹

접근 방법 #

해당 문제는 std::next_permutation과 std::set을 이용해서 길이가 m인 순열을 std::set에 넣어 중복을 제거하는 로직으로 처음 접근하였습니다.

시행착오 #

std::next_permutation을 이용하여 전체 숫자가 아닌 일부만 이용하는 로직을 헷갈려 다시 std::next_permutation 구현을 보면서 학습했습니다.¹

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    auto r_first = std::make_reverse_iterator(last);
    auto r_last = std::make_reverse_iterator(first);
    auto left = std::is_sorted_until(r_first, r_last);

    if (left != r_last)
    {
        auto right = std::upper_bound(r_first, left, *left);
        std::iter_swap(left, right);
    }

    std::reverse(left.base(), last);
    return left != r_last여
}

std::upper_bound는 이전 N-Queen 문제에서 사용된 std::lower_bound와 반대되는 로직으로 해당 값 이상이 되는 값의 위치를 가리키는 iterator를 반환합니다. std::is_sorted_until은 첫번째 매개변수 위치와 두 번째 매개변수 위치 사이에서 비내림차순이 유지되는 마지막 위치를 리턴합니다.²

이후 비내림차순 순열의 가장 큰 값(left)값이 마지막 값이 아니라면, 즉 전체 수열이 이미 비내림차순으로 정렬되어 있지 않았다면 left가 가리키는 값보다 큰 값중 최소값을 선택한 다음 right로 할당합니다. 이 때 left를 pivot이라 할 수 있습니다. pivot은 뒤에서부터 내림차순이 끝나는 원소를 가리키며 이는 바꾸어야 할 최소 위치를 의미합니다.

left와 right를 바꾼다음 교체된 left 뒷 부분을 std::reverse로 정렬합니다. 이러한 로직을 이용하여 오름차순으로 정렬된 수열을 넣어주면 사전순으로 구성된 수열들을 얻을 수 있습니다.

해결 방법 #

vector<vector<int>> solution() {
    int n, m;
    std::cin >> n >> m;
    // 길이가 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
    vector<int> num(n);
    set<vector<int>> s;
    for (int i = 0; i < n; i++) {
        num[i] = i + 1;
    }
    do {
        vector<int> temp;
        for (int i = 0; i < m; i++) {
            temp.emplace_back(num[i]);
        }
        s.insert(temp);
    } while (std::next_permutation(num.begin(), num.end()));
    vector<vector<int>> answer;
    for(const vector<int>& v: s){
        answer.emplace_back(v);
    }
    return answer;
}

알고리즘 설명 #

std::set을 이용하여 중복 수열들을 제거하는 방식을 사용하였습니다. 앞서 설명했듯이 std::next_permutation을 이용하여 순열들을 사전순으로 생성되게 한 다음 길이가 m이 된 이후에는 끊고 set에 넣어 보관하도록 하였습니다. 이후 set에 담긴 중복되지 않은 길이가 m인 순열들의 집합을 모두 vector로 옮겨 리턴하였습니다.

성능 분석 #

Time Complexity: $O(N!\times M)$

std::next_permutation의 경우 $O(N!)$의 시간복잡도를 가지고 M개씩 복사하는데 또 $O(M)$이 걸리므로 매우 비효율적이지만 N과 M의 크기가 8이하라는 조건이 있어서 해당 문제의 시간 제한 조건을 맞출 수 있었습니다.

핵심 정리 #

std::next_permutation의 구현 코드를 자세히 살펴볼 기회가 없었는데 해당 문제를 풀 때 그 기회를 가질 수 있어 순열 생성의 방식을 더 깊게 이해할 수 있었습니다. 또한 iterator와 관련된 여러 코드들을 보면서 STL 구조에서의 iterator의 사용 방식에 대해서도 고민해볼 수 있었습니다.

Pelikan's Glide