BOJ 15649 - N과 M (1) (C++) / Team Fortune Drill Week1

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

문제를 푼 날짜: 2025. 04. 08

#backtracking

최초 풀이

#include <iostream>
#include <vector>
using namespace std;


int N, M;
void bruteForce(vector<int> selected, int left_num); // selected: 현재 고른 순열, left_num: 더 골라야하는 개수

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    vector<int> v;

    bruteForce(v, M);
    return 0;
}

void bruteForce(vector<int> selected, int left_num){
    //기저사례
    if(left_num == 0){
        for(auto& element : selected){
            cout << element << ' ';
        }
        cout << '\n';
    }
    for(int i = 1; i <= N; i++){
        bool exist = false;
        for(auto itr = selected.begin(); itr != selected.end(); ++itr){
            if(*itr == i){
                exist = true;
                break;
            }
        }
        if(exist == false){
            selected.push_back(i);
            bruteForce(selected, left_num - 1);
            selected.pop_back();
        }
    }
}

개선된 풀이

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<bool> visited; // 1부터 N까지 사용 여부를 저장 (인덱스 1부터 사용)

void bruteForce(vector<int>& permutation, int depth) {
    if (depth == M) { // 기저사례: M개가 골라진 경우
        for (int num : permutation) {
            cout << num << ' ';
        }
        cout << '\n';
        return;
    }
    // 1부터 N까지 순서대로 탐색 (사전순 증가)
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) { // 사용되지 않은 원소인 경우
            visited[i] = true;
            permutation.push_back(i);
            bruteForce(permutation, depth + 1);
            permutation.pop_back();  // 백트래킹: 마지막 원소 제거
            visited[i] = false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    visited.assign(N + 1, false);  // N개 숫자를 위해 false로 초기화
    vector<int> permutation;       // 현재까지 골라진 순열을 저장할 벡터

    bruteForce(permutation, 0);
    return 0;
}

📌 1. 문제 접근 및 이해

• 문제 유형: 백트래킹을 이용해 1부터 N까지 숫자 중 중복 없이 M개를 선택하는 순열 생성 문제
• 핵심 요구사항:
  • 모든 수열은 중복 없이 선택되어야 하며
  • 사전순으로 증가하는 순서로 출력되어야 한다

---

🧠 2. 구현 시 배운 점

✅ 백트래킹의 기본 패턴

• 재귀 호출을 이용해 가능한 모든 경우를 탐색하는 방식
• 기저사례(base case)를 명확히 정의하고, 조건에 따라 출력을 수행

✅ 중복 검사 기법

• 기존 코드에서는 매 호출마다 vector 내부를 순회하며 O(M) 시간으로 중복 여부를 검사
• 개선된 방식에서는 visited 배열을 사용하여 O(1) 시간에 중복 여부 확인 가능

✅ 참조 전달의 중요성

• 기존 코드에서는 vector<int>를 값으로 전달(pass-by-value) → 호출마다 복사 비용 발생
• 개선된 코드에서는 참조(pass-by-reference) 로 전달하고, 호출 후에는 pop_back()으로 상태 복원 → 메모리 효율 및 속도 향상

✅ 코드 가독성과 유지보수성

• 변수명은 의미가 명확해야 가독성이 좋아짐
  예: selected → permutation
• 함수 인자도 문제의 의미와 로직 흐름을 잘 드러내도록 네이밍

---

⏱️ 3. 시간복잡도 측면에서의 피드백

❌ 기존 방식

• 순열의 총 개수:
  $P(N, M) = \frac{N!}{(N - M)!}$
• 각 호출마다 중복 확인: $O(M)$
• 총 시간복잡도:
  $O\left( \frac{N!}{(N - M)!} \times N \times M \right)$

✅ visited 배열을 사용한 개선 방식

• 중복 확인: O(1)
• 총 시간복잡도:
  $O\left( \frac{N!}{(N - M)!} \times N \right)$

---

✅ 결론 및 얻어가야 할 점

• 문제 해결 역량
  백트래킹 문제의 기본 패턴을 충분히 익히고, visited 배열을 활용한 효율적인 중복 제거 방식 이해

• 효율성과 가독성 모두 중요

  • 알고리즘 효율성: 중복 제거 비용 최소화
  • 코드 품질: 의미 있는 변수명, 함수 분리, 참조 전달 등 실무적인 작성 습관 강화

• 작은 최적화의 힘
  불필요한 복사 제거, O(M) → O(1) 개선 등 작은 변화가 전체 성능에 끼치는 영향 체감

---