사실, 예전부터 클라우드 자격증에는 관심이 있었다.

클라우드 자격증을 생각했던 이유는 커리어의 큰 목표는 DevOps Engineer인데 첫 커리어로는 힘든 것이 사실이다. 그래서 BE 개발자로 시작하여 커리어를 점점 넓히는 식으로 하고 싶은데 BE도 알면 좋은 것은 사실이니까.

그러나 머리 속으로 생각만 하고 본격적인 계기가 없었는데 3학년 2학기에 전공수업에 치이며 끝없는 고통을 받고 "아.. 쉬고싶다..."는 생각과 함께 나도 모르게 휴학을 결정해버렸다.

휴학을 하고 어차피 많은 목표를 세워봤자 제대로 이루지도 못할거 세 가지 목표를 세웠었는데

1. 자격증$AWS$
2. 포트폴리오 만들기
3. 오픽 도전

이었다.

그런데 빡빡했던 학교생활을 벗어나서 휴학생활을 라식도 하고 F1 직관도 즐기다보니 한 달이 그냥 증발해버렸다. 그렇게 약간씩 휴학때 목표 달성도 해야되는데 슬슬 시간의 압박이 느껴져 스트레스가 커지고 있었다.

그러던 중 학교 홈페이지와 한창 학교를 다니는 친구들에게서 카카오 테크 캠퍼스라는 것을 한다는 것을 듣고 "일단 이거라도 하자"는 생각으로 지원하고 어쩌다보니 붙어버렸다. 이에 관한 내용은 나중에 따로 풀겠다.

어쨌든 카테캠을 따라가다보니 시간이 생각보다 굉장히 빠르게 지났다... 진짜 생각한 것보다 훨씬

그래서 휴학했던 목표달성은 해야될 것 같은데 포트폴리오는 지금까지 했던 플젝들이 뭔가 아쉬웠는데 카테캠에서 할 플젝들 추가한다고 생각하고 그 이후에 만들면 될 것 같고... 오픽은 hmm...$나는 휴학때 놀기만 한 스레기다ㅠㅠ$

그렇다면 남은 것은 자격증뿐이다!!

일단 박죠?

카테캠 일정표를 봤는데 Step1과 Step2 사이에 일주일정도의 여유가 있었다. 어차피 내 성격상 뚜렷한 목표가 없으면 공부 잘 안하니까 일단 신청부터 하자고 생각했다.

공부 방법은 적당히 AWS Skill Builder에서 강의를 듣고 덤프 사이트 아무데나 들어가서 문제풀고 해설보고 하면서 시험 준비를 할 것 같다.

Cloud Practitioner는 AWS 클라우드에 관한 굉장히 기본적인 내용이기 때문에 단순히 시험 합격이 목표가 아닌 기본을 채운다는 생각으로 블로그에 TIL 형식으로 정리하며 공부할 생각이다.

1. 기본 풀이

이 문제는 사실 브론즈2 밖에 안되는 굉장히 쉬운 문제다. 당장 재귀 코드도 다주기 때문에 그대로 풀면 된다.

 #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
 
int cnt;
 
int recursion(const string s, int l, int r){
    cnt++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}
 
int isPalindrome(const string s){
    return recursion(s, 0, s.size()-1);
}
 
int main(){
    fastio;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cnt = 0;
        string s;
        cin >> s;
        cout << isPalindrome(s) << ' ' << cnt << endl;
    }
    return 0;
}

그러나 이대로 풀면 바로 TLE가 나온다. 그렇다면 어떻게 풀어야 될까?

2. 맞왜틀?

이는 c++의 string 타입의 특성에 의한 것이다.

string은 문자열을 함수 인자로 넘겨줄 때 문자열을 통째로 넘겨주기 때문에 시간이 오래걸리지만, char *는 문자열을 넘겨줄 때 시작주소만을 넘겨주기 때문에 string보다 더 빠르다.

이를 해결하는 방법은 총 2가지가 있다.

1. char *사용

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
 
int cnt;
 
int recursion(const char* s, int l, int r){
    cnt++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}
 
int isPalindrome(const char* s){
    return recursion(s, 0, strlen(s)-1);
}
 
int main(){
    fastio;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cnt = 0;
        char s[1001];
        cin >> s;
        cout << isPalindrome(s) << ' ' << cnt << endl;
    }
    return 0;
}

이렇게 string대신 char *로 풀면 된다.

2. s.c_str()사용

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
 
int cnt;
 
int recursion(const char* s, int l, int r){
    cnt++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}
 
