반응형

백트래킹을 이용하여 다양한 문제를 구현해보자.


모든 문제는 백준 문제를 이용하여 문제를 적용하고 풀어보려 한다.





1. 순열(nPr)


N과 M(1) :: https://www.acmicpc.net/problem/15649

순열은 아래와 같이 코딩 할 수 있다.


현재 값을 넣고 방문을 표시해준 후 다음 재귀를 반복하면 방문된 값들 빼고 계속 처리를 할 수 있다.


그 후 내가 출력 할 값이 m과 같아지면 출력을 하면 된다.


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
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> vc; // 내가 출력할 것
bool visit[10]; // 그 숫자가 쓰는지확인
 
void dfs()
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
 
        return;
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (!visit[i])
        {
            visit[i] = true;
            vc.push_back(i);
            dfs();
            vc.pop_back();
            visit[i] = false;
        }
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    dfs();
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(5) :: https://www.acmicpc.net/problem/15654


인덱스 내로 해결 할 수 없는 값들을 처리하는 방법이다.


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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <unordered_map>
 
using namespace std;
 
int n, m;
int arr[10];
unordered_map<int, int> visit;
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m)
        {
            if (!visit[arr[i]])
            {
                vc.push_back(arr[i]);
                visit[arr[i]] = 1;
                dfs(i + 1);
                visit[arr[i]] = 0;
                vc.pop_back();
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    sort(arr, arr + n);
    dfs(0);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(9) :: https://www.acmicpc.net/problem/15663


중복된 순열 값을 어떻게 처리할 지 생각해보자.


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
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int n, m;
pii arr[10];
 
map<pii, int> visit;
map<vector<int>, int> mp;
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m && !mp.count(vc))
    {
        mp[vc] = 1;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m)
        {
            if(!visit[arr[i]])
            {
                vc.push_back(arr[i].first);
                visit[arr[i]] = true;
                dfs(i + 1);
                visit[arr[i]] = false;
                vc.pop_back(); 
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        arr[i] = { val, i };
    }
    sort(arr, arr + n);
    dfs(0);
 
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        for (auto i : it->first)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





2. 조합(nCr)


N과 M(2) :: https://www.acmicpc.net/problem/15650


조합은 이전 수의 참조를 하면 안된다는 것을 생각하면 쉽게 구현 할 수 있다.


재귀에 인자가 들어가는데 현재 인덱스 다음 인덱스를 인자로 보내어 이전 값을 참조 못하도록 하자.


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
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, m;
 
vector<int> vc;
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = cnt; i <= n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(i);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    dfs(1);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(6) :: https://www.acmicpc.net/problem/15655


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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
int arr[10];
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = cnt; i < n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(arr[i]);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    sort(arr, arr + n);
    dfs(0);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(10) :: https://www.acmicpc.net/problem/15664



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
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int n, m;
pii arr[10];
 
map<pii, int> visit;
map<vector<int>, int> mp;
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m && !mp.count(vc))
    {
        mp[vc] = 1;
        return;
    }
 
    for (int i = cnt; i < n; i++)
    {
        if (vc.size() < m)
        {
            if(!visit[arr[i]])
            {
                vc.push_back(arr[i].first);
                visit[arr[i]] = true;
                dfs(i + 1);
                visit[arr[i]] = false;
                vc.pop_back(); 
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        arr[i] = { val, i };
    }
    sort(arr, arr + n);
    dfs(0);
 
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        for (auto i : it->first)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





3. 중복 순열(nπr)


N과 M(3) :: https://www.acmicpc.net/problem/15651


중복 순열은 중복해서 뽑아도 되고 이전 값을 뽑아도 된다는 것을 이용하여 코딩해보자.


위의 내용들을 이해하기 시작했다면 이 코드도 충분히 이해 할 수 있다.



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
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> vc;
 
void dfs()
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(i);
            dfs();
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    dfs();
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





N과 M(7) :: https://www.acmicpc.net/problem/15656



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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
int arr[10];
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(arr[i]);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    sort(arr, arr + n);
    dfs(0);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





N과 M(10) :: https://www.acmicpc.net/problem/15664



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
58
59
60
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int n, m;
pii arr[10];
vector<int> vc;
 
map<vector<int>, int> mp;
 
void dfs(int cnt)
{
    if (vc.size() == m && !mp.count(vc))
    {
        mp[vc] = 1;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m)
        {
            vc.push_back(arr[i].first);
            dfs(i + 1);
            vc.pop_back(); 
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        arr[i] = { val, i };
    }
    sort(arr, arr + n);
    dfs(0);
 
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        for (auto i : it->first)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





4. 중복 조합(nHr)


N과 M(4) :: https://www.acmicpc.net/problem/15652


중복 조합은 중복 순열에서 이전 값들을 다시 쓸 수 없게만 처리해주면 된다.


이때 중복해서 계속 뽑을 수 있으니 조건에서 간단한 예외처리를 생각해줘보자.


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
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (vc.size() < m && (vc.size() == 0 || vc[vc.size() - 1] <= i))
        {
            vc.push_back(i);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    dfs(1);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




N과 M(8) :: https://www.acmicpc.net/problem/15657



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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
int arr[10];
vector<int> vc;
 
void dfs(int cnt)
{
    if (vc.size() == m)
    {
        for (auto i : vc)
            printf("%d ", i);
        printf("\n");
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m && (!vc.size() || vc[vc.size() - 1] <= arr[i]))
        {
            vc.push_back(arr[i]);
            dfs(i + 1);
            vc.pop_back();
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    sort(arr, arr + n);
    dfs(0);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
cs





N과 M(12) :: https://www.acmicpc.net/problem/15666



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
58
59
60
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int n, m;
pii arr[10];
vector<int> vc;
 
map<vector<int>, int> mp;
 
void dfs(int cnt)
{
    if (vc.size() == m && !mp.count(vc))
    {
        mp[vc] = 1;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (vc.size() < m && (!vc.size() || vc[vc.size() - 1] <= arr[i].first))
        {
            vc.push_back(arr[i].first);
            dfs(i + 1);
            vc.pop_back(); 
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        arr[i] = { val, i };
    }
    sort(arr, arr + n);
    dfs(0);
 
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        for (auto i : it->first)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus









TIP


조합을 다른 방식으로 한번 이해해보자.


우리는 고등학생 때 조합의 방식을 아래와 같이 생각해본 적이있다.


7개중 4개를 뽑으려면 ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ을 두고 이중에 4군데에만 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
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    vector<int> vc = { 0,0,0,1,1,1,1 };
 
    for (int i = 0; i < vc.size(); i++)
        if (vc[i])
            cout << i << " ";
    cout << endl;
 
    while (next_permutation(vc.begin(), vc.end())) {
        for (int i = 0; i < vc.size(); i++)
            if (vc[i])
                cout << i << " ";
 
        cout << endl;
    }
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



반응형
저작자표시 비영리 변경금지 (새창열림)

'Applied > 알고리즘' 카테고리의 다른 글

편집거리 알고리즘  (2) 2018.06.29
컨벡스 헐 알고리즘(Convex Hull Algorithm)  (3) 2018.06.21
확장 유클리드 알고리즘  (2) 2018.04.18
모듈러 연산(Modular Arithmetic)  (8) 2018.04.18
과반수 찾기 알고리즘  (4) 2018.04.08

티스토리툴바