백준 15654 N과M (5) C++ 풀이 (무조건 이해시켜드림)

안녕하세요~ 여러분~

프루니입니다^___^

 

오늘 풀어볼 문제는 백준 15654번 N과M (5) 문제입니다.

언어는 C++입니다~

 

N과M 시리즈에서 4번째까지는 거의 비슷했는데

이 문제에서는 입력받는 것이 추가되었더라구요 ??

작은 변화 덕분에(?) 지루하지두 않구 좋더라구용 ㅎㅎ

 

자 그럼 문제 마스터하러 가주아~~!!!!!!!!!!!!!!!

 

---

문제

 

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

---

입력

 

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

---

출력

 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

---

프루니의 풀이

사용 언어 : C++

사용 알고리즘 : 브루트포스

 

문제 해석

입력받은 N개의 숫자 중에 M개를 뽑아 나열하는 순열 문제입니다. 중복은 허용하지 않습니다.

이 문제는 모든 경우를 모두 출력해야하기 때문에 브루트포스를 사용해야 합니다.

 

!여기서 잠깐! 호옥시 브루트포스에 대해 모르시는 분들이 있다면 보세용! (사실 제가 몰랐어용 히히)

 

브루트포스가 뭐죵?

브루트포스는 모든 경우를 하나도 빠짐없이 직접 다 실행하는 것이랍니다!

 

나무위키에 따르면

"브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다." 라고 합니다!

 

모든 경우를 다 돌아봐야 하는 문제라면 브루트포스 알고리즘을 쓰면 되겠어용!

 

문제 풀이

자 해당 문제를 브루트포스를 사용하여 코드로 구현하는 방식은 두가지 입니다.

첫번째는 재귀, 두번째는 반복문이에요~

프루니는 재귀를 선호하여 재귀함수로 구현했어요!

하지만 반복문을 원하시는 분들이 계시다면 반복문으로도 구현하여 올릴게요!! 댓글로 요청주세요~ 바아로 갑니다!

 

일단 재귀든 반복문이든 문제를 해결하기 위해 진행되는 흐름은 같아요!

M개의 숫자를 뽑을 때마다 출력하는 동작을 경우의 수가 끝날때까지 반복하면 된답니다!

아래 그림은 M개의 숫자를 뽑는 루틴을 표현한 그림이에요~

 

 

위 패턴을 코드로 구현하기 위해 먼저 배열 2개과 벡터 1개가 필요해요!

 

첫번째 배열은 어떤 숫자가 이미 뽑았던 숫자인지 아닌지를 저장하고 있는 bool형 배열이고

두번째 배열은 지금까지 뽑은 숫자를 저장하고 있는 int형 배열이에요~

벡터는 int형 벡터로 입력받은 N개의 숫자를 저장하는 벡터랍니다!(배열을 사용해도 되지만 벡터를 사용한 이유는 사전순서 출력을 위해 sort 알고리즘을 쓰기 위해서에요!! 귀차니즘 ㅎㅎ)

 

프루니는 첫번째 배열 이름을 visited, 두번째 배열이름을 sequence, 입력받은 숫자를 저장하는 벡터 이름은 numbers로 설정했어요~

 

visited는 처음에 모든 요소가 false로 초기화 되어있고 뽑힌 숫자에 해당하는 요소는 true로 설정해준답니다!

sequence에는 현재 뽑은 숫자를 추가해주면 되어요~

 

자 이제 코드를 볼게요~ 

 

재귀로 구현한 코드!

주석으로 설명할게요~

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 10001

vector<int> numbers;
bool visited[9];
int sequence[MAX];
int N, M;

//재귀함수
//매개변수 cnt는 현재 뽑아야하는 숫자의 순번이에요! 
//이미 2개를 뽑았고 3번째 숫자를 뽑을 차례라면 cnt에 3을 넣어 함수를 호출하면 됩니다!
void DFS(int cnt)
{
    //재귀함수 탈출조건 : m개 다 뽑을 때 출력 후 return
    if (cnt == M)
    {
        for (int i = 0; i < M; ++i)
        {
            cout << sequence[i] << ' ';
        }
        cout << '\n';
        return;
    }

    //1~N까지의 숫자를 모두 돌며 각 숫자가 이미 뽑힌 숫자인지 검사하고 뽑힌적없는 숫자이면 뽑는 반복문입니다~
    for (int i = 1; i <= N; ++i)
    {
        if (!visited[i]) // numbers의 i번째 요소를 뽑은 적이 있는지 확인하고 뽑은적이 없을때만 추가해요!
        {
            sequence[cnt] = numbers[i]; // 현재 뽑고있는 순서의 숫자로 numbers의 i번째 요소를 추가해요!
            visited[i] = true; // numbers의 i번째 요소를 뽑았기 때문에 뽑았다는 표시로 visited의 i번째 요소를 true로 설정해요~
            DFS(cnt + 1); // M개의 숫자 중에서 cnt번째 숫자까지 뽑았으니까 그다음 숫자인 cnt+1번째 숫자를 뽑기위해 cnt+1을 매개변수로 DFS함수를 호출해요
            visited[i] = false; // 바로 위 코드인 DFS함수가 한번 끝나고 돌아왔기 때문에 그다음 M개의 숫자를 새로 뽑기전에 뽑았던 기록을 모두 false로 초기화해요!
        }
    }
}

int main()
{
    cin >> N >> M; // N, M을 입력받아요~

    int num = 0;
    numbers.push_back(num);
    for (int i = 1; i <= N; ++i) // N개의 숫자를 입력받고 numbers에 저장해요~
    {
        cin >> num;
        numbers.push_back(num);
    }

    sort(numbers.begin(), numbers.end()); // 문제에서 출력할때 사전 순서로 출력해야한다는 조건이 있기때문에 입력받은 숫자를 미리 오름차순으로 정렬해놔요~
    
    DFS(0); // 재귀함수 시작!
    return 0;
}

 

자! 아까 브루트포스로 푼다면서 갑짜기!!!!! DFS라는 단어가 등장해서 어이가 없는 분들을 위해 설명을 드리자면!!! 

 

DFS는 한번 방문했던(뽑았던) 숫자에는 다시는 방문하지 않기 때문에 visited배열의 요소가 true로 설정되는 순간 다시 false로 변경되는 경우가 없이 그것으로 끝이랍니다!

하지만 이 코드에서는 DFS처럼 visited배열의 요소를 true로 설정한 후, DFS에서 탈출 조건을 만족하여 return되고 다시 DFS함수가 호출되기전에!! visited배열의 요소를 false로 되돌려주는 코드가 있어요!!!!!!!!!!!

닫기

 visited[i] = false;

바로 이것!!

 

따라서 M개의 숫자를 모두 뽑은 후 출력하고, 또다른 경우의 M개의 숫자를 뽑을때 visited 배열의 요소가 모두 false가 되어 또 뽑힐 수 있답니다! 그래서 모든 경우의 수를 모두 도는 브루트포스가 되는 것이에요!!!

 

끗!

---

 

후 여러분 고생많으셨어요~

이해가 되셨다면 공감버튼 한번씩 눌러주세요(꾸벅)

이해가 안되셨다면 댓글로 질문해주세요!!! 바아로 갑니다.

 

될때까지 하면 됩니다.

반드시 뿌십시다!!

 

자 그럼 저는 또 다음 문제를 가지고 올게요~ 

안녕~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~