int isPalindrome(const char* s){
    return recursion(s, 0, strlen(s)-1);
}
 
int main(){
    fastio;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cnt = 0;
        string s;
        cin >> s;
        cout << isPalindrome(s.c_str()) << ' ' << cnt << endl;
    }
    return 0;
}

 사실상 이 포스트를 작성한 실질적인 이유인데, std::string c_str()함수를 사용하면 string형이 char *형으로 변환된다. 이를 활용하면 기존에 string타입에서는 사용할 수 없었던 strtok, strlen 등 string.h에 포함되어있는 여러 함수들을 사용할 수 있게된다.

 이는 잘 사용한다면 큰 도움이 될 것 같다.

1. 기본 풀이

다른것보다 문제를 이해하는데에 시간이 오래걸렸다. 문제만 이해한다면 그냥 시키는 대로만 하면 풀 수 있다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;
 
int main() {
    fastio;
    int n, num = 64;
    vector<int> v;
    cin >> n;
    v.push_back(64);
 
    while(num > n) {
        int min = v[0];
        int min_idx = 0;
        for(int i = 0; i < v.size(); i++) {
            if(min > v[i]) {
                min = v[i];
                min_idx = i;
            }
        }
        v.erase(v.begin() + min_idx);
        v.push_back(min / 2);
        num -= min / 2;
        if(num < n) {
            v.push_back(min / 2);
            num += min / 2;
        }
    }
 
    if(num == n) cout << v.size() << endl;
    else cout << -1 << endl;
 
    return 0;
}

이해하지 못한 이유

이해를 못한 부분은 1-2.
위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
이 부분인데 처음 64에서 절반 중 하나를 버리고 나머지 하나를 버리면 0인데 뭐 어쩌라는 거지라는 생각을 계속 했다. 이 부분 때문에 구글링도 했는데 나랑 비슷한 사람이 은근 있더라...
어쨌든 저 부분을 풀어서 설명하자면
위에서 자른 절반의 막대와 그 외의 나머지 막대의 길이의 합이 X보다 작으면 절반의 막대 두 개를 그대로 챙기고, 크거나 같다면 둘 중 하나를 버린다는 뜻이다.
즉, 막대의 길이의 합이 X보다 작다면 자르기만 하고 둘 다 챙긴다는 뜻이다.

2. 또 다른 풀이

문제를 풀고난 이후 태그를 봤는데 비트마스킹을 봤다. 그래서 왜 이 문제가 비트마스킹인가? 에 대해서 생각해봤다.
이 문제는 기본 막대기의 크기가 $64$ $(1000000 == 2^6$)으로 주어져있다.
그리고 항상 2씩 나누면서 버릴지 유지할지를 결정한다.

예를 들어보자. 백준에 기본적으로 제시되어 있는 예시인 23을 해보자.

64를 2로 나누면 32. 32는 23보다 크니 버림.

32를 2로 나누면 16. 16은 23보다 작으니 유지

16을 2로 나누면 8. 16 + 8은 23보다 크니 버림.

8을 2로 나누면 4. 16 + 4는 23보다 작으니 유지.

4를 2로 나누면 2. 16 + 4 + 2는 23보다 작으니 유지.

2를 2로 나누면 1. 16 + 4 + 2 + 1은 23과 같다.

결론적으로 23 = 16 + 4 + 2 + 1. 어딘가 익숙한 숫자다.

즉, 항상 2로 나누기 때문에 결과값은 입력값의 비트 개수다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;
 
int main() {
    fastio;
    int x;
    cin >> x;
    cout << bitset<7>(x).count() << endl;
    return 0;
}

여담으로 이 포스팅은 처음으로 마크다운으로 작성되었다.

결국 

$$(100+1+|-1)+$$

이 식을 만족하는지 안하는지를 체크하면 된다는 것이다.

 처음에 오토마타 전공수업때 배웠던 state machine이 생각났었으나 그렇게 코딩할 생각은 못하고... 조건을 생각해서 전부 노가다로 풀려고 했었다. 그러나 아무리 해도 뭔가 조건이 너무 복잡하고 나오는 경우의 수도 많아서 풀기가 힘들었다.

 그래서 가장 처음에 생각했던 state machine을 이용한 풀이를 생각해봤다.

내가 직접그린 NFA다$발그림..$

우선 initial state는 S0이며, 위 그림과 같이 상태가 변화한다.

이를 코드로 작성하면,

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;
 
