'알고리즘' 카테고리의 글 목록 (3 Page)

완전탐색 - 순열 응용편 (차이를 최대로 - 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

예제 출력

소스 코드

 
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
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;
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

삼성 코딩 테스트 기출 - 연구소 14502번 (DFS, BFS) (0)	2018.04.04
완전탐색 - BFS (숨바꼭질 1697번 , 소수 경로 - 1963번 , DSLR - 9019번) (0)	2018.04.03
완전탐색 - 순열 기초 (0)	2018.04.02
완전탐색 - Brute Force Search (0)	2018.04.02
완전탐색 - 비트마스크 기초 (0)	2018.03.30

완전탐색 - 순열 기초

C++ STL의 알고리즘의 next_permutation 과 prev_permutation을 활용하여 완전탐색 문제에 응용해봅시다.

순열을 연습해보자

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

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

예제 입력 1 복사

예제 출력 1 복사

소스 코드

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

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전탐색 - BFS (숨바꼭질 1697번 , 소수 경로 - 1963번 , DSLR - 9019번) (0)	2018.04.03
완전탐색 - 순열 응용편 (차이를 최대로 - 10819번 , 외판원 순회 2 - 10971번 , 로또 - 6603번) (0)	2018.04.02
완전탐색 - Brute Force Search (0)	2018.04.02
완전탐색 - 비트마스크 기초 (0)	2018.03.30
일곱난쟁이 2309번 - 완탐(순열) (0)	2018.03.22

완전탐색-BruteForceSearch.md

완전 탐색 - Brute Force Search

일단 완전 탐색을 할 수 있는 방법은 여러가지가 있는데,

1) Brute Force - 그냥 다 해보리기

2) BFS - 그래프로 표현하여 다 탐색하기

3) 재귀

4) 비트마스크

5) 순열

6) 백트래킹

등등 이 있다.

Brute Force

그냥 다 검색해보는 Brute Force를 공부해보자아.
for문과 if문을 이용하여 처음부터 쭈루룩 탐색해보는 방법.
여기서 중요한 것은 범위, 무작정 다 검색하기 때문에 시간초과가 날수 있다.
for문 1억번을 1초라고 보통 생각하기 때문에 이걸 잘 생각하며 풀어야 한다.

쉬운 문제로 일단 어떤 느낌인지 공부를 해보면

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

날짜 계산 1476번

이 문제는 for문 과 간단한 if문을 통해 1, 1 , 1부터 쭈루룩 돌아서 입력과 같은 값이 되었을 때 count한 값을 출력하는 심플한 문제

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 숫자를 E, 태양을 나타내는 숫자를 S, 달을 나타내는 숫자를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 지나면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입력 1

 
xxxxxxxxxx
1 16 16

예제 출력 1

 
xxxxxxxxxx
16

예제 입력 2

 
xxxxxxxxxx
1 1 1

예제 출력 2

 
xxxxxxxxxx
1

예제 입력 3

 
xxxxxxxxxx
1 2 3

예제 출력 3

 
xxxxxxxxxx
5266

소스 코드

 
xxxxxxxxxx
#include<iostream>
using namespace std;
int main()
{
    // 날짜 계산 1476번
    int E, S, M;
    int e = 1, s = 1, m = 1;
    int year = 1;
    cin >> E >> S >> M;
    while (!(E == e && S == s && M == m))
    {
        e++;
        s++;
        m++;
        if (e == 16) e = 1;
        if (s == 29) s = 1;
        if (m == 20) m = 1;
        year++;
    }
    cout << year << '\n';
    return 0;
}

리모콘 1107번

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

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 중복되서 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

예제 입력 1

 
xxxxxxxxxx
5457
3
6 7 8

예제 출력 1

 
xxxxxxxxxx
6

예제 입력 2

 
xxxxxxxxxx
100
5
0 1 2 3 4

예제 출력 2

 
xxxxxxxxxx
0

예제 입력 3

 
xxxxxxxxxx
500000
8
0 2 3 4 6 7 8 9

