[알고리즘] 백준 15663 c++

문제 링크

15663번: N과 M (9)

틀린이유

• 백트래킹의 본질 생각 못 함
• 중복 수열이 안된다길래 Set 자료구조 생각했는데 그러면 중복으로 나온 수, 그리고 그 수가 몇 번 나왔는 지 새는 변수가 따로 또 필요했음
• 생각해야하는 경우의 수가 너무 많아 이 방법이 아니라고 판단함

문제 분석

문제

• N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 구하라
  • N개의 자연수 중에서 M개를 고른 수열

입력

• 1 ≤ M ≤ N ≤ 8
• 입력으로 주어지는 수 ≤ 10,000
• 입력으로 주어지는 수 중복으로 주어질 수 있음

출력

• 중복되는 수열은 여러 번 출력하면 안된다
• 수열은 사전 순으로 증가하는 순서로 출력해야 한다

해결방안

• 중복 수열이라는 것을 어떻게 체크할 수 있을까?
• 이전 수열의 마지막 항과 새로운 수열의 마지막 항이 같으면 중복 수열
  • 어떻게? 백트래킹!
  • 1 2 → 1 2 3 → 1 2 → 1 2 4 → …
  • 이런 순서가 되기 때문에 같은 Level에서 check

코드

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

int N, M;
int input[10];
int ans[10];
bool isUsed[10];

void func(int L){
    if (L == M){
        for (int i=0; i<M; i++) cout << ans[i] << ' ';
        cout << '\n';
        return;
    }

    int tmp = 0;
    for (int i=0; i<N; i++){
        if (!isUsed[i] && tmp != input[i]){
            ans[L] = input[i];
            tmp = input[i];
            isUsed[i] = true;
            func(L+1);
            isUsed[i] = false;
        }
    }
}

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

    cin >> N >> M;
    for (int i=0; i<N; i++) cin >> input[i];
    sort(input, input+N);
    for (int i=0; i<N; i++) cout << input[i] << ' ';
    cout << '\n';
    func(0);

    return 0;
}

공부과정

사실 나는 답 코드를 보고 한번에 tmp 변수가 어떻게 저장되고 어떻게 사용되는 지 이해하지 못했다.
그래서 먼저 재귀함수가 Stack 메모리에 어떻게 들어가는지 찾아보았다.

위 그림은 대표적인 재귀함수인 factorial 함수가 stack 메모리에 들어가는 과정이다.
이를 통해 해당 문제의 tmp 변수는 func함수가 불릴 때마다 독립적인 새 변수 주소로 할당되는 것을 알 수 있었다. 즉, tmp변수는 같은 Level에서만 유효하고 다음 Level로 넘어가면 tmp=0으로 초기화된 새로운 변수에서 시작되는 것이다.

따라서 tmp 변수가 input[i] 값을 저장한 이유는 같은 Level에서 중복 수열을 만들지 않기 위해서이다. input 수열을 오름차순으로 정렬했기 때문에 같은 값을 갖는 수가 있다면 바로 옆에 위치할 것이다. tmp값이 이전 수열의 마지막 항을 저장하고 있으므로 같은 Level에서 check하면 중복 수열을 만들지 않게 되는 것이다.