void solve() {
    int state[8][2] = {
        {1, 2},     //s0
        {-1, 0},    //s1
        {3, -1},    //s2
        {4, -1},    //s3
        {4, 5},     //s4
        {1, 6},     //s5
        {7, 6},     //s6
        {4, 0}      //s7
    };
    int current = 0;
    string s;
    cin >> s;
 
    for(int i = 0; i < s.size(); i++) {
        if(current == -1) break;
        current = state[current][s[i] - '0'];
    }
 
    if(current == 0 || current == 5 || current == 6) cout << "YES" << endl;
    else cout << "NO" << endl;
}
 
int main() {
    fastio;
    int T;
    cin >> T;
    for(int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

 이러한 정말 깔끔한 코드가 나오는데 나는 왜 이걸 조건 하나하나 다 찾아가며 했는지 현타가 오더라...

 그리고 이 포스트를 작성하면서 생각난건데 오토마타의 형식언어를 통해 정규식을 만들 수 있는데 이게 그 정규식이 아닌가? 라는 생각이 들었다. 그런 생각이 들고나서 파이썬에는 정규식을 확인할 수 있는 메소드가 있는걸로 아는데 C++에도 있는지 찾아보았다.

https://modoocode.com/303

있더라... 현타가 좀 많이 왔다.

이를 활용해 코드를 작성해봤다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;
 
int main() {
    fastio;
    int T;
    cin >> T;
    regex re("(100+1+|01)+");
 
    for(int i = 0; i < T; i++) {
        string s;
        cin >> s;
        cout << (regex_match(s, re) ? "YES" : "NO") << endl;
    }
 
    return 0;
}

하... 분명 풀었는데 현타가 정말 많이오는 문제였다.

 +와 -만을 이용한 식을 입력받아 괄호를 적절히 넣어 가장 작은 수를 만드는 문제다.

 괄호를 적절히 넣는다는 말은 그냥 계산 우선순위를 만들라는 것이고 가장 작은 수를 만들기 위해서는 숫자와 -사이에 괄호가 있다면 수가 -가 되어서 가장 작은 수가 될 것이다.

이 예제를 보면 결국

$$55-(50+40)$$

이러한 식이 되어 결과값이 35가 나오게 된다.

 이는 이후 +가 나오면 위 식과 같이 한번에 -를 하게되고 만약 -가 나온다면 한 번 괄호를 닫았다가 다시 괄호를 열게된다. 즉, 이후 어떠한 연산자가 나오든지 상관없이 쭉 -연산만 진행해주면 된다. 따라서 minus에 관한 bool타입 변수를 만들어서 이를 확인하면 될 것 같다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
 
int main() {
    int res = 0;
    string str, num;
    bool minus = false;
    cin >> str;
 
 
    for(int i = 0; i <= str.length(); i++) {
        if(str[i] == '-' || str[i] == '+' || i == str.length()) {
            if(minus) res -= stoi(num);
            else res += stoi(num);
            num = "";
        } else {
            num += str[i];
        }
 
        if(str[i] == '-') minus = true;
    }
    cout << res << endl;
    return 0;
}

이 문제는 사실 군대에서 한 번 풀었었던 문제다. 스택에 여는 괄호는 무조건 push, 닫는 괄호가 나올 때 top과 짝이 맞으면 넘어가고 짝이 맞지 않거나 스택이 비었으면 no를 출력하는 간단한 문제다.

 다만 군대에서 풀었을 때 TLE가 발생했는데 그 이유는 초기화의 문제였다. 이 문제는 C++로 풀었는데, 만약 C로 풀었다면 그냥 top = -1을 대입하면 빠르게 초기화할 수 있었겠지만 stl을 사용하다보니 초기화 방법이 다음과 같이 할 수밖에 없었다.

void init() {
  if(s.empty()) return;
  while(!s.empty()) s.pop();
}

그런데 정말 간단한 방법을 찾았다.

"."이 입력될 때까지 무한루프고, 어차피 한 줄씩 입력받으면서 바로 결과값을 출력한다면 그냥 매 루프마다 스택을 새로 선언하면 되지 않을까?

#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 
    while(1) {
        string temp;
        getline(cin, temp);
        if(temp.length() && temp[0] == '.') break;
 
        stack<char> s;
        bool res = true;
       
        for(int i = 0; i < temp.length(); i++) {
            if(temp[i] == '(' || temp[i] == '[')
                s.push(temp[i]);
            else if(temp[i] == ')') {
                if(!s.empty() && s.top() == '(') s.pop();
                else {
                    res = false;
                    break;    
                }
            } else if(temp[i] == ']') {
                if(!s.empty() && s.top() == '[') s.pop();
                else {
                    res = false;
                    break;    
                }
            }
        }
        if(res && s.empty()) cout << "yes\n";
        else cout << "no\n";
    } 
 
    return 0;
}

그 결과는 성공이였다.

간단히 풀려면 정말 간단하다. 그냥 입력받은 수 배열에 넣고 그 이후 숫자 입력 받을때마다 반복문으로 체크해보면 된다.

#include <stdio.h>
#define MAX_SIZE 100000
 
int main() {
    int n, m;
    int t, temp;
    int arr[MAX_SIZE];
 
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        t = 0;
        scanf("%d", &temp);
        for(int j = 0; j < n; j++) {
            if(arr[j] == temp) {
                printf("1\n");
                t = 1;
                break;
            }
        }
        if(t == 0) printf("0\n");
    }
 
    return 0;
}