예제 출력

 
xxxxxxxxxx
11117

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v(10);
int res;
int check(int c)
{
    int len = 0;
    if(c == 0)
    {
        if(v[0]) return 0;
        else return 1;
    }
    
    while(c > 0)
    {
        if(v[c % 10]) return 0;
        len++;
        c /= 10;
    }
    return len;
}
int main()
{
    int c;
    int n;
    cin >> c;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int tmp;
        cin >> tmp;
        v[tmp] = 1;
    }
    
    res = abs(c - 100);
    
    
    for(int i=0;i<=1000000;i++)
    {
        int len = check(i);
        if(len > 0)
        {
            int press = abs(c - i);
            if(res > len + press)
                res = len + press;
        }
    }
    
    cout << res << '\n';
    
    return 0;
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전탐색 - 순열 응용편 (차이를 최대로 - 10819번 , 외판원 순회 2 - 10971번 , 로또 - 6603번) (0)	2018.04.02
완전탐색 - 순열 기초 (0)	2018.04.02
완전탐색 - 비트마스크 기초 (0)	2018.03.30
일곱난쟁이 2309번 - 완탐(순열) (0)	2018.03.22
1244번 최대상금 - [S/W 문제해결 응용] (0)	2018.03.22

완전 탐색 - 비트마스크

비트 연산

shift left (<<) , shift right (>>) 두개의 연산이 있다

A >> B (A 를 오른쪽으로 B비트만큼 이동)

1 >> 1 0(이진법)

10 >> 1 101(이진법)

10 >> 2 1010 을 오른쪽으로 2비트 이동 ==> 10 즉 2가 됨

A << B 는 A * 2^B

A >> B 는 A / 2^B

이것을 이용하여 할 수 있는 것은 정수를 통해 집합을 표현할 수 있다.

만약 10명의 학생이 있고, 0~9번 이라는 번호로 학생을 표현하고 싶을 때 1,3,5,7,9 번의 학생을 한 집합으로 표현한다면,

$2^1 + 2^3 + 2^5 + 2^7 + 2^9 = 682$

이런 식으로 표현이 가능하며, 2진법으로 표현한다면 1010101010(2) 으로 표현할 수 있다.

만약에 내가 5번 학생이 있는걸 확인하고 싶으면

 
xxxxxxxxxx
int sum = 682;
if(sum & (1 << 5)) cout << "5번 학생이 있다" << '\n';

이 집합 상태에서 어느 한 학생을 추가(삽입) 하고싶다면 OR(|) 연산을 이용하면 된다.

 
xxxxxxxxxx
sum = sum | (1 << 2);   // 2번 학생을 추가

$682 | 2^2 = 682 |(1 << 2) = 686 (1010101110(2))$

여기서 + 연산을 사용하지 않은 이유는 carry가 발생하여, 다른 값에 영향을 줄수 있기 때문에 OR연산을 사용한다.

집합에서 어느 한 학생을 제거(삭제) 하고 싶다면 N0T(&)연산을 이용하면 된다.

 
xxxxxxxxxx
sum = sum & ~(1 << 5);  // 5번 학생을 제거

전체 집합 표현

$(1 << N) - 1 = 2^N - 1$

공집합

$0$

A라는 집합에서 특정 n 을 추가 할때

A | (1 << n)

A라는 집합에서 특정 n 을 확인 할때

A & (1 << n)

A라는 집합에서 특정 n 을 제거 할때

A & ~(1 << n)

A라는 집합에서 각 값을 토글 할때

A ^ (1 << n)

비트마스크 연산 연습해보기

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

소스 코드

 
x
#include<iostream>
#include<string>
using namespace std;
int sum;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string ins;
        cin >> ins;
        if(ins == "add")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum | (1 << tmp);
        }
        else if(ins == "remove")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum & ~(1 << tmp);
        }
        else if(ins == "check")
        {
            int tmp;
            cin >> tmp;
            if(sum & (1 << tmp)) cout << "1" << '\n';
            else cout << "0" << '\n';
        }
        else if(ins == "toggle")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum ^ (1 << tmp);
        }
        else if(ins == "all")
            sum = (1 << 20) - 1;
        else if(ins == "empty")
            sum = 0;
    }
    return 0;
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전탐색 - 순열 기초 (0)	2018.04.02
완전탐색 - Brute Force Search (0)	2018.04.02
일곱난쟁이 2309번 - 완탐(순열) (0)	2018.03.22
1244번 최대상금 - [S/W 문제해결 응용] (0)	2018.03.22
로또 6603번 - 순열 (0)	2018.03.22

열혈강호 11375번 - 이분매칭

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	256MB	4080	1548	803	34.567%

