맥에서 코딩하기 위해, Visual Studio Code를 세팅해보았다.


https://ldgeao99.tistory.com/203 이 링크가 가장 도움이 됐지만 일부 세팅은 다시 해줘야 했다(디버깅용 -g 옵션, a.out 등)


tasks.jon과 launch.json이 필요한데.. 현재 내 설정 공개한다.


tasks.jon

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
{
    "version": "2.0.0",
    "runner": "terminal",
    "type": "shell",
    "echoCommand": true,
    "presentation" : { "reveal": "always" },
    "tasks": [
          //C++ 컴파일
          {
            "label": "C++빌드하자",
            "command": "g++",
            "args": [
                "-g",
                "-std=c++11",
                "${file}",
                "-o",
                "${fileDirname}/${fileBasenameNoExtension}"
            ],
            "group": "build",
 
            //컴파일시 에러를 편집기에 반영
            //참고:   https://code.visualstudio.com/docs/editor/tasks#_defining-a-problem-matcher
 
            "problemMatcher": {
                "fileLocation": [
                    "relative",
                    "${workspaceRoot}"
                ],
                "pattern": {
                    // The regular expression. 
                   //Example to match: helloWorld.c:5:3: warning: implicit declaration of function 'prinft'
                    "regexp": "^(.*):(\\d+):(\\d+):\\s+(warning error):\\s+(.*)$",
                    "file": 1,
                    "line": 2,
                    "column": 3,
                    "severity": 4,
                    "message": 5
                }
            }
        },
        {
 
            "label": "실행",
            "command": "cd ${fileDirname} && ./${fileBasenameNoExtension}",
            "group": "test"
        }
    ]
}
cs


launch.jon

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
{
    // IntelliSense를 사용하여 가능한 특성에 대해 알아보세요.
    // 기존 특성에 대한 설명을 보려면 가리킵니다.
    // 자세한 내용을 보려면 https://go.microsoft.com/fwlink/?linkid=830387을(를) 방문하세요.
    "version": "0.2.0",
    "configurations": [
        {
            "name": "(lldb) 연결",
            "type": "cppdbg",
            "request": "attach",
            "program": "${workspaceFolder}/a.out",
            "processId": "${command:pickProcess}",
            "MIMode": "lldb"
        },
        {
            "name": "(lldb) 시작",
            "type": "cppdbg",
            "request": "launch",
            "program": "${workspaceFolder}/a",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "lldb"
        }
    ]
}
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

인접행렬, 인접리스트  (0) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
C++ bigint class  (1) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15

탑코더할때는 moj를 많이 썼는데, 자동으로 내 템플릿코드 가져오고, testcase 빌드할 수 있게 해주는등 온라인저지 이용시 시간단축에 도움이 된다.


코드포스로 옮기면서 비슷한걸 찾아봤는데 VsCaide라는걸 찾았다.


그냥 visual studio 2019에서 확장 > 확장관리 들어가서 vscaide로 검색하고 설치하면 된다 (간단)



반응형

'Programming > Problem Solving' 카테고리의 다른 글

