완전탐색 - 순열 응용편 (차이를 최대로 - 10819번 , 외판원 순회 2 - 10971번 , 로또 - 6603번)

완전탐색 - 순열 응용편 (차이를 최대로 - 10819번 , 외판원 순회 2 - 10971번 , 로또 - 6603번)

완전 탐색을 순열을 이용하여 문제를 한번 기똥차게 풀어보자

일단 순열의 시간 복잡도는 O(N!) 이라는 것을 알자!

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

1) 차이를 최대로 - 10819번

주어진 정수의 숫자들의 순서를 순열(next_permutation)을 통해 구하고, 조건문을 통해 가장 큰 값을 구합시드아. 근데 여기서 주의할 점은 처음부터 쫘르르르르륵 구해야 하기 때문에, 그냥 주어진 입력에서 순열을 돌리는 것이아니라, 정렬(sort)을 한다음에 돌려야 처음부터 끝까지 도는 것이다.

 

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이 때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최대값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력

 
x
6
20 1 15 8 4 10

예제 출력

 
62

 

소스 코드

 
​x
#include<iostream>
#include<vector>
#include<algorithm>
​
using namespace std;
​
int main()
{
    int t;
    vector<int> v;
    int res = 0;
    cin >> t;
    for(int i=0;i<t;i++)
    {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    sort(v.begin(), v.end());
    
    do{
        int tmp = 0;
        for(int i=0;i<v.size() - 1;i++)
            tmp += abs(v[i] - v[i+1]);
        if(res < tmp)
            res = tmp;
    }while(next_permutation(v.begin(), v.end()));
    
    cout << res << '\n';
    
    return 0;
}
​

 

2) 외판원 순회 2 - 10971번

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

순열을 이용하여 처음부터 끝까지 모든 경우의 수를 구한다음 , for문을 이용하여 완전 탐색하는 문제

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i,j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i,j] 는 W[j,i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i,i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i,j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2<=N<=10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i,j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력

 
xxxxxxxxxx
4
0 10 15 20
5  0  9 10
6 13  0 12
8  8  9  0

예제 출력

 
xxxxxxxxxx
35

 

소스 코드

 
x
#include<iostream>
#include<algorithm>
#include<vector>
​
using namespace std;
​
int main()
{
    int n , res = 987654321;
    cin >> n;
    vector<vector<int>> v(n+1,vector<int>(n+1,0));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cin >> v[i][j];
    }
    
    vector<int> tmp(n+1);
    for(int i=1;i<=n;i++)
        tmp[i] = i;
    
    do{
        int len = 0;
        int chk = 0;
        for(int i=1;i<=tmp.size() - 2;i++)
        {
            len += v[tmp[i]][tmp[i+1]];
            if(!v[tmp[i]][tmp[i+1]]) chk = 1;
        }
        len += v[tmp[4]][tmp[1]];
        if(!v[tmp[4]][tmp[1]]) chk = 1;
        if(res > len && chk == 0)
            res = len;
    }while(next_permutation(tmp.begin(), tmp.end()));
    
    cout << res << '\n';
    
    return 0;
}
​

 

여기서 시간 복잡도를 줄일 수 있는 방법이 있는데 잘 생각해보면

1 -> 2 -> 3 -> 4 , 2 -> 3 -> 4 -> 1 , 3 -> 4 -> 1 -> 2 , 4 -> 1 -> 2 -> 3

이 네가지는 모든 같은 경우의 수 인걸 알 수 있다. 그래서 첫번째를 제외한 나머지는 의미가 없는 연산이 된다. 그래서 시작 위치를 고정 시켜도 상관이 없는데 , 1의 위치를 고정 시켜버리자(순열의 갯수가 1줄어듬 , factorial 기준으로는 엄청나게 효과적인 방법)

 

while(next_permutation(tmp.begin(), tmp.end())); 이 부분을

while(next_permutation(tmp.begin() + 1, tmp.end())); 이걸로 수정 하면 같은 결과를 가지면서 더 욱 빠른 알고리즘이 된다.

 

3) 로또 - 6603번

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

이 문제에서 아주 좋은 스킬 하나 배울 수 있다 생각한다.

예를 들어 7개의 숫자가 있는데, 이중 내가 6개의 숫자를 골라야 한다.소스를 통해 확인해보자

아! 일단 여기서 알아야 할게 순열은 중복되는 것은 걸러버린다. 예를 들어 설명하면

d 라는 벡터에 [0] = 0, [1] = 1, [2] = 1, [3] = 1, [4] = 1 , [6] = 1; 이 있고, 순열을 돌리면

0 1 1 1 1 1 1

1 0 1 1 1 1 1

1 1 0 1 1 1 1

1 1 1 0 1 1 1

1 1 1 1 0 1 1

1 1 1 1 1 0 1

1 1 1 1 1 1 0 요로코롬 중복을 제외되면서 출력된다.

 

문제

독일 로또는 {1, 2, ..., 49}에서 숫자 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 숫자 중 k(k>6)개의 숫자를 골라 집합 S를 만든 다음 그 숫자만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 숫자를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 숫자를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 k (6 < k < 13)이고, 다음 k개 숫자는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스 마다 숫자를 고르는 모든 방법을 출력한다. 이 때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력

 
xxxxxxxxxx
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력

 
xxxxxxxxxx
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
​
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

 

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<vector>
#include<algorithm>
​
using namespace std;
​
int main()
{
    while(1)
    {
        int n;
        cin >> n;
        if(!n) break;
        vector<int> v;
        for(int i=0;i<n;i++)
        {
            int tmp;
            cin >> tmp;
            v.push_back(tmp);
        }
        
        vector<int> d;
        for(int i=1;i<=n-6;i++)
            d.push_back(0);
        for(int i=1;i<=6;i++)
            d.push_back(1);
        
        vector<vector<int>> res;
        do{
            vector<int> tmp;
            for(int i=0;i<n;i++)
                if(d[i]) tmp.push_back(v[i]);
            res.push_back(tmp);
        }while(next_permutation(d.begin(), d.end()));
        
        sort(res.begin(),res.end());
        
        for(int i=0;i<res.size();i++)
        {
            for(int j =0;j<res[i].size();j++)
                cout << res[i][j] << ' ';
            cout << '\n';
        }
        cout << '\n';
    }
    return 0;
}
​