문제

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

예제 입력

 
xxxxxxxxxx
5 5
2 1 2
1 1
2 2 3
3 3 4 5
1 1

예제 출력

 
xxxxxxxxxx
4

소스 코드

 
x
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int emp;    // 일하는 사람 수
int work;   // 작업의 수
int res;    // 결과
vector<vector<int>> v(1001);    // 어떤 사람이 무슨 일 할 수 있는지 저장
int visit[1001];        // i번째 사람의 이미 방문했는지 check
int match[1001];        // i번째 일을 누가 했는지 match[i]에 저장
int dfs(int person)
{
    if (visit[person]) return 0;        // 이미 dfs돌았다면 패스
    visit[person] = 1;
    
    for (int i = 0; i < v[person].size(); i++)
    {
        int here_work = v[person][i];       // 직원이 무슨 일 할 수 있는지 here_work에 저장
        if (!match[here_work] || dfs(match[here_work]))
        {
            match[here_work] = person;      // 그 작업을 현재 사람에게 매칭
            return 1;
        }
    }
    return 0;
}
int main()
{
    cin >> emp >> work;
    for (int i = 1; i <= emp; i++)
    {
        int seq;
        cin >> seq;
        for (int j = 1; j <= seq; j++)
        {
            int tmp;
            cin >> tmp;
            v[i].push_back(tmp);
        }
    }
    for (int i = 1; i <= emp; i++)
    {
        fill(visit, visit + emp, 0);
        if (dfs(i)) res++;
    }
    cout << res << '\n';
    return 0;
}

2018-03-22-일곱난쟁이2309번.md

일곱 난쟁이 2309번 - 완탐(순열)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	10771	6066	4744	57.378%

이 문제는 순열을 이용하여 푼 완전탐색 문제이다
9명의 난쟁이들 중에 7명을 고르고 조건을 만족하면 출력하는 문제
vector하나 만들어서 7개의 1과 2개의 0을 넣어 순열 쭈루루룩 돌린담에 조건을 만족하면 출력
이 방법은 next_permutation을 돌리기 전 맨처음 상태도 체크 해야하기 때문에 do_while 사용

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 일곱 난쟁이의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다.

예제 입력

 
xxxxxxxxxx
20
7
23
19
10
15
25
8
13

예제 출력

 
xxxxxxxxxx
7
8
10
13
19
20
23