[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05
Visual Studio Code  (0) 2020.04.03
C++ bigint class  (1) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01

여기나온게 지금까지 내가 알기로는 가장 좋다.

내 github에도 저장해두었다.

아래는 bigint를 사용한 A+B샘플(백준15740문제의 답안이기도 하다)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
#include <bits/stdc++.h>
using namespace std;
/*
  ######################################################################
  #######################   THE   BIG   INT   ##########################
*/
const int base = 1000000000;
const int base_digits = 9;
struct bigint {
    vector<int> a;
    int sign;
    /*<arpa>*/
    int size() {
        if (a.empty())return 0;
        int ans = (a.size() - 1* base_digits;
        int ca = a.back();
        while (ca)
            ans++, ca /= 10;
        return ans;
    }
    bigint operator ^(const bigint& v) {
        bigint ans = 1, a = *this, b = v;
        while (!b.isZero()) {
            if (b % 2)
                ans *= a;
            a *= a, b /= 2;
        }
        return ans;
    }
    string to_string() {
        stringstream ss;
        ss << *this;
        string s;
        ss >> s;
        return s;
    }
    int sumof() {
        string s = to_string();
        int ans = 0;
        for (auto c : s)  ans += c - '0';
        return ans;
    }
    /*</arpa>*/
    bigint() :
        sign(1) {
    }
 
    bigint(long long v) {
        *this = v;
    }
 
    bigint(const string& s) {
        read(s);
    }
 
    void operator=(const bigint& v) {
        sign = v.sign;
        a = v.a;
    }
 
    void operator=(long long v) {
        sign = 1;
        a.clear();
        if (v < 0)
            sign = -1, v = -v;
        for (; v > 0; v = v / base)
            a.push_back(v % base);
    }
 
    bigint operator+(const bigint& v) const {
        if (sign == v.sign) {
            bigint res = v;
 
            for (int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry; ++i) {
                if (i == (int)res.a.size())
                    res.a.push_back(0);
                res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
                carry = res.a[i] >= base;
                if (carry)
                    res.a[i] -= base;
            }
            return res;
        }
        return *this - (-v);
    }
 
    bigint operator-(const bigint& v) const {
        if (sign == v.sign) {
            if (abs() >= v.abs()) {
                bigint res = *this;
                for (int i = 0, carry = 0; i < (int)v.a.size() || carry; ++i) {
                    res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
                    carry = res.a[i] < 0;
                    if (carry)
                        res.a[i] += base;
                }
                res.trim();
                return res;
            }
            return -(v - *this);
        }
        return *this + (-v);
    }
 
    void operator*=(int v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i) {
            if (i == (int)a.size())
                a.push_back(0);
            long long cur = a[i] * (long long)v + carry;
            carry = (int)(cur / base);
            a[i] = (int)(cur % base);
            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
        }
        trim();
    }
 
    bigint operator*(int v) const {
        bigint res = *this;
        res *= v;
        return res;
    }
 
    void operator*=(long long v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i) {
            if (i == (int)a.size())
                a.push_back(0);
            long long cur = a[i] * (long long)v + carry;
            carry = (int)(cur / base);
            a[i] = (int)(cur % base);
            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
        }
        trim();
    }
 
    bigint operator*(long long v) const {
        bigint res = *this;
        res *= v;
        return res;
    }
 
    friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1) {
        int norm = base / (b1.a.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.a.resize(a.a.size());
 
        for (int i = a.a.size() - 1; i >= 0; i--) {
            r *= base;
            r += a.a[i];
            int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
            int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
            int d = ((long long)base * s1 + s2) / b.a.back();
            r -= b * d;
            while (r < 0)
                r += b, --d;
            q.a[i] = d;
        }
 
        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return make_pair(q, r / norm);
    }
 
    bigint operator/(const bigint& v) const {
        return divmod(*this, v).first;
    }
 
    bigint operator%(const bigint& v) const {
        return divmod(*this, v).second;
    }
 
    void operator/=(int v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = (int)a.size() - 1, rem = 0; i >= 0--i) {
            long long cur = a[i] + rem * (long long)base;
            a[i] = (int)(cur / v);
            rem = (int)(cur % v);
        }
        trim();
    }
 
    bigint operator/(int v) const {
        bigint res = *this;
        res /= v;
        return res;
    }
 
    int operator%(int v) const {
        if (v < 0)
            v = -v;
        int m = 0;
        for (int i = a.size() - 1; i >= 0--i)
            m = (a[i] + m * (long long)base) % v;
        return m * sign;
    }
 
    void operator+=(const bigint& v) {
        *this = *this + v;
    }
    void operator-=(const bigint& v) {
        *this = *this - v;
    }
    void operator*=(const bigint& v) {
        *this = *this * v;
    }
    void operator/=(const bigint& v) {
        *this = *this / v;
    }
 
    bool operator<(const bigint& v) const {
        if (sign != v.sign)
            return sign < v.sign;
        if (a.size() != v.a.size())
            return a.size() * sign < v.a.size()* v.sign;
        for (int i = a.size() - 1; i >= 0; i--)
            if (a[i] != v.a[i])
                return a[i] * sign < v.a[i] * sign;
        return false;
    }
 
    bool operator>(const bigint& v) const {
        return v < *this;
    }
    bool operator<=(const bigint& v) const {
        return !(v < *this);
    }
    bool operator>=(const bigint& v) const {
        return !(*this < v);
    }
    bool operator==(const bigint& v) const {
        return !(*this < v) && !(v < *this);
    }
    bool operator!=(const bigint& v) const {
        return *this < v || v < *this;
    }
 
    void trim() {
        while (!a.empty() && !a.back())
            a.pop_back();
        if (a.empty())
            sign = 1;
    }
 
    bool isZero() const {
        return a.empty() || (a.size() == 1 && !a[0]);
    }
 
    bigint operator-() const {
        bigint res = *this;
        res.sign = -sign;
        return res;
    }
 
    bigint abs() const {
        bigint res = *this;
        res.sign *= res.sign;
        return res;
    }
 
    long long longValue() const {
        long long res = 0;
        for (int i = a.size() - 1; i >= 0; i--)
            res = res * base + a[i];
        return res * sign;
    }
 
    friend bigint gcd(const bigint& a, const bigint& b) {
        return b.isZero() ? a : gcd(b, a % b);
    }
    friend bigint lcm(const bigint& a, const bigint& b) {
        return a / gcd(a, b) * b;
    }
 
    void read(const string& s) {
        sign = 1;
        a.clear();
        int pos = 0;
        while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) {
            if (s[pos] == '-')
                sign = -sign;
            ++pos;
        }
        for (int i = s.size() - 1; i >= pos; i -= base_digits) {
            int x = 0;
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            a.push_back(x);
        }
        trim();
    }
 
    friend istream& operator>>(istream& stream, bigint& v) {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }
 
    friend ostream& operator<<(ostream& stream, const bigint& v) {
        if (v.sign == -1)
            stream << '-';
        stream << (v.a.empty() ? 0 : v.a.back());
        for (int i = (int)v.a.size() - 2; i >= 0--i)
            stream << setw(base_digits) << setfill('0'<< v.a[i];
        return stream;
    }
 
    static vector<int> convert_base(const vector<int>& a, int old_digits, int new_digits) {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0= 1;
        for (int i = 1; i < (int)p.size(); i++)
            p[i] = p[i - 1* 10;
        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for (int i = 0; i < (int)a.size(); i++) {
            cur += a[i] * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits) {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int)cur);
        while (!res.empty() && !res.back())
            res.pop_back();
        return res;
    }
 
    typedef vector<long long> vll;
 
    static vll karatsubaMultiply(const vll& a, const vll& b) {
        int n = a.size();
        vll res(n + n);
        if (n <= 32) {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return res;
        }
 
        int k = n >> 1;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());
 
        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);
 
        for (int i = 0; i < k; i++)
            a2[i] += a1[i];
        for (int i = 0; i < k; i++)
            b2[i] += b1[i];
 
        vll r = karatsubaMultiply(a2, b2);
        for (int i = 0; i < (int)a1b1.size(); i++)
            r[i] -= a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            r[i] -= a2b2[i];
 
        for (int i = 0; i < (int)r.size(); i++)
            res[i + k] += r[i];
        for (int i = 0; i < (int)a1b1.size(); i++)
            res[i] += a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            res[i + n] += a2b2[i];
        return res;
    }
 
    bigint operator*(const bigint& v) const {
        vector<int> a6 = convert_base(this->a, base_digits, 6);
        vector<int> b6 = convert_base(v.a, base_digits, 6);
        vll a(a6.begin(), a6.end());
        vll b(b6.begin(), b6.end());
        while (a.size() < b.size())
            a.push_back(0);
        while (b.size() < a.size())
            b.push_back(0);
        while (a.size() & (a.size() - 1))
            a.push_back(0), b.push_back(0);
        vll c = karatsubaMultiply(a, b);
        bigint res;
        res.sign = sign * v.sign;
        for (int i = 0, carry = 0; i < (int)c.size(); i++) {
            long long cur = c[i] + carry;
            res.a.push_back((int)(cur % 1000000));
            carry = (int)(cur / 1000000);
        }
        res.a = convert_base(res.a, 6, base_digits);
        res.trim();
        return res;
    }
};
/*
  #######################   THE   BIG   INT   ##########################
  ######################################################################
*/
 
 
 
 
string a, b;
int main(void)
{
    cin >> a >> b;
    bigint A(a), B(b), C;
    C = A + B;
    cout << C.to_string() << endl;
    return 0;
}
 
 
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

