1주차 6월 1일 - 6월7일

시작전

알고리즘에 대한 심리적 부담이 컸었는데, 그냥 아무 생각없이 일주일에 세문제만 풀기로 마음을 먹었다. 더 푼다고 실력이 빨리늘거나 그러진 않을것같고, 장기전으로 보고 그냥 내 코드의 수준을 높이는데 언젠가는 도움이 될 것이라는 마음으로 매주 세문제를 풀려고 한다. 주말에 몰아서 풀어도 부담없는 양으로 딱 정했다. 

 

이번주의 문제

1. 숨박꼭질4: https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

2. DSLR: https://www.acmicpc.net/problem/9019

9019번: DSLR

 

3. 퍼즐: https://www.acmicpc.net/problem/1525

1525번: 퍼즐

 

나의 풀이

1. 숨박꼭질 4

- 이문제는 딱히 어려운건 아니다. 그냥 BFS 하는 기초 문제인데, check 배열을 활용해서 어디서 왔는지 기록을 해주면 해결 가능하다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int check[200001];
int n, k;
vector<int> ans;

void bfs(){
    queue<int> q;
    q.push(n);
    check[n] = -2; 

    while(!q.empty()){
        int a = q.front();
        q.pop();
        
        if(a == k){
            break;
        }

        if(a - 1 >= 0 && check[a-1] == -1){
            check[a-1] = a;
            q.push(a-1);
        }

        if(a * 2 <= 200000 && check[a*2] == -1){
            check[a*2] = a;
            q.push(a*2);
        }

        if(a + 1 <= 200000 && check[a+1] == -1){
            check[a+1] = a;
            q.push(a+1);
        }
    }

    // cout << check[17] << "\n";
    // cout << check[18] << "\n";
    // cout << check[9] << "\n";
    // cout << check[10] << "\n";
    // cout << check[5] << "\n";
    int next = k;
    while(next != -2){
        // cout << next << " ";
        ans.push_back(next);
        next = check[next];
    }

    cout << ans.size() - 1 << "\n";

    for(int i = ans.size()-1; i >= 0; i--){
        cout << ans[i] << " ";
    }

    // cout << check[k] << "\n";
}

int main(){
    cin >> n >> k;

    for(int i = 0; i < 200001; i++){
        check[i] = -1;
    }

    bfs();

    return 0;
}

 

 

2. DSLR: 비슷한 문제인데, 생각보다 정답률은 낮다. 생각해보면 문제의 조건때문에 틀리는건가? 

- S 의 조건에 대해서 많이 햇갈렸다. n-1이 0이되면 9999가 된단건지, -1이 되면 9999가 된단건지 헷갈려서 한참 헤맸는데 막상 메인 코드부분은 비슷해서 별로 어려운건 없었다. 

 

- 경계값을 테스팅 해보면 된다는 말이 뭔소린지 이제 알았다. 대충 틀릴만한거 조금은 테스팅 해보는 습관을 가져야할 것 같다. 아직 더 효육적인 코드를 짜는 건 어려운 것 같다. 

 

- 이차원 배열 머리 아프게 쓰는것 보다 그냥 일차원 배열 두개쓰는게 정신건강에 훨씬 이롭다는 것을 배웠고 써먹었다. 

 

-스트링 관련 함수는 아직 좀 낯선데, 점점 익숙해 져가고 있다.

 

- 함수를 구분해서 알고리즘 문제를 풀지 않았었는데, 이제 점차 함수를 구분해서 기능을 명확히 하면 풀려고 한다.

 

- 회사에서 이상한거 만드느라 시간 쓰다가, 알고리즘같은걸 하니까 마음이 편안해지는 느낌이다. 

 

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int T;
char check[10001];
int check_int[10001];
int a;
int b;

void resetCheck(){
    for(int i = 0; i < 10001; i++){
        check[i] = '.'; // reset '.'
        check_int[i] = -1; 
    }
}

int getNum(int arr[]){
    int result = 0;
    for(int i = 0; i < 4; i++){
        result *= 10;
        result += arr[i];
    }
    return result;
}

int rotateL(int a){
    int sa[4];
    for(int i = 2; i >=0; i--){
        sa[i] = a % 10;
        a = a / 10;
    }
    sa[3] = a;
    return getNum(sa);
}

int rotateR(int a){
    int sa[4];
    sa[0] = a % 10;
    a = a / 10;
    for(int i = 3; i >=1; i--){
        sa[i] = a % 10;
        a = a / 10;
    }
    return getNum(sa);
}

void printRoute(){
    string answer = "";
    int next = b;
    while(check[next] != '*'){
        // answer.push_back(check[next]);
        answer.insert(0, 1, check[next]);
        next = check_int[next];
    }
    cout << answer << "\n";
}

void bfs(){
    check[a] = '*'; // * 는 시작
    check_int[a] = -3;
    queue<int> q;
    q.push(a);
    
    while(!q.empty()){ 
        int n = q.front();
        q.pop();

        if(n == b){
            printRoute();
            return;
        }

        // D
        if(check[(n * 2) % 10000] == '.'){
            // cout << "d" << "\n";
            check[(n * 2) % 10000] = 'D';
            check_int[(n * 2) % 10000] = n;
            q.push((n * 2) % 10000);
        }

        // S
        if((n - 1) >= 0 && check[n - 1] == '.'){
            check[n - 1] = 'S';
            check_int[n - 1] = n;
            q.push(n - 1);
        } else if((n - 1) == -1 && check[9999] == '.'){
            check[9999] = 'S';
            check_int[9999] = n;
            q.push(9999);
        } 

        // L
        int ll = rotateL(n);
        if(check[ll] == '.'){
            // cout << "l" << "\n";
            check[ll] = 'L';
            check_int[ll] = n;
            q.push(ll);
        }

        // R
        int rr = rotateR(n);
        if(check[rr] == '.'){
            // cout << "r" << "\n";
            check[rr] = 'R';
            check_int[rr] = n;
            q.push(rr);
        }
    }
}

int main(){
    cin >> T;
    while(T--){   
        cin >> a >> b;
        // intToArray();
        resetCheck();
        bfs();
    }
}

 

 

3. 퍼즐

- 이차원 배열을 쓰는 BFS문제가 젤 약한데 이 문제를 풀면서 map이라는 개념을 배움

- https://twpower.github.io/91-how-to-use-map-in-cpp

[C++] C++ STL map 기본 사용법과 예제

- 키의 조건이 복잡할때 쓴다. 

- string 함수도 to_string, find 등을 사용했음.

- swap함수로 위치를 탁, 바꾸는걸 할 수 있다. 

 

 

이건 내가 직접 푼게 아닌데, 다음엔 직접 풀길!!