그리고 이렇게 대충 반복문으로 코드를 짜면 정말 당연하게도

빨간색 시간초과를 볼 수 있다.

그렇다면 이 문제는 탐색알고리즘을 써야 된다는 건데 그 중 제일 간단하다고 생각하는 이진탐색을 사용했다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100000
 
int compare(const void *a, const void *b);
int bst(int* arr, int start, int end, int target);
 
int main() {
    int n, m;
    int t, temp;
    int arr[MAX_SIZE];
 
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    qsort(arr, n, sizeof(int), compare);
    
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", &temp);
        if(bst(arr, 0, n, temp) != -1) printf("1\n");
        else printf("0\n");
    }
 
    return 0;
}
 
int compare(const void *a, const void *b) {
    if(*(int *)a > *(int *)b) return 1;
    if(*(int *)a < *(int *)b) return -1;
    if(*(int *)a == *(int *)b) return 0;
}
 
int bst(int* arr, int start, int end, int target) {
    if(start > end) return -1;
    int mid = (start + end) / 2;
    if(arr[mid] > target) return bst(arr, start, mid - 1, target);
    else if(arr[mid] < target) return bst(arr, mid + 1, end, target);
    else return mid;
}

 이렇게 예쁜 이진탐색코드를 작성했더니 틀렸다고 나온다. 이때부터 맞왜틀을 계속 외치기 시작한다. 분명 예제도 정상적으로 작동하고 다른거 이상한거 넣어도 정상적으로 작동하는데 왜 안되지?

그때부터 눈이 돌아가서 하나씩 바꿔보기 시작하다가 어쩌다 반례를 찾았다.

원래라면 결과값이 0이 나와야 하지만 1이 나와버렸다. 반례를 찾았으니 이것을 해결하기 위해 열심히 디버거를 돌려봤는데, 

배열에서 우리가 입력을 하고 사용하는 크기는 1이다. 즉, 인덱스는 0까지만 사용한다. 그러나 두번째 bst함수를 들어갔을 때 start와 end가 1이 되고 이에 따라 mid값도 1이 된다. 여기서 arr[1]을 불러왔을 때 이 값이 0이 나오고 그게 target과 같은 수라서 최종 결과로 1이 출력되는 것이다.

 이 결과가 결국엔 사용가능한 index를 넘어가서 이러한 결과가 나온다고 생각해서 bst함수에 함수의 크기 len이라는 인자를 추가해주고 처음 탈출 조건에 start > len이라는 조건을 추가해줬다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100000
 
int compare(const void *a, const void *b);
int bst(int* arr, int start, int end, int target, int len);
 
int main() {
    int n, m;
    int t, temp;
    int* arr;
 
    scanf("%d", &n);
    arr = malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    qsort(arr, n, sizeof(int), compare);
 
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", &temp);
        if(bst(arr, 0, n, temp, n) != -1) printf("1\n");
        else printf("0\n");
    }
 
    return 0;
}
 
int compare(const void *a, const void *b) {
    if(*(int *)a > *(int *)b) return 1;
    else if(*(int *)a < *(int *)b) return -1;
    else return 0;
}
 
int bst(int* arr, int start, int end, int target, int len) {
    if(start > end || start >= len) return -1;
    int mid = (start + end) / 2;
    if(arr[mid] > target) return bst(arr, start, mid - 1, target, len);
    else if(arr[mid] < target) return bst(arr, mid + 1, end, target, len);
    else return mid;
}

 중간에 배열이 포인터 동적할당으로 바꼈는데 혹시나 배열 크기문제 때문인가 싶어서 수정했었는데 아니였다. 그래도 그냥 메모리 크기 생각해서 놔뒀다.