Visual Studio Code  (0) 2020.04.03
코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21

문제는 여기






퀸은 배치된 칸을 기준으로 가로,세로, 그리고 대각선 이동이 가능한 가장 가치있는 말로 다음 빨간선과 같이 움직인다.





다음은 N이 8일때 해 중의 하나이다.



만약 모든 경우의 수에 대해서 재귀를 통해 브루트포스 방식으로 구한다음에 해인지 아닌지를 말단에서 체크하게 되면, DFS가 되는데, 

N=8인 경우 체스판의 칸 개수가 8x8=64개이고 이중에 8개를 고르는 조합의 수가 되므로 $_{64}C_8 = 4,426,165,368$이 되어 44억이 넘어갑니다. 이중에 92개만이 정답이죠.


가로로 겹치지 않게 한줄에 하나의 queen만 놓는식으로 가지치기(백트래킹)를 하게되면 $8^8 = 16,777,216$으로 줄어듭니다. (천6백만)


세로로도 겹치지 않게 permutation을 사용하는 백트래킹의 경우 $8! = 40,320$이 되어 훨씬 줄어듭니다.


다음과 같이 한줄씩 보면서 가로,세로,대각선 모두에 대해 백트래킹을 사용하면 5,508정도로 더 줄어듭니다.


이 문제의 경우 이정도 가지치기를 하면 제한시간내에 맞았습니다를 받을 수 있습니다.





