[ 브루트포스 ] 필수과제 해결하기 ( 백준 1063, 1436, 11723 c++)

✅ 브루트포스 알고리즘

☑️ 완전 탐색

말 그대로 정말 모든 경우의 수를 다 보는 것!

 

 

 

 

필수 과제 1 <킹>

#include <iostream>
#include <vector>

using namespace std;

int BF(int n, string& k, string& d, vector<string>& moveD) {
    
    //주소값으로 전달해 함수에서 k,d의 값을 변형시킴
    
    string lastK, lastD; //움직이기 전 k,d의 위치
    
    for(int i=0; i<n; i++) {
        
        lastK=k;
        lastD=d;
        
        //킹의 이동
        if(!moveD[i].compare("T")) { //직진
            k[1]++;
        } else if (!moveD[i].compare("R")) {//오른쪽
            k[0]++;
        } else if (!moveD[i].compare("B")) {
            k[1]--;
        } else if (!moveD[i].compare("L")) {
            k[0]--;
        } else if (!moveD[i].compare("RT")) {
            k[0]++;
            k[1]++;
        } else if (!moveD[i].compare("RB")) {
            k[0]++;
            k[1]--;
        } else if (!moveD[i].compare("LB")) {
            k[0]--;
            k[1]--;
        } else if (!moveD[i].compare("LT")) {
            k[1]++;
            k[0]--;
        }
        
        
        //킹이 밖으로 나갔을 때
        if(k[0]<'A' || k[0]>'H' || k[1]<'1' || k[1]>'8') {
            k=lastK; //방금 한 이동은 취소하고, 다음 반복 진행!
            continue;
        }
        
        
        //킹이 돌이 있는 곳으로 움직일 때
        if(!k.compare(d)) {
            
            //k가 움직인 만큼 d도 움직여!
            d[0]+=(k[0]-lastK[0]);
            d[1]+=(k[1]-lastK[1]);
            
            //움직인 돌이 밖으로 나갔을 때
            if(d[0]<'A' || d[0]>'H' || d[1]<'1' || d[1]>'8') {
                
                d=lastD; //방금 한 이동은 취소하고, 다음 반복 진행!
                k=lastK;
                continue;
            }
        }
        
        
    }
    
    return 0;
}



int main()
{
    
    int n; //킹이 움직인 횟수
    string k, d; //킹과 돌의 위치
    vector <string> moveD (n, "?"); //킹의 이동 방향 저장
    string temp;
    
    
    //입력

    cin >> k >> d >> n;
    
    for(int i=0; i<n; i++) {
        cin >> temp;
        moveD.push_back(temp);
    }
    
    //연산
    BF(n, k, d, moveD);
    
    
    //출력
    cout << k << '\n' << d;

    
    return 0;
}

아스키 코드 잘못봐서 한참 헤맨 문제... ㅎㅠ

바부같이... 왠지 풀이엔 문제가 없고 반례도 다 맞는데 자꾸 틀렸다구 뜨더라니..

72 대신에 90인가가 들어있었다 (대체 왜?)

암튼 눈 빠지게 봐도 안보였는데 튜터님이 찾아주심 ㅎㅎㅎ :)... 사랑함미다 알튜비튜...💚

 

튜터님이 65말구 그냥 'A' 이렇게 고치는 게 좋을 것 같다구 피드백 주셔서 고쳤다!

브루트포스라 걍 문제 이해하구 차례차례 다 해보면 되는 쉬운 문제!

 

 

 

필수 과제 2 <영화감독 숌>

#include <iostream>

using namespace std;

const int NUM = 666;

int main()
{
    
    int n;
    
    //입력
    cin >> n;
    
    
    //연산
    int cnt=0; //종말의 수의 개수
    int i=666; //현재 점검하고 있는 수
    int temp=i;
    
    while(n!=cnt) {
        
        while(temp>0) {
            
            if(temp%1000==NUM) { //끝자리 666이면 카운트 +1
                cnt++; //종말의 수다!
                break;
            } else { //끝자리 666아니면 일의 자리 수 자르고 다시 점검
                temp/=10;
            }
        }
        
        i++;
        temp=i;
        
    }


    //출력
    cout << i-1; //while 마지막에 i++되었으므로 뺴주기
    return 0;
}

 

666이 연속되는 수들이 규칙성이 있는 줄 알고 예전에 한참 헤맸던 문제..

그냥 단순히 666이 반복되는 수가 나올때마다 카운트하면서 몇 번째 666수인지 찾는..

진짜 말 그대로 브루트포스 알고리즘 문제였다 ㅎㅎ

괜히 이상하게 생각해서 문제를 꼬았지만.. 결국 구현은 단순하다!

 

 

 

필수 과제 3 <집합>

#include <iostream>
#include <vector> 

using namespace std;

int main()
{
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    string cmd;
    int x;
    vector <int> s;
    int ans=0;
    
    cin >> n;
    
    while(n>0) {
        cin >> cmd ;
        if(!cmd.compare("add")) {
            cin>>x;
            ans |= (1 << x); //원소 추가
        } 
        
        else if(!cmd.compare("remove")) {
            cin>>x;
            ans &= ~(1 << x);//원소 삭제

        } 
        
        else if(!cmd.compare("check")) {
            cin>>x;
            if (ans & (1 << x))
                cout << 1 << '\n';
            else
                cout << 0 << '\n';
        } 
        
        else if(!cmd.compare("toggle")) {
            cin>>x;
            ans ^= (1 << x);

        } 
        
        else if(!cmd.compare("all")) {
            ans = (1 << 21) - 1;

        } 
        
        else if(!cmd.compare("empty")) {
            ans = 0;
        }
        
        n--;
    }
    
    
    
    return 0;
}

비트마스킹을 활용한 문제 !

https://rebro.kr/63

비트마스크 (BitMask) 알고리즘