By_Me

.gitignore가 제대로 동작하지 않아서 ignore처리된 파일이 changed 파일에 계속 뜨는 경우

1.1 원인

.gitignore에 파일을 추가하기 전에 stage에 올라간 파일들이 캐시처리되어 기록이 남아있기 때문

1.2 해결

git rm -r --cached .
git add .
git commit -m "fixed untracked files"
git push origin 자신의 branch

👍 해결완료

난이도: G4

문제풀이 : stack 이용

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    stack<pair<int, int>> stk;
    vector<int> res(n, -1);

    int x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;

        while (!stk.empty() && stk.top().second < x)
        {
            res[stk.top().first] = x;
            stk.pop();
        }

        stk.push({i, x});
    }

    for (auto v : res)
        cout << v << " ";

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int n;
long long m;
vector<long long> v;

long long res = INT_MAX;
void selectedNum(int start, int end)
{
    while (start <= end && end < n)
    {
        if (v[end] - v[start] == m)
        {
            res = m;
            return;
        }
        else if (v[end] - v[start] > m)
        {
            res = min(res, v[end] - v[start]);
            start++;
        }
        else
        {
            end++;
        }
    }
}

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    long long x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        v.push_back(x);
    }

    sort(v.begin(), v.end());

    selectedNum(0, 0);

    cout << res;

    return 0;
}

https://www.acmicpc.net/problem/1351

해당 문제는 dp와 hash를 적용하여 문제를 해결하였다,

처음에, dp만을 활용하여 재귀함수 호출을 통해서 문제를 제출했으나, 시간 초과가 발생하였다. 아무래도 n <= 10^ 12, p, q <= 10^9이다보니, memorization을 활용하지 않아서 그런 것 같다.

* 해당 문제는 Top-down 방식으로 dp를 해결하다보니 memorization이 필요하다.

따라서 map STL 라이브러리를 사용하여 해결하는데, 해당 문제에서 dp의 순서는 크게 상관없기때문에 상대적으로 더 간단한 unordered_map을 활용한다. 또한 배열로 선언하기에는 n이 너무 크므로, map을 활용하여 필요한 값들만 따로 저장해두므로 훨씬 편리하다.

또한, 

A[0] = 1

A[i] = A[i/p] + A[j/q] 이므로 다음과 같이 코드를 작성하였다.

#include <iostream>
#include <unordered_map>
using namespace std;

long long n, p, q;
long long res = 0;
unordered_map<long long, long long> m;

long long solution(long long x)
{
    if (x == 0)
        return 1;

    if (m[x] != 0)
    {
        return m[x];
    }
    else
    {
        return m[x] = solution(x / p) + solution(x / q);
    }
}

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> p >> q;

    m[0] = 1;
    cout << solution(n);

    return 0;
}

* 하나의 sentence로 이루어진 문장에서 단어별로 분리하기

#include <iostream>
using namespace std;

int main(int argc, char const *argv[])
{
    string a = "It is time to study", res;

    int pos, max = INT_MIN;
    while ((pos = a.find(' ')) != string::npos)
    {
        string tmp = a.substr(0, pos);
        int len = tmp.size();
        if (len > max)
        {
            max = len;
            res = tmp;
        }

        cout << tmp << '\n';
        a = a.substr(pos + 1);
    }

    if (a.size() > max)
    {
        max = a.size();
        res = a;
    }

    cout << res << '\n';

    return 0;
}

<algorithm> 헤더파일을 통해서 string 안에 소문자, 대문자, 숫자를 구별할 수 있다.

substr(pos, cnt) : pos부터 cnt개수만큼 꺼내온다.

vector와 같이 push_back(), pop_back()로 값을 넣어줄 수 있다.

clear(): string을 비운다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(int argc, char const *argv[])
{
    string a = "Time is 2023Year 10Month";
    cout << a.size() << '\n';

    for (int i = 0; i < a.size(); i++)
    {
        cout << a[i] << " ";
    }
    cout << '\n';

    for (int i = 0; i < a.size(); i++)
    {
        if (isupper(a[i]))
        {
            cout << a[i] << " ";
        }
    }
    cout << '\n';

    for (int i = 0; i < a.size(); i++)
    {
        if (islower(a[i]))
        {
            cout << a[i] << " ";
        }
    }
    cout << '\n';

    for (int i = 0; i < a.size(); i++)
    {
        if (isdigit(a[i]))
        {
            cout << a[i] << " ";
        }
    }
    cout << '\n';

    cout << a.find('Y') << '\n';

    a.push_back('a');
    cout << a << '\n';

    a.pop_back();
    cout << a << '\n';

    a += " 31day";
    cout << a << '\n';

    cout << a.substr(8) << '\n';
    cout << a.substr(8, 4) << '\n';
    a.clear();

    cout << a << '\n';

    return 0;
}