AlgorithmBOJ

백준 암호만들기 1759

,

1. 백준암호만들기1759

2. 컴퓨팅 스킬

  • Recursive를 활용한 풀이 백트래킹 두가지 방법으로 풀겠습니다.
  • include헤더에 sort함수를 사용하겠습니다. 그 이유는 사전식으로 가능성 있는 암호를 모두 출력한다. 라는 조건이 있기 때문입니다.

3. 컴퓨팅 사고

  • 조합의 방식으로 풀어야합니다. 어떻게 조합으로 풀어야된다는 생각을 하였을까요? 문자의 종류는 C가지, 암호는 서로 다른 L개의 알파벳 소문자들로 구성된다고 문제에 나와있다. 이것이 뜻하는 바는 바로 C개의 문자중 L개를 뽑는 방식이다 결국 조합을 나타내는 문제라는 것입니다.

  • 백트래킹을 푸는 방식은 두가지 방법이 있습니다. 개인마다 풀이의 차이이긴 하나 개인적으로 1번풀이로 진행합니다.

  1. vector와 check변수를 활용한 풀이
  2. vector 알파벳을 선택하는 recursive(), 알파벳을 선택하지 않는 recursive()

  • 재귀함수 호출시 idx변수와 cnt변수를 사용합니다. Idx변수는 시작점을 결정해주는 변수, cnt는 몇 개를 뽑아야하는지 그리고 재귀 호출 종료 해당 basement 조건이 됩니다.

  • 그리고, 조합은 순열과 다르게 해당 지정된 idx값 이하의 값들은 구성하지 않습니다. 예를 들어, 123 213 312 는 모두 동일한 경우로 생각합니다. 조합을 구현하기 위해서는 check배열변수와 알파벳을 담기위한 vector를 선언합니다.

  • 해당값이 사용되었더라면 check[i] == true로 확인하여 continue를 진행합니다. 그리고 나서 다음 반복문 수가 진행되면서 해당값이 사용되지 않았다면 해당 값을 check=true를 진행하고, vector에 해당되는 알파벳을 push_back을 해주게됩니다. 그리고나서 재귀호출을 하면서 cnt+1의 값을 해주며 idx의 값은 i의 값을 넣어주면서 진행합니다. cnt값은 내가 고를 값이며, idx의 값은 해당 기준이 되는 값이기때문에 반복문을 돌면서 해당값에 대한 재귀호출을 반복하게 하게됩니다.

  • 만약 cnt의 값이 내가 구하고자하는 n의 값과 같다면 해당 경우를 구한것이기 때문에 실질적인 로직을 작성합니다.

  • 알파벳은 자음 21가지, 모음 [a,e,i,o,u] 5가지로 구성됩니다. 따라서, push_back으로 넣었던 vector의 값을 하나씩 꺼내면서 해당 알파벳이 [a,e,i,o,u]중에 하나 일 경우 모음에 대한 개수를 증가시켜주고, 이와반대로 자음일 경우 자음의 개수를 증가시켜줍니다.

  • 모음의 개수는 1이상이여야하고, 자음의 개수는 2이상이여야합니다. 만약 이 해당되는 조건에 만족한다면 해당 vector에 있는 값을 모두 출력시켜주게 됩니다.

  • 그리고, Return값으로 해당 재귀함수가 종료되고나서 check=false로 방문을 해제시키고, 마지막에 들어있던 벡터값도 빼주게 됩니다. 그리고나서 다음에 해당하는 경우의 수로 재귀함수가 호출되면서 조합에 대한 모든경우를 구할 수 있게됩니다.

  • idx변수는 해당 기준이 되는점이고, cnt는 해당종료 조건(몇개를 뽑을지 조건)입니다.

  • 2번 백트래킹방식으로 사용할 경우 선택한 경우, 선택하지 않은경우를 cnt값을 더해주는지 안더해주는지 경우로 나누어서 재귀호출이 진행되게 됩니다. 2번방식은 개인적으로 직관적인 판단하기가 힘들고 1번방식이 직관적인 이해가 더 쉬웠습니다.

  • 조합과 반대로 순열은 idx변수가 사라지게 됩니다. 왜냐하면 기준이 되는점을 확인해야합니다. 예를 들어서 [1,2,3,4,5] [2,1,3,4,5]는 조합과 다르게 다른경우의 수로 나타냅니다. 조합은 저것을 하나의 경우의수로 판단하기 때문입니다. 그리고 순열은 idx를 사용하지 않으므로 해당되는 모든값에 첫번째 값부터 다시 확인을 진행한다는 차이점이 있습니다.

3.1. DFS 백트래킹 1번 방식

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
using namespace std;
bool check[15];
vector<char> str;
void dfs(vector<char> v, int m, int n, int idx, int cnt){
    
    if(cnt == n){
        int ja = 0;
        int mo = 0;
        for(int i=0; i<str.size(); i++){
            
            if(str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' ||str[i] == 'u'){
                mo +=1;
            }else{
                ja +=1;
            }
        }
        
        if(mo >=1 && ja >= 2){
            for(int i=0; i<str.size(); i++){
                cout << str[i];
            }
            cout << '\n';
        }
        return;
    }
    if(idx == v.size()){
        return;
    }

    for(int i=idx; i<v.size(); i++){
        if(check[i] == true){
            continue;
        }
        check[i] = true;
        str.push_back(v[i]);
        dfs(v,m,n,i,cnt+1);
        str.pop_back();
        check[i] = false;
        
    }
}
int main(void){
    int n = 0;
    int m = 0;
    cin >> n >> m;
    vector<char> v(m);
    for(int i=0; i<m; i++){
        cin >> v[i];
    }
        
    sort(v.begin(),v.end());
    dfs(v,m,n,0,0);
    return 0;

}

3.2. DFS 백트래킹 2번방식

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
void dfs(vector<char> v, int n, int m, string str, int idx){
    
    if(str.length() == n){
        int ja=0;
        int mo=0;
        for(int i=0; i<str.size(); i++){
            if(str[i] == 'a' || str[i] == 'e'|| str[i] == 'i' || str[i] == 'o' || str[i] == 'u'){
                mo +=1;
            }else {
                ja +=1;
            }
        }
        if(mo >= 1 && ja >= 2){
            cout << str << '\n';
        }
        return;
    }
    if(v.size() == idx){
        return;
    }
    
    //알파벳 선택 하는 경우
    dfs(v,n,m,str+v[idx],idx+1);
    //알파벳 선택 하지 않는 경우
    dfs(v,n,m,str,idx+1);
}

int main(void){
    int n,m;
    cin >> n >> m;
    vector<char> v(m);
    for(int i=0; i<m; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    dfs(v,n,m,"",0);
    
}

Share