[Algorithm] 백준 - N과 M (10) (15664번)

문제

[백준] N과 M (10)

사용 알고리즘

- 백트래킹 (BackTracking)

해결방법

• 주어진 수열을 백트래킹을 통해 탐색하면서, 부분 집합의 개수가 M이 된 경우만 집합에 담는다.
• 오름차순 정렬

소스코드

사용언어 : c++

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
 
using namespace std;
 
int N, M;
set<vector<int>> unique_row; // 부분 수열을 저장할 집합
 
// 백트래킹을 이용하여 부분 수열 생성
void generateSubsequences(vector<int>& sequence, vector<int>& current, int index) {
    if (index == sequence.size()){
        if (current.size() == M) {
            vector<int> temp;
            for (int num : current) {
                temp.push_back(num);
            }

            sort(temp.begin(), temp.end()); // 오름차순 정렬
            unique_row.insert(temp);
        }
        return;
    }
 
    // 현재 원소를 선택하지 않고 다음 원소로 이동
    generateSubsequences(sequence, current, index + 1);
 
    // 현재 원소를 선택하고 다음 원소로 이동
    current.push_back(sequence[index]);
    generateSubsequences(sequence, current, index + 1);
 
    // 백트래킹을 위해 선택한 원소 제거
    current.pop_back();
}
 
int main() {
    vector<int> sequence;
    vector<int> current;
 
    cin >> N >> M;
 
    int num;
    for (int i=0; i<N; i++) {
        cin >> num;
        sequence.push_back(num);
    }
 
    generateSubsequences(sequence, current, 0);
 
    for (const auto& row : unique_row) {
        for (int v : row) {
            cout << v << " ";
        }
        cout << endl;
    }
 
    return 0;
}

set / unordered_set

• set
  • 집합으로, 중복원소가 존재하지 않다.
  • O(logN)
  • 기본적으로 오름차순 정렬이다
  • set<T> 으로 선언한다. T는 자료형
  • insert(), erase(), clear(), find(), count(), empty(), size() 제공
• unordered_set
  • Hash 자료구조로 구현되어 있다.
  • O(1)
  • set과 다르게 정렬되지 않는다.

 

 

람다함수

* [capture](parameters) => return_type {

//함수 본문

}

• c++11 부터 람다 함수 가능
• capture : 외부 변수를 담아 람다 함수 내에서 사용할 수 있게 해줌
• parameters : 함수의 매개변수를 저장
• retury_type : 함수의 반환 타입을 지정

 

한줄평

백트래킹으로 부분 수열을 구했던 지난 문제와 매우 유사한 문제이다.