소스코드

 
xxxxxxxxxx
// 2309번 일곱난쟁이
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v(9);
void input()
{
 for (int i = 0; i < 9; i++)
  cin >> v[i];
}
void DFS()
{
 vector<int> tmp;
 for (int i = 0; i < 2; i++)
  tmp.push_back(0);
 for (int i = 0; i < 7; i++)
  tmp.push_back(1);
 do {
  int sum = 0;
  for (int i = 0; i < tmp.size(); i++)
   if (tmp[i]) sum += v[i];
  if (sum == 100)
   break;
 } while (next_permutation(tmp.begin(), tmp.end()));
 vector<int> res;
 for (int i = 0; i < tmp.size(); i++)
 {
  if (tmp[i]) res.push_back(v[i]);
 }
 sort(res.begin(), res.end());
 for (int i = 0; i < res.size(); i++)
  cout << res[i] << '\n';
}
int main()
{
 input();
 DFS();
 return 0;
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전탐색 - Brute Force Search (0)	2018.04.02
완전탐색 - 비트마스크 기초 (0)	2018.03.30
1244번 최대상금 - [S/W 문제해결 응용] (0)	2018.03.22
로또 6603번 - 순열 (0)	2018.03.22
백준 - 숨바꼭질 1697번 - 완전탐색(BFS) (2)	2018.03.09

1244번 최대상금 - [S/W 문제해결 응용]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD

이 문제는 이중 for문으로 완전탐색을 아주 그냥 돌려버렸다.

중복체크 안하고 돌리면 테스트케이스 7번까지는 돌아간다.

하지만 테스트케이스 8번부터 시간초과가 나버린다.

그러므로 중복체크 해야하므니다.

소스코드

 
xxxxxxxxxx
// 1244 최대상금 - 완탐
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int T, seq;
vector<int> v;
int max_price;
int check[1000000][11];
int calc()
{
    int tmp = 0;
    for (int i = 0; i < v.size(); i++)
        tmp += (v[i] * pow(10, v.size() - i - 1));
    
    return tmp;
}
void swap(int f,int s)
{
    int first = v[f];
    int second = v[s];
    v[f] = second, v[s] = first;
}
void DFS(int n)
{
    if (n >= seq)
    {
        max_price = max(max_price, calc());
        return;
    }
    if (check[calc()][n]) return;       // 이 두줄이 중복체크용
    check[calc()][n] = 1;
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = i+1; j < v.size(); j++)
        {
            swap(i, j);
            DFS(n + 1);
            swap(i, j);
        }
    }
}
void input()
{
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        string tmp;
        cin >> tmp >> seq;
        for (int j = 0; j < tmp.size(); j++)
            v.push_back(tmp[j] - '0');
        DFS(0);
        cout << "#" << i << " " << max_price;
        max_price = 0;
        v.clear();
    }
}
int main()
{
    input();
    
    return 0;
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전탐색 - Brute Force Search (0)	2018.04.02
완전탐색 - 비트마스크 기초 (0)	2018.03.30
일곱난쟁이 2309번 - 완탐(순열) (0)	2018.03.22
로또 6603번 - 순열 (0)	2018.03.22
백준 - 숨바꼭질 1697번 - 완전탐색(BFS) (2)	2018.03.09

2018-03-22-6603번 로또.md

로또 6603번 (완전탐색-순열)

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

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	128MB	4821	2685	1995	55.602%

algorithm에 있는 순열함수인 next_permutation을 이용하여
만약 7개 중에 6개를 골라야한다면, 배열에 0을 1개 , 1을 6개 넣어서 나올수 있는 모든 순열을 쫘르르륵 한다음에 1이 위치하고있는 인덱스를 활용하면, 7가지 숫자중 6개의 모든 조합을 추출할 수 있다. 말로는 이해하기 어려울수 있으니 소스를 참고바람.

문제

독일 로또는 {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()
{
    int k;
    while (cin >> k)
    {
        if (k == 0) break;
        vector<int> v(k);
        for (int i = 0; i < k; i++)
            cin >> v[i];
        vector<int> d(k);
        for (int i = 0; i < k - 6; i++)
            d[i] = 0;
        
        for (int i = k - 6; i < k; i++)
            d[i] = 1;
        
        vector<vector<int>> ans;
        do {
            vector<int> current;
            for (int i = 0; i < k; i++)
            {
                if (d[i] == 1)
                    current.push_back(v[i]);
            }
            ans.push_back(current);
        } while (next_permutation(d.begin(), d.end()));
        sort(ans.begin(), ans.end());
        
        for (int i = 0; i < ans.size(); i++)
        {
            for (int j = 0; j < ans[i].size(); j++)
                cout << ans[i][j] << ' ';
            cout << '\n';
        }
        cout << '\n';
    }
    return 0;
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전탐색 - Brute Force Search (0)	2018.04.02
완전탐색 - 비트마스크 기초 (0)	2018.03.30
일곱난쟁이 2309번 - 완탐(순열) (0)	2018.03.22
1244번 최대상금 - [S/W 문제해결 응용] (0)	2018.03.22
백준 - 숨바꼭질 1697번 - 완전탐색(BFS) (2)	2018.03.09

완전탐색 - 숨바꼭질(BFS).md

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	29306	8091	5079	24.925%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력

 
5 17

예제 출력

기본적인 BFS문제이다. Queue에 다음에 갈 수 있는 좌표를 저장하고, Vector을 이용하여 해당 Vector<좌표>에 값이 없을 경우 방문하지 않는 곳이므로 다음에 방문 하게 했다.

BFS를 이용했음으로 가장 빠른 시간을 위한 조건은 따로 필요하지 않았다.

 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<int> v(100001);
void BFS(int start, int end)
{
    queue<int> q;
    q.push(start);
    v[start] = 1;
    while (1)
    {
        if (q.empty()) break;
        int now = q.front();
        q.pop();
        if (now - 1 >= 0)
        {
            if (!v[now - 1])
            {
                v[now - 1] = v[now] + 1;
                q.push(now - 1);
            }
        }
        if (now + 1 <= 100000)
        {
            if (!v[now + 1])
            {
                v[now + 1] = v[now] + 1;
                q.push(now + 1);
            }
        }
        if (now * 2 <= 100000)
        {
            if (!v[now * 2])
            {
                v[now * 2] = v[now] + 1;
                q.push(now * 2);
            }
        }
        if (v[end])
        {
            cout << v[end] - 1 << '\n';
            break;
        }
    }
}
int main()
{
    int s, e;
    cin >> s >> e;
    BFS(s,e);
    return 0;
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전탐색 - Brute Force Search (0)	2018.04.02
완전탐색 - 비트마스크 기초 (0)	2018.03.30
일곱난쟁이 2309번 - 완탐(순열) (0)	2018.03.22
1244번 최대상금 - [S/W 문제해결 응용] (0)	2018.03.22
로또 6603번 - 순열 (0)	2018.03.22

#include<iostream>

#include<windows.h>

#include<time.h>

#include<stdlib.h>

#include "sort.h"

#pragma warning (disable : 4996)

const int N = 10000;

int b[N + 1] , a[N+1];

void MergeSort(int a[], int l, int r)

{

int i, j, k, m;

if (r > l)

{

m = (r + l) / 2;

MergeSort(a, l, m);

MergeSort(a, m + 1, r);

for (i = m + 1; i > l; i--) b[i - 1] = a[i - 1];

for (j = m; j < r; j++) b[r + m - j] = a[j + 1];

for (k = l; k <= r; k++)

a[k] = b[i] < b[j] ? b[i++] : b[j--];

}

int main()

{

int i;

double start_time;

srand(time(NULL));

for (i = 1; i <= N; i++) a[i] = rand();

start_time = clock();

MergeSort(a, 1, N);

cout << "(난수값을 갖는 랜덤 배열일때) 합병 정렬의 실행 시간 (N = " << N << ") : " << (clock() - start_time)/CLOCKS_PER_SEC << "초" << endl;

CheckSort(a, N);

cout << endl;

int reverse = N;

for (i = 1; i <= N; i++) a[i] = reverse--;

start_time = clock();

MergeSort(a, 1, N);

cout << "(역순으로 정렬된 배열일때) 합병 정렬의 실행 시간 (N = " << N << ") : " << (clock() - start_time)/CLOCKS_PER_SEC << "초" << endl;

CheckSort(a, N);

cout << endl;

for (i = 1; i <= N; i++) a[i] = i;

start_time = clock();

MergeSort(a, 1, N);

cout << "(정렬된 배열) 합병 정렬의 실행 시간 (N = " << N << ") : " << (clock() - start_time) / CLOCKS_PER_SEC << "초" << endl;

CheckSort(a, N);

cout << endl;

system("pause");

return 0;

}

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

Programmers - 호텔대실 155651번 (0)	2023.02.09
Vector 2차원 동적 할당 해보리기 (0)	2018.04.03
Visual Studio 2017 (C++) 자연 합병 정렬 (0)	2017.11.04
1장) 알고리즘과 문제해결 (0)	2017.10.19
(C++) 칵테일 쉐이크 정렬 - (ADL 추가) (0)	2017.09.26

알고리즘

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

1) 차이를 최대로 - 10819번

문제

입력

출력

예제 입력

예제 출력

2) 외판원 순회 2 - 10971번

문제

입력

출력

예제 입력

예제 출력

3) 로또 - 6603번

문제

입력

출력

예제 입력

예제 출력

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전탐색 - 순열 기초

순열을 연습해보자

문제

입력

출력

예제 입력 1 복사

예제 출력 1 복사

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전 탐색 - Brute Force Search

Brute Force

날짜 계산 1476번

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

리모콘 1107번

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력

'알고리즘 > 완전탐색' 카테고리의 다른 글

완전 탐색 - 비트마스크

비트 연산

'알고리즘 > 완전탐색' 카테고리의 다른 글

열혈강호 11375번 - 이분매칭

일곱 난쟁이 2309번 - 완탐(순열)

'알고리즘 > 완전탐색' 카테고리의 다른 글

1244번 최대상금 - [S/W 문제해결 응용]

소스코드

'알고리즘 > 완전탐색' 카테고리의 다른 글

로또 6603번 (완전탐색-순열)

소스코드

'알고리즘 > 완전탐색' 카테고리의 다른 글

문제

입력

출력

예제 입력

예제 출력

'알고리즘 > 완전탐색' 카테고리의 다른 글

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

티스토리툴바