소스코드는 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
 
int N;
int vx[15+1], vy[15+1];
 
int go(int y, int x)
{
    //check valid (back tracking)
    for (int i = 0; i < y; i++) {
        if (y == vy[i] || x == vx[i]) return 0;  //직선겹침
        if (abs(x - vx[i]) == abs(y - vy[i])) return 0//대각겹침
    }
 
    //terminal condition
    if (y == N - 1return 1;
 
    //now record position
    vy[y] = y, vx[y] = x;
 
    //loop
    int r = 0;
    for (int i = 0; i < N; i++) {
        r += go(y + 1, i);
    }
 
    return r;
}
 
int main(void)
{
    scanf("%d"&N);
    int r = 0;
    for (int i = 0; i < N; i++) r += go(0, i);
    printf("%d\n", r);
    return 0;
}
cs






반응형

'Programming > Problem Solving' 카테고리의 다른 글

코드포스 C++ 헬퍼(VsCaide)  (0) 2020.04.02
C++ bigint class  (1) 2020.03.30
행렬코딩  (0) 2020.03.01
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21
백준 팁모음  (0) 2019.03.18

행렬은 알고리즘 문제를 풀 때도 그렇고, 3D 코딩을 할때도 필요하고 여러모로 쓸 경우가 많은것 같아 여기 정리합니다.


먼저 나이브한 행렬곱셈을 구현해보면 다음과 같습니다. (관련 문제: 백준 2740번 행렬곱셈)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll A[101][101], B[101][101], C[101][101];
 
int main(void)
{
    int n, m; scanf("%d %d"&n, &m);
    for (int y = 0; y < n; y++)
    for (int x = 0; x < m; x++
        scanf("%lld"&A[y][x]);
 
    int k; scanf("%d %d"&m, &k);
    for (int y = 0; y < m; y++)
    for (int x = 0; x < k; x++
        scanf("%lld"&B[y][x]);
 
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < k; x++) {
            for (int i = 0; i < m; i++
                C[y][x] += A[y][i] * B[i][x];
            
            printf("%lld ", C[y][x]);
        }
        printf("\n");
    }
 
    return 0;
}
cs


특별할건 없고, 2차원 배열로 잡고 y, x (또는 행, 열 이라고도 표현 가능) 순으로 인덱스 할당해서 계산한다는 것..


근데 한가지 불편한점이 발견되는것은 곱셈결과를 리턴하도록 함수로 뺄 경우에 행렬을 리턴값으로 두기 까다롭다는 것이다 (2차원 배열이니까.. 한가지 work around는 걍 out-value 파라미터를 사용하는것.. 하지만 그렇더라도 리턴값처럼 복사기반이 아니기 때문에 값의 정합성(오버라이팅 된다거나..)에 대해 항상 고민해야한다.) 

따라서 자연스럽게 2차원배열 그 자체로 쓰는것보다 struct나 class로 빼는걸 생각하게 되는데.. 대입연산자나 생성자, 소멸자, 멤버함수등 생각할게 많아지고 코드의 단순함이 많이 훼손(?)된다.


vector의 vector를 사용하면 위의 리턴문제를 비교적 간단하게 해결할 수 있다. 아래 코드를 보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
 
typedef vector<vector<int>> matrix;
 
matrix mul(matrix A, matrix B)
{
    int n = A.size(), m = A[0].size(), k = B[0].size();
    matrix C(n, vector<int>(k));
 
    for (int y = 0; y < n; y++)
    for (int x = 0; x < k; x++)
    for (int i = 0; i < m; i++)
        C[y][x] += A[y][i] * B[i][x];
    return C;
}
 
int main(void)
{
    int n, m; scanf("%d %d"&n, &m);
    matrix A(n, vector<int>(m));
    for (int y = 0; y < n; y++)
    for (int x = 0; x < m; x++
        scanf("%d"&A[y][x]);
 
    int k; scanf("%d %d"&m, &k);
    matrix B(m, vector<int>(k));
    for (int y = 0; y < m; y++)
    for (int x = 0; x < k; x++
        scanf("%d"&B[y][x]);
 
    matrix C(n, vector<int>(k));
    C = mul(A, B);
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < k; x++) {
            printf("%d ", C[y][x]);
        }
        printf("\n");
    }
 
    return 0;
}
cs



연산자 오버로딩을 사용하면 mul 함수대신 * 기호를 사용할수도 있다. 다음을 보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
 
typedef vector<vector<int>> matrix;
 
matrix operator * (matrix A, matrix B) 
{
    int n = A.size(), m = A[0].size(), k = B[0].size();
    matrix C(n, vector<int>(k));
 
    for (int y = 0; y < n; y++)
    for (int x = 0; x < k; x++)
    for (int i = 0; i < m; i++)
        C[y][x] += A[y][i] * B[i][x];
    return C;
}
 
int main(void)
{
    int n, m; scanf("%d %d"&n, &m);
    matrix A(n, vector<int>(m));
    for (int y = 0; y < n; y++)
    for (int x = 0; x < m; x++
        scanf("%d"&A[y][x]);
 
    int k; scanf("%d %d"&m, &k);
    matrix B(m, vector<int>(k));
    for (int y = 0; y < m; y++)
    for (int x = 0; x < k; x++
        scanf("%d"&B[y][x]);
 
    matrix C(n, vector<int>(k));
    C = A * B;
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < k; x++) {
            printf("%d ", C[y][x]);
        }
        printf("\n");
    }
 
    return 0;
}
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

C++ bigint class  (1) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21
백준 팁모음  (0) 2019.03.18
백준 제출시 오류유형 정리  (0) 2019.03.18

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

이 문제 처럼 여러줄의 문장을 입력으로 받는 경우를 생각해보자.


나이브하게 생각하면 아래처럼 하면 될 것 같지만..

1
2
3
4
5
    char line[100];
    while(1){
        scanf("%s", line);
        if(strcmp(line, ".")==0break;
    }
cs


막상해보면 공백이나 줄바꿈 단위로 끊어져서 단어 단위로 들어옴을 알 수 있다. (더군다나 공백이나 줄바꿈 정보는 소실된다)

만약 원하는게 단어단위로 끊어서 처리하는거라면 이렇게 처리해도 상관은 없다. 


하지만 이 문제의 경우처럼 줄바꿈 정보가 필요한 경우는 다른 방법이 필요하다.


1
2
3
4
5
6
    char line[100];
    while(1){
        gets(line);
        if(strcmp(line, ".")==0break;
    }
 
cs

그런경우 이런식으로 scanf 대신 gets를 쓰면 줄단위로 받는게 가능하다.

근데 황당하게도 C++14부터는 gets를 지원하지 않는다. ㄷ ㄷ ㄷ

따라서 이함수를 쓰려면 컴파일러를 C로 두거나 C++11이하로 두어야 한다.

또한가지 번거로움이 있는데 visual studio 2017에서는 gets를 지원하지 않아서 gets_s로 바꿔야 한다 ㅠ(근데 또 이대로 제출하면 안됨)


fgets(line, sizeof(line), stdin);  이거는 visual studio, gcc 둘다되는것 같다.


scanf("%[^\n]", str); 신기하게도 이것도 된다.
scanf("%99[^\n]", str); 좀더 safe하게 하려면 이렇게 100-1 숫자를 앞에 적어주면 된다. 1은 \n용


반응형

'Programming > Problem Solving' 카테고리의 다른 글

C++ bigint class  (1) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01
백준 팁모음  (0) 2019.03.18
백준 제출시 오류유형 정리  (0) 2019.03.18

 

 

c++에서 string 입력받기

이 문제에서 처럼, 공백이 포함된 한 줄 전체를 string에 받아올 일이 있을때는 아래처럼 getline을 쓰면 된다.

1
2
string str;
getline(cin, str);
cs

 

c++로 입출력하기

앞에거는 printf,scanf랑 페어링 끄기, 뒤에거는 입출력반복될때 처리에 대한것

1
ios::sync_with_stdio(0);cin.tie(0);
cs

이거 하고 나면 printf, scanf쓰면 안된다.

헤더파일 단순화 하기

알고리즘 문제를 풀다보면 다음과 같이 헤더파일이 점점 길어지고 지저분해짐을 알 수 있다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <stack>
#include <queue>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <map>
 
using namespace std;
 
int dp[2][1000000+1];
int main(void)
{
cs

 

그 이유는 매번 문제마다 필요한 vector, map, string등을 그때 그때 추가하다보면 귀찮아서져 그냥 슈퍼셋으로 들고가게 되는 현상이 나타난다(...)

 

근데 gcc에서만 지원하긴하지만 다음처럼 <bits/stdc++h>를 쓰면 헤더파일이 무척 깔끔해진다. 자주쓰는 헤더들을 모아서 처리해주는 역할을 해주기 때문이다.

 

1
2
3
4
5
6
7
#include <bits/stdc++.h>
using namespace std;
 
int main(void)
{
    return 0;
}
cs

 

표준은 아니라서 visual c++나 xcode에서는 잘 안되는데,

xcode 기반의 clion을 쓰는 내 경우는 여기 링크에 나온대로 stdc++.h파일을 복사한다음에 다음경로에 설정해주니 잘 되었다.

만약에 bits/stdc++.h의 경로를 못찾겠다고 나오면,

CMakeLists.txt를 열어서 다음 부분을 추가해주면 되었다(include_directories 부분)

 

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1

mac에서 그냥 c++을 쓰는경우 (visual studio code등에서 사용) 다음 경로에 설정해주면 된다.

 

/usr/local/include

 

visual studio를 쓰는 경우는 아래 링크에 복사

 

D:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.31.31103\include

 

그래프 그려주는 툴

https://csacademy.com/app/graph_editor/ 정말 짱인거 같다.

 

stl을 printf-style로 디버깅하기

visual studio가 라인디버깅 성능이 막강하긴 하지만, PS를 하다가 그렇게 하다보면 시간이 너무 많이 흘러가게 된다.

따라서 간단하게 vector나 map등을 print로 찍어보면 좋은데, built-in으로는 그러한 함수가 없고 반드시 루프를 돌려야 한다.

여기 있는 헤더를 include하면 그러한 점을 보완해준다.

 

간단하게 사용법을 보려면 다음 예제를 보자.

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
#include "dbg.h"  // https://github.com/sharkdp/dbg-macro
using namespace std;
int main()
{
    map<intstring> m = { {1,"abc"}, {2,"cde"} };
    dbg(m);
    return 0;
}
cs

 

dbg()로 감싸주기만 하면 그내용을 다음처럼 출력해준다.

1
[..\nothing\nothing.cpp:7 (main)] m = {{1"abc"}, {2"cde"}}
cs

 

물론 온라인저지에 이대로 제출할수는 없기 때문에(커스텀 헤더라, 저지 서버에서는 인식못하고, 속도도 떨어뜨릴거고)

다음과 같이 감싸주는 부분이 필요하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
#ifdef WIN32
#include "dbg.h"  // https://github.com/sharkdp/dbg-macro
#else
#define dbg(...)
#endif
int main()
{
    map<intstring> m = { {1,"abc"}, {2,"cde"} };
    dbg(m);
    return 0;
}
cs

 

나는 간단하게 WIN32으로 감싸주었지만, 좀 더 고민해서 잘 감싸는게 필요할지도 (-DONLINE_JUDGE등 사용)

 

 

입력개수가 명시되지 않은 입력을 받는법

예를 들어 이 문제의 경우 입력개수 없이 받도록 되어 있다. 

while(cin << n) 이렇게 받는걸로 추천되어 있다.

c스타일로 받을경우는 다음처럼 하면 된다.

1
2
3
4
int n;
while(scanf("%d"&n)!=EOF){
    //do something
}
cs

이 문제에서 연습할 수 있다.

 

freopen 사용하기

백준에서는 ONLINE_JUDGE를 define하고 있으므로 다음과 같이 사용하면 파일로 입력을 줄 수 있다.

1
2
3
#ifndef ONLINE_JUDGE
    freopen("input.txt""rt", stdin);
#endif
cs

 

char를 입력받는 방법

이 문제를 보면 숫자를 입력받은 다음에 char를 입력받게 되어 있는데 생각없이 scanf("%d") 한다음에 scanf("%c")를 하게 되면 \n char 때문에 제대로 안된다. 방법은 scanf("%c") 대신에 scanf("\n%c")로 해주면 되긴했다.

또는 숫자는 scanf("%d") 로 받고 그다음은 scanf("%s")로 문자열로 받아서 문자열 파싱을 해도 됨

 

EOF까지 입력받기

이 문제와 같이 N이주어지는게 아니라 단순히 EOF까지 입력을 받으라는 경우가 있다.

이때는 C언어의 경우는 다음처럼 scanf의 리턴값이 EOF임을 체크하면 된다.

#include <cstdio>

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        // process the input
    }
    return 0;
}

 

개행문자까지 문자열을 읽는 방법

3 @ %
10.4 # % @
8 #

위와 같이 어쩔때는 문자가 2개 (@ X), 어쩔때는 문자가 3개 (# % @), 어쩔때는 문자가 한개(#) 주어질때,

아래처럼 %[^\n]를 쓰면 개행문자까지 문자열을 읽을 수가 있다.

double A;
char s[10] = {};
scanf("%lf %[^\n]", &A, s);
for (int i = 0; s[i] != '\0'; ++i) {
    if (s[i] == '@') A *= 3;
    else if (s[i] == '%') A += 5;
    else if (s[i] == '#') A -= 7;
}

이 문제를 참조하자.

반응형

'Programming > Problem Solving' 카테고리의 다른 글

C++ bigint class  (1) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21
백준 제출시 오류유형 정리  (0) 2019.03.18


런타임오류

1. 배열 크기가 너무 작게 잡혔거나


2. 다음처럼 T로 여러 테스트 케이스를 돌리는데 배열이나 변수가 그 밖에 선언되어 있는 경우 발생가능

1
2
3
4
5
6
7
8
 
int t[1001],pre[1001],r[1001];
vector<int> v[1001];
int main(void)
{
    int T;scanf("%d",&T);
    while(T--){
        
cs


반응형

'Programming > Problem Solving' 카테고리의 다른 글

C++ bigint class  (1) 2020.03.30
백준 9663번 N-Queen  (0) 2020.03.15
행렬코딩  (0) 2020.03.01
C언어에서 표준입력으로 string 입력 받기  (0) 2020.02.21
백준 팁모음  (0) 2019.03.18

+ Recent posts