완전탐색 - Brute Force Search

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