[모각코] 9회차

우리가치 모각코 9회차

 

1. 일시

👉🏻 2022년 11월 10일

2. 장소 

👉🏻 성곡도서관 지하 1층 카페 인피니티 / 북악관 카페

 

3. 학습내용

오늘은 각자 풀고 싶은 알고리즘 문제와 추천해주는 문제를 풀어보는 시간을 갖었다.

 

#1913

친구가 추천해준 문제는 1913번의 달팽이 문제다.

1부터 입력한 수의 제곱 수까지 배열에 입력해야 하는데, 배열에 입력할 때의 규칙을 친구와 다르게 생각하였고 내가 생각한 방식으로 구현이 되지 않아 한참 헤맸다.

#include <iostream>
using namespace std;
typedef long long ll;
int square[1000][1000];
struct pos
{
    int x;
    int y;
};
pos dir[4] = {
    {-1, 0},
    {0, 1},
    {1, 0},
    {0, -1},
};
pos prev = dir[0];
int pre = 0;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, start, end;
    ll target;
    cin >> n >> target;
    start = n / 2;
    end = n * n;
    square[start][start] = 1;
    ll num = 2;
    int a = start, b = start;
    int cur = 0;
    int pre = 0;
    int retA = start, retB = start;
    for (int a = start, b = start; num <= end; ++num)
    {
        int dx;
        int dy;

        dx = a + dir[cur].x;
        dy = b + dir[cur].y;

        int flag = -1;
        if (square[dx][dy] == 0)
        {
            pre = cur;
            ++cur;
            if (cur == 4)
                cur = 0;
        }
        else
        {
            dx = a + dir[pre].x;
            dy = b + dir[pre].y;
        }
        a = dx;
        b = dy;
        square[dx][dy] = num;
        if (num == target)
        {
            retA = a;
            retB = b;
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            cout << square[i][j] << " ";
        cout << "\n";
    }
    cout << retA + 1 << " " << retB + 1;
    return 0;
}

 

#13414

내가 정한 두 번째 문제는 13414번의 수강신청 문제인데, 이 문제는 우리학교에서 제출한 문제라고해서 더 흥미가 생겨 풀어보고 싶었다.

친구는 unordered_map을 이용해서 풀었다고 했는데, 나는 map을 이용하였다. 원소를 찾을 때, unordered_map은 O(1), map은 O(logN)이 걸려 N이 128이상일 때부터는 unordered_map을 사용하는 것이 더 효율적이라고 글에서 본 적이 있는데, 제대로 학습하지 않아서 이런 효율을 생각하지 못하고 코드를 작성한 것이 많이 아쉬웠다. 확실히 시간과 메모리를 비교해보니 내가 작성한 코드의 효율이 더 나쁘게 나왔다. 또, 맞힌 사람들의 코드를 보니 comp함수도 바로 ==이 아닌 크기를 비교해줘도 되었을텐데, 많이 부족하다는 것을 느꼈다.

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
map<string, int> m;
string s[1000001];
bool comp(const pair<string, int> a, const pair<string, int> b)
{
    if (a.second == b.second)
        return a.first < b.first;
    else
        return a.second < b.second;
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int k, l;
    cin >> k >> l;

    for (int i = 1; i <= l; ++i)
    {
        cin >> s[i];
    }
    for (int i = 1; i <= l; ++i)
    {
        if (m.find(s[i]) == m.end())
        {
            m.insert(make_pair(s[i], i));
        }
        else
        {
            m[s[i]] = i;
        }
        if (i == l)
            break;
    }
    vector<pair<string, int>> vec(m.begin(), m.end());
    sort(vec.begin(), vec.end(), comp);
    int cnt = 0;
    for (auto &elem : vec)
    {
        cout << elem.first << "\n";
        ++cnt;
        if (cnt == k)
            break;
    }
    return 0;
}

4. 소감(느낀 점)

당연한 말이지만, 작성한 코드를 제출해서 맞는 것도 중요하지만 그 이후에 더 맞힌 사람들의 코드를 보고 본인의 코드에서 부족한 점을 발견하는 것이 발전하기 위해서는 더 중요한 단계인 것 같다. 귀찮아서 그냥 넘어갈 때가 훨씬 더 많은데, 앞으로는 귀찮음을 버리고 더 낮은 자세로 배우는 학습 태도를 기르도록 노력해야겠다.

 

---

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

1913번: 달팽이

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

13414번: 수강신청

https://www.youtube.com/c/BaaarkingDog/videos

BaaarkingDog