띠그랭

완전탐색 - 순열 기초

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

순열을 연습해보자

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

문제

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

입력

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

출력

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

예제 입력 1 복사

 
3

예제 출력 1 복사

 
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 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;
}

완전 탐색 - 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;
}
​

완전 탐색 - 비트마스크

비트 연산

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진법으로 표현한다면 1010101010(2) 으로 표현할 수 있다.

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

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

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

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

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

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

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

전체 집합 표현

공집합

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