Jgtony Developer blog

18 Jul 2019

알고리즘 - 브루트 포스(중급)

c++

앞서 살펴본 브루트 포스 알고리즘의 중급 사용 방법을 제시한다. 일반적으로 브루트 포스 문제에서 가장 문제가 되는 것은 시간 이므로, 이부분을 효율적으로 조절할 수 있는 방법을 알아본다.

브루트 포스를 푸는 방법

  1. for 문
  2. 순열 사용
  3. 재귀사용
  4. 비트마스크 사용



리모컨 (1107번 문제)

+ 와 - 버튼은 모든 숫자를 누르고 나서 실행된다는 것을 알 수 있다. 또한 같은 숫자(장소)를 중복적으로 방문하는 경우에는 절대 최소가 될 수 없다. 따라서 + 나 - 버튼은 한가지 종류만 사용해야 한다.

이동하려는 채널은 0~500000 까지이다. 따라서 우리가 누르는 채널 C는 0~1000000의 범위에 있다고 생각하면 된다. 왜냐면 50만까지 + 만 눌러서 이동한경우 50만번이 나오게 된다. 반대로 정답보다 큰곳에서 작은곳으로 갈 수 있는 최대 값은 -50만이기 때문에 100만의 범위가 나오게 된다.

  1. 이동할 채널을 정한다
  2. 이동할 채널에 고장난 버튼이 있는지 확인하고
  3. + 나 - 버튼을 몇개 눌러야 할 지 정해본다.

코드 설명

#include <stdio.h>
#include <stdlib.h>
int broken[10]; // 고장난 버튼 (true, false)
int strLen;         // broken_check 에 들어온 숫자의 자리수
int n,m;

/* broken_check 함수
인자로 들어온 수를 고장난 버튼 없이 만들수 있는지(true,false)
또 인자로 들어온 수의 자리수(strLen)를 계산
*/
bool broken_check(int num) {
    int ct = 1;
    bool broken_flag = false;
    if(num==0) {
        strLen = ct;
        if(broken[0]) return true;
        else return false;
    }
    while(num!=0) {
        if(broken[num%10]) broken_flag = true;
        num /= 10;
        ct++;
    }
    strLen = ct-1;
    return broken_flag;
}

int main() {
    int tmp,ct,res = -1;
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=0;i<m;i++) {
        scanf("%d",&tmp);
        broken[tmp] = true;
    }

    bool isBroken = broken_check(n);
    /* isBroken ? 브루트포스 : 간단계산
    만약 인풋 번호를 고장난 버튼 없이 누를 수 있다면
    좀 더 빠르게 계산하기 위해 (if not brute force)
    \*/
    if(!isBroken) {
        tmp = abs(n-100);
        if(tmp < strLen) res = tmp;
        else res = strLen;
    }
    /* res = min(모든경우의수)
    인풋이 50만까지이므로 100만까지 브루트 포스
    숫자로만 만들수 있는 수가 나타나면, 매번 경우의 수를 계산
    가장 큰 값을 min 에 저장
    \*/
    else {
        res = abs(n-100);
        for(int i=0;i<=1000000;i++) {
            tmp = i;
            if(!broken_check(i) && (res>strLen+abs(n-tmp) || res==-1)) {
                res = strLen + abs(n-tmp);
            }
        }
    }
    printf("%d",res);
}



카잉 달력 (6064번 문제)

M,N 과 x,y의 규칙을 먼저 찾아야만 한다.

// M=10,N=12
년   M   N
1    1   1
2    2   2  
...
10  10 10
11  1   11
12  2   12
13  3   1

위와 같이 보면 (if 년%M==0 ? M : x=년도%M ), (if 년%N==0 ? N : y=년도%N ) 로 나타난다. 문제는 M,N,x,y 를 가지고 년도를 구하는 문제이다.

근데 그냥 브루트포스를 돌려버리면, 가지수가 16억 가지로 구할수가 없다.(시간제한에 걸린다)

위에서 구한 규칙을 보면, x 는 년도를 M으로 나눈 나머지라는 것을 알 수 있다. 단 까다로운 것은, 나머지가 0이 되어야 할 때 그대로 M이 나온다는 것만 다르다. 그럼 반대로 말해서 년도를 구하려면 x 를 기준으로 M년씩 늘려가면서 해당하는 y 값이 나타나는지를 보면 된다!

코드 설명

#include <stdio.h>

/* 결과값을 계산하는 함수
x의 년도에 해당하는 y 값만 찾으면 되므로
총 범위 4만번만 계산하면 된다
\*/
int find(int m,int n,int x,int y) {
    for(int i=0;i<=40000;i++) {
        int Yr = (m*i)+x;
        if(Yr%n==0 && n==y) return Yr;
        else if(Yr%n==y) return Yr;
    }
    return -1;
}

int main() {
    int t,m,n,x,y;
    scanf("%d",&t);
    while(t--) {
        scanf("%d %d %d %d",&m,&n,&x,&y);
        printf("%d\n",find(m,n,x,y));
    }
}



수 이어 쓰기1 (1748번 문제)

먼저 N의 자리수를 계산하고, 1자리수부터 N자리수까지 더해가면 된다. (쉽다)

코드는 다음과 같다.

#include <stdio.h>
#include <math.h>

int check(int num) {
    int ct = 0;
    while(num!=0) {
        num/=10;
        ct++;
    }
    return ct;
}

int main() {
    int n,res = 0;
    scanf("%d",&n);
    int l = check(n);
    for(int i=1;i<l;i++) {
        res += (pow(10,i)-pow(10,i-1)) * i;
    }
    res += (n-pow(10,l-1)+1) * l;
    printf("%d",res);
}

Other Posts

Comments