RealMySQL 2권 스터디

작년 3월에 1권 스터디로 시작했고, 휴식기간 2달을 포함해서도 1년이 넘는 장기간에 걸쳐서 2권 스터디까지 마무리되었다.

생각보다 딥한 내용이 많았어서 완벽하게 이해하고 넘어가겠다 라기보단 이런게 있다 정도로 읽고 넘어가자는 마인드로 했다.

이번달 내용 중에는 슬로우 쿼리, 미사용 인덱스, 테이블의 작업량 등 이런 세세한 것들을 조회하여 최적화에 도움될 수 있겠다는 생각이 들었고,

생각보다 유용한데 모르고 있는 신기한 기능들이 많았고, 언제 이런것들을 써볼까 하고 관심있게 본 내용들이 많았다.

물론 기억나는건 많진 않다 ^^ 이건 여유를 갖고 복습해야 하지 않을까 싶다.

 

1일 1알고리즘

 

마무리

같이 부트캠프 했던 분들이랑 모각코를 시작했다.

처음에는 오후 9시부터 자기 전까지 진행했었고, 지금은 오전 9시부터 자기 전까지로 변경하여 진행하고 있다.

그래도 같이 공부하는 분들이 있어서 나도 자극받고 할 수 있을 것 같다.

SQL 문제도 풀고있고, CS 공부도 계속 하고있는데 CS는 해도해도 끝이 안나오는것 같다.

그래서인지 이번 회고글을 되게 빠르게 쓰는 느낌인데 사람이 부지런해야지 ^^

 

아 그리고 현대모비스 알고리즘 대회 예선을 했는데 다신 안나가려고 ^^

작년과 마찬가지로 0솔로 마무리했다. 아니 탈주가 맞는듯

반례를 1시간 반만에 찾았지만 내가 생각한 개념이 아니다 라는 결론이 나왔고 그대로 탈주했다.

얘기를 들어보니 빡구현이 많았다는 소문이 들리긴 하지만 어우 다음 대회는 이거보단 낫겠지 라는 회로를 돌려봐야겠다.

'잡담' 카테고리의 다른 글

2024년 7월 회고  (2) 2024.08.01
엘리스 코드 챌린지 예선 후기  (2) 2024.07.20
Nexters 24기 회고  (2) 2024.06.16
5월 회고  (1) 2024.06.07
4월 회고  (2) 2024.05.13

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

 

간단한 dp 문제입니다.

문제가 요구하는 육각수들의 수를 미리 구한 다음 N을 만들기 위해 필요한 육각수의 갯수를 구하여 해결할 수 있습니다.

 

육각수의 수는

1 * 1

2 * 3

3 * 5

4 * 7

5 * 9

이렇게 규칙을 찾을 수 있고, An = n * (2n - 1) 으로 구할 수 있습니다.

 

dp[i] = i를 만들기 위해 필요한 육각수의 최소 갯수

인덱스가 갯수이므로 dp[i] = dp[i - 현재 육각수의 갯수] + 1으로 최솟값을 갱신할 수 있습니다.

 

 

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
#include <iostream>
#define MAX_N 1000001
#define MAX_M 710
using namespace std;
 
int list[MAX_M];
int dp[MAX_N];
int N;
 
void init() {
    for (int i = 1; i < MAX_M; i++) {
        list[i] = i * ((i << 1) - 1);
    }
}
 
void func() {
    init();
 
    dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        dp[i] = 1e9;
        for (int j = 1; j < MAX_M; j++) {
            if (i < list[j]) break;
            dp[i] = min(dp[i], dp[i - list[j]] + 1);
        }
    }
 
    cout << dp[N] << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 17258 인기가 넘쳐흘러  (0) 2024.07.20
boj 1398 동전 문제  (0) 2024.07.04
boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27

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

 

1. 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기
2. 한 장소에서 임의의 개수의 조약돌을 가져가기

조약돌을 가져갈 수 있는 방법은 이렇게 두가지 입니다.

 

"어떤 장소에 조약돌이 더 이상 없는 경우에도 그 장소는 그대로 남아 있어서, 초기에 인접하지 않았던 두 장소가 인접한 것으로 바뀌지 않는다."

그리고 이렇게 조건도 명시되어 있어서 그 자리에 있는 조약돌은 모두 가져가야 되는것을 알 수 있습니다.

 

dp[i]: i번 위치까지 1번 작업을 통해 줄어든 작업의 최대 횟수

우선 최대 작업 횟수는 N번으로,  모두 2번 방법으로 가져가는 경우입니다.

dp를 구할때는 1번 방법만 사용하기 때문에 앞에서 가져간 이후 몇개가 남았는지 유지하는게 중요합니다.

도중에 r = 0이 되었다면 dp[i - 1] + 1으로 갱신하여 횟수를 줄여주도록 합니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 2501
using namespace std;
 
int dp[MAX];
int list[MAX];
int N;
 
void func() {
    for (int i = 1; i <= N; i++) {
        dp[i] = max(dp[i], dp[i - 1]);
        int r = list[i];
        for (int j = i + 1; j <= N; j++) {
            r = list[j] - r;
 
            if (r < 0) break;
            if (!r) dp[j] = max(dp[j], dp[i - 1] + 1);
        }
    }
 
    cout << N - dp[N] << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1398 동전 문제  (0) 2024.07.04
boj 1229 육각수  (0) 2024.06.30
boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13

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

 

같은 위치에 있는 문자를 비교하여 아래와 같이 점수를 받습니다.

1. 두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다.
2. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다.
3. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다.

 

여기서 문자 사이에 공백을 원하는대로 넣을수 있기 때문에

적절하게 공백을 넣어서 점수를 최대로 받아야 하는 문제입니다.

 

dp[idx1][idx2]: 문자열을 idx1, idx2까지 사용했을 때 얻을 수 있는 최대 점수

s1, s2 중 하나의 문자에 공백을 추가하거나 두 문자를 비교하여 a, b, c 중 적절한 값을 더합니다.

위 3가지 중 max를 구하도록 합니다.

 

 

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
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define MAX 3010
using namespace std;
 
string s1, s2;
int dp[MAX][MAX];
int a, b, c;
int len1, len2;
 
int solve(int idx1, int idx2) {
    if (idx1 == len1) return (len2 - idx2) * b;
    if (idx2 == len2) return (len1 - idx1) * b;
 
    int& ret = dp[idx1][idx2];
    if (ret != -1) return ret;
    ret = b + max(solve(idx1 + 1, idx2), solve(idx1, idx2 + 1));
    if (s1[idx1] == s2[idx2]) {
        ret = max(ret, solve(idx1 + 1, idx2 + 1) + a);
    }
    else {
        ret = max(ret, solve(idx1 + 1, idx2 + 1) + c);
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0) << '\n';
}
 
void input() {
    cin >> a >> b >> c >> s1 >> s2;
    len1 = s1.size();
    len2 = s2.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29
boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13

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

 

  • Ai = 1 (i ≤ 0)
  • Ai = A⌊i / P⌋ - X + A⌊i / Q⌋ - Y (i ≥ 1)

여기에서 An을 구하는 문제입니다.

우선 N이 10^13이기 때문에 단순 배열만으로는 해결할 수 없습니다.

그래서 처음 생각해낸건 map을 사용하여 dp를 해결하려고 했습니다.

 

dp 재귀를 돌릴 때 dp[n] != -1이면 dp[n]을 리턴했던것 처럼

map에 포함되어 있는 수는 이미 방문처리가 되었으므로 그 수를 리턴하도록 합니다.

 

 

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
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
 
unordered_map<ll, ll> m;
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n <= 0) return 1LL;
    if (m.find(n) != m.end()) return m[n];
    return m[n] = solve(n / p - x) + solve(n / q - y);
}
 
void func() {
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

근데 생각보다 메모리를 많이 차지하고, 시간도 많이 소요되는 것을 알 수 있습니다.

다른분들의 제출 현황을 보니 이 방법은 비효율적이라는 것을 알 수 있었습니다.

 

제가 확인해봤던 풀이로는 배열을 활용하는 방법이었습니다.

하지만 N의 범위가 10^13이기 때문에 모든 범위를 배열로 해결할 수는 없습니다.

문제에서 허용하는 메모리 512MB 내에서는 가능하기 때문에 10000000 까지는 배열로, 나머지는 재귀로 해결할 수 있었습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 10000001
using namespace std;
typedef long long ll;
 
ll dp[MAX];
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n < MAX) return dp[n];
 
    ll l = 1LL;
    if (n / p - x > 0) l = solve(n / p - x);
 
    ll r = 1LL;
    if (n / q - y > 0) r = solve(n / q - y);
 
    return l + r;
}
 
void init() {
    dp[0] = 1LL;
    for (int i = 1; i < MAX; i++) {
        dp[i] = dp[max(0LL, i / p - x)] + dp[max(0LL, i / q - y)];
    }
}
 
void func() {
    init();
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

아까와 비교하면 메모리와 시간 차이가 정말 많이 난다는 것을 알 수 있습니다.

'algorithm > dp' 카테고리의 다른 글

boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28
boj 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08

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

 

이 문제에서 고려할 부분은 cost를 적절하게 소모하여 1번 방에서 N번 방까지 이동시켜야 합니다.

각 방마다 type이 3개가 있기 때문에 어떤 방에서 cost가 소모되는지, 추가되는지, 유지되는지를 확인해야 합니다.

 

type == E이면 빈 방이며, cost가 들지 않습니다.

type == L이면 레프리콘 방으로, 현재 cost, 이동할 방의 cost 중 높은 값을 갖게 됩니다.

type == T이면 트롤 방으로, 해당 방의 cost만큼 소모해야 합니다. 더 적은 금액을 갖고있다면 지나갈 수 없습니다.

여기서 E 방은 cost가 0인 L방으로 취급이 가능합니다.

따라서 저는 L, T 2가지 경우만 고려했습니다.

 

전체적인 로직으로는 1번 방부터 출발하여 연결되어 있는 모든 방을 bfs로 탐색합니다.

나머지는 위에 작성한 것들을 참고하여 다음 방으로 이동하면 됩니다.

cost마다 어떤 방을 갈 수 있거나 못 가는 경우가 나뉘기 때문에 visit 배열을 2차원 배열로 사용하여 방문처리를 다르게 했습니다.

 

"이는 맨 처음에 모험가가 1번 방에서 시작하려 할 때에도 마찬가지이다."

라는 말이 문제에 명시되어 있어서 1번 방부터 cost를 검사해야 합니다.

1번 방에서는 금액이 0이기 때문에 T번 방이고 cost가 있다면 false를 리턴해주도록 하고,

나머지의 경우에는 해당 방의 cost만큼의 금액을 더하여 출발해주시면 되겠습니다.

 

 

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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX_N 1001
#define MAX_COST 501
using namespace std;
typedef pair<int, int> pii;
 
typedef struct Node {
    char type;
    int cost;
    vector<int> next;
}Node;
 
Node list[MAX_N];
bool visit[MAX_N][MAX_COST];
int N;
 
bool bfs(int s) {
    queue<pii> q;
    if (list[s].type == 'T' && list[s].cost) return false;
    else {
        q.push({ s,list[s].cost });
        visit[s][list[s].cost] = true;
    }
 
    while (!q.empty()) {
        int x = q.front().first;
        int cost = q.front().second;
        q.pop();
 
        if (x == N) return true;
 
        for (auto next : list[x].next) {
            if (list[next].type == 'T') {
                if (cost < list[next].cost) continue;
                if (visit[next][cost - list[next].cost]) continue;
                q.push({ next, cost - list[next].cost });
                visit[next][cost - list[next].cost] = true;
            }
            else {
                if (visit[next][max(cost, list[next].cost)]) continue;
                q.push({ next, max(cost, list[next].cost) });
                visit[next][max(cost, list[next].cost)] = true;
            }
        }
    }
 
    return false;
}
 
void func() {
    if (bfs(1)) cout << "Yes\n";
    else cout << "No\n";
}
 
void input() {
    cin >> N;
    if (!N) exit(0);
 
    int x;
    for (int i = 1; i <= N; i++) {
        cin >> list[i].type >> list[i].cost;
        while (1) {
            cin >> x;
            if (!x) break;
            list[i].next.push_back(x);
        }
    }
}
 
void init() {
    memset(visit, false, sizeof(visit));
    for (int i = 1; i <= N; i++) {
        list[i].next.clear();
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    while (1) {
        input();
        func();
        init();
    }
 
    return 0;
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 27211 도넛 행성  (2) 2024.07.17
boj 19940 피자 오븐  (0) 2024.07.16
boj 2412 암벽 등반  (0) 2024.06.22
boj 14497 주난의 난(難)  (0) 2024.06.21
boj 2132 나무 위의 벌레  (0) 2024.06.17

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

 

(0, 0) 좌표에서 출발하여 주어진 좌표만을 이용해서 목적지인 y = E에 도착하는 최소 이동횟수를 구하는 문제입니다.

좌표 범위가 x * y = 1000000 * 200000 이라 배열로는 해결할 수 없습니다.

그래서 홈이 있는 좌표는 set으로 관리하도록 합니다.

set에는 같은 y좌표들 기준으로 x 좌표를 모아주시면 됩니다. (목적지가 y=E이라 y 좌표 기준)

 

이동은 x, y 각각 -2 ~ +2 범위 내에서만 이동이 가능하고, 범위 내에 홈이 있다면 해당 홈을 지우고 queue에 넣어주시면 됩니다.

일반적으로 bfs는 visit 배열을 사용하여 방문처리를 하지만 범위가 너무 크기 때문에 set에 있는 원소를 지우는 방식으로 방문처리를 대신할 수 있습니다.

 

 

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
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#define MAX 200001
using namespace std;
typedef pair<int, int> pii;
 
set<int> s[MAX];
int N, E;
 
int bfs(int sx, int sy) {
    queue<pii> q;
    q.push({ sx,sy });
    for (int t = 0; !q.empty(); t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            if (y == E) return t;
 
            for (int ny = max(0, y - 2); ny <= min(E, y + 2); ny++) {
                for (int nx = max(0, x - 2); nx <= x + 2; nx++) {
                    if (s[ny].find(nx) == s[ny].end()) continue;
                    q.push({ nx,ny });
                    s[ny].erase(nx);
                }
            }
        }
    }
 
    return -1;
}
 
void func() {
    cout << bfs(0, 0) << '\n';
}
 
void input() {
    int x, y;
    cin >> N >> E;
    for (int i = 0; i < N; i++) {
        cin >> x >> y;
        s[y].insert(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 19940 피자 오븐  (0) 2024.07.16
boj 2310 어드벤처 게임  (0) 2024.06.25
boj 14497 주난의 난(難)  (0) 2024.06.21
boj 2132 나무 위의 벌레  (0) 2024.06.17
boj 16985 Maaaaaaaaaze  (0) 2022.12.16

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

 

bfs에서도 최단 거리를 구하는 문제를 풀 때

꽤 많은 분들이 거리를 queue에 같이 포함시켜서 푸시는걸 본적 있습니다.

 

이 문제는 점프의 최소 횟수를 구하는 문제로, 최단 거리를 구하는 문제와 비슷하다고 할 수 있습니다.

사실 이 문제를 이해하는데 꽤 오랜 시간이 걸렸었는데 문제에서 보여주는 예시와 힌트를 보고는 뇌정지가 왔었습니다.

쉽게 얘기한다면 그냥 0인 좌표들을 탐색으로 쭉 지나가다가 1이 만나면 멈춘다고 생각하시면 될것 같습니다.

 

위에서 언급한것처럼 점프 횟수를 queue에 넣어서 구현할 수도 있겠지만 똑같은 queue를 하나더 사용한다면 그렇게 하지 않고도 해결할 수 있었습니다.

우선 q에는 값이 0인 좌표들만 들어가게 되고, next에는 값이 1인 좌표들이 들어가게 됩니다.

q에 있는 좌표들로 탐색을 쭉 진행하게 되면 그게 1사이클이 되겠고,

다음 next에 있는 원소들을 q에 넣어준다면 다음 사이클을 진행할 수 있습니다.

그렇게 한다면 목적지에 도착했을 때 그 사이클 번호가 답이 될 것입니다.

 

그 외 로직은 간단하게 bfs 탐색을 1을 만날때까지 해주시면 됩니다.

1을 만난다면 그 좌표의 값은 0으로 바꿔주시면 되겠고, (ex, ey) 에 도착했을 때 t를 리턴하도록 합니다.

 

 

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
#include <iostream>
#include <queue>
#define MAX 310
using namespace std;
typedef pair<int, int> pii;
 
char list[MAX][MAX];
bool visit[MAX][MAX];
int direct[4][2] = { { 0,1 }, { 1,0 }, { 0,-1 }, { -1,0 } };
int N, M;
int sx, sy, ex, ey;
 
int bfs() {
    queue<pii> q;
    q.push({sx,sy});
    visit[0][0] = true;
    for (int t = 0; !q.empty(); t++) {
        queue<pii> next;
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            if (x == ex && y == ey) return t;
 
            for (int d = 0; d < 4; d++) {
                int nx = x + direct[d][0];
                int ny = y + direct[d][1];
 
                if (nx <= 0 || ny <= 0 || nx > N || ny > M) continue;
                if (visit[nx][ny]) continue;
 
                visit[nx][ny] = true;
                if (list[nx][ny] == '0') {
                    q.push({ nx,ny });
                }
                if (list[nx][ny] == '1' || list[nx][ny] == '#') {
                    list[nx][ny] = '0';
                    next.push({ nx,ny });
                }
            }
        }
 
        while (!next.empty()) {
            q.push(next.front());
            next.pop();
        }
    }
 
    return -1;
}
 
void func() {
    cout << bfs() << '\n';
}
 
void input() {
    cin >> N >> M >> sx >> sy >> ex >> ey;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 2310 어드벤처 게임  (0) 2024.06.25
boj 2412 암벽 등반  (0) 2024.06.22
boj 2132 나무 위의 벌레  (0) 2024.06.17
boj 16985 Maaaaaaaaaze  (0) 2022.12.16
boj 14466 소가 길을 건너간 이유 6  (0) 2022.10.13

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

 

이 문제는 이해하는데 오래걸린것 같습니다.

"현재 노드에서 거리가 D 이하인 모든 노드에 전단지를 돌릴 수 있다." 라고 문제에 나와있는데

거리가 D 이하인 노드까지만 갈 수 있다 라고 이해를 했어서 어떻게 첫번째 예제의 답이 6이 나오는거지? 생각을 했습니다.

하지만 제 생각을 틀렸었고, "거리가 D 이하인 노드까지는 그곳에 가지 않고도 전달이 가능하다." 라는 말이 맞습니다.

 

그렇다면 dfs를 이용하여 각 노드들의 depth를 구한다음 그 depth가 D 이하라면 전단지를 전달할 수 있게 됩니다.

depth는 리프 노드가 0이고, 자식노드들의 depth 중 최대 + 1로 계산합니다.

depth를 구했다면 D 이하인 depth를 카운팅하면 노드의 갯수를 구할 수 있습니다.

그 다음 거리는 1번 노드까지 돌아와야 하므로 간선의 갯수 * 2로 구할 수 있습니다.

 

 

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
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
using namespace std;
 
vector<int> v[MAX];
bool visit[MAX];
int dep[MAX];
int N, S, D;
 
int dfs(int x) {
    visit[x] = true;
 
    for (auto next : v[x]) {
        if (visit[next]) continue;
        dep[x] = max(dep[x], dfs(next) + 1);
    }
 
    return dep[x];
}
 
void func() {
    dfs(S);
 
    int ret = 0;
    for (int i = 1; i <= N; i++) {
        ret += (dep[i] >= D);
    }
    cout << max(0, ((ret - 1) << 1)) << '\n';
}
 
void input() {
    int x, y;
    cin >> N >> S >> D;
    for (int i = 1; i < N; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 30893 트리 게임  (0) 2024.07.19
boj 19236 청소년 상어  (0) 2021.04.22
boj 2239 스도쿠  (0) 2021.04.16
boj 2458 키 순서  (0) 2021.04.13
boj 14889 스타트와 링크  (0) 2021.03.17

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

 

4년 전에 풀지 못한 문제를 지금에서야 풀게되었습니다.

그땐 어려웠지만 지금도 어렵네요 ㅎ

 

이 문제는 어디서든 출발이 가능하며, 열매를 최대한 많이 먹을 수 있는 경로를 찾아야 합니다.

문제 자체는 트리의 지름 문제와 같은 문제입니다.

열매가 트리의 가중치라고 생각하고 접근한다면 쉽게 해결할 수 있습니다.

 

문제의 로직은

1. 처음 출발할 정점으로 아무지점이나 정합니다. (풀이에서는 1번 정점에서 출발)

2. 1에서 정한 출발 정점에서 가장 열매를 많이 먹을 수 있는 위치를 찾습니다.

3. 2에서 구한 최대 갯수가 정답이 되며, 해당 경로의 양쪽 끝은 1, 2에서 구한 정점이 됩니다. 따라서 두 정점 중 번호가 낮은 정점을 출력합니다.

 

저는 bfs로 풀었지만 dfs로도 풀리는 것으로 알고있어서 시간이 된다면 풀어봐야되겠네요.

 

 

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
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 10001
using namespace std;
typedef pair<int, int> pii;
 
vector<int> v[MAX];
int list[MAX];
int w[MAX];
int weight, idx;
int N;
 
bool isHigher(int we, int i, int x) {
    if (we == w[x]) {
        return i > x;
    }
    return we < w[x];
}
 
void bfs(int x) {
    memset(w, -1, sizeof(w));
 
    queue<int> q;
    q.push(x);
    w[x] = list[x];
    weight = list[x];
    idx = x;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
 
        if (isHigher(weight, idx, now)) {
            idx = now;
            weight = w[now];
        }
 
        for (auto next : v[now]) {
            if (w[next] != -1) continue;
            w[next] = w[now] + list[next];
            q.push(next);
        }
    }
}
 
void func() {
    bfs(1);
    int tmp = idx;
    bfs(idx);
    cout << weight << ' ' << min(tmp, idx) << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
 
    int x, y;
    for (int i = 1; i < N; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 2412 암벽 등반  (0) 2024.06.22
boj 14497 주난의 난(難)  (0) 2024.06.21
boj 16985 Maaaaaaaaaze  (0) 2022.12.16
boj 14466 소가 길을 건너간 이유 6  (0) 2022.10.13
boj 18112 이진수 게임  (0) 2022.09.16

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

 

예전에 재채점되어 틀린 문제를 다시 풀게 되었습니다.

 

덕분에 이 글은 내리게되었네요 ㅠ

이전에는 merge sort로 풀었던 문제라 그건 수정해서 AC를 받았고, 이번에는 다른 방법으로 접근했습니다.

 

이 문제처럼 버블 소트의 특징을 이해하고 있다면 해결할 수 있습니다.

버블소트는 앞뒤의 수를 비교하여 앞의 숫자가 크면 두 수의 위치를 swap 하게 됩니다.

이 문제는 그 swap의 횟수를 구하는 문제로 본인보다 앞에 있지만 더 큰수의 갯수를 세어주면 된다는 결론이 나옵니다.

 

그러면 입력으로 주어지는 정수들로 세그먼트 트리를 이용할 수 있습니다.

본인보다 먼저 트리에 들어간 수 중에 본인보다 큰 수의 갯수를 카운팅하도록 합니다.

하지만 입력의 범위는 절댓값이 10억이라서 배열로 표현하기는 어려울 수 있습니다.

그렇다면 N이 50만이라는 것을 이용하여 좌표압축 기법을 생각할 수 있습니다.

 

https://whyeskang.com/362

 

좌표 압축 (Coordinate Compression)

3년전에 대학 과제로 좌표 압축 기법을 활용하는 문제가 나왔었지만 이해를 못해서 풀지 못했습니다. 지금와서 보니 생각보다 간단했고, 정리하면서 포스팅합니다. 우선 좌표압축이란, 수의 범

whyeskang.com

위 게시글을 참고하시면 문제없이 좌표압축 기법을 사용하실 수 있을 것입니다.

 

좌표압축이 끝났다면 1 ~ N의 범위 내에서 본인보다 큰 수의 갯수를 세그먼트 트리를 활용하여 구할 수 있습니다.

입력이 들어온 순서대로 query 함수를 이용하여 갯수를 구하고, update를 시켜주면 차례대로 구할 수 있습니다.

 

 

[C++]

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
#include <iostream>
#include <algorithm>
#define MAX 500001
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
pii list[MAX];
ll tree[MAX << 2];
int N;
 
void compress() {
    sort(list, list + N);
    int pre = 1e9 + 1;
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (pre != list[i].first) cnt++;
        pre = list[i].first;
        list[i].first = cnt;
    }
    sort(list, list + N, [](pii a, pii b) {
        return a.second < b.second;
    });
}
 
ll update(int node, int l, int r, int x) {
    if (x < l || r < x) return tree[node];
    if (l == r) return ++tree[node];
 
    int m = (l + r) >> 1;
    return tree[node] = update(node << 1, l, m, x) + update((node << 1) + 1, m + 1, r, x);
}
 
ll query(int node, int l, int r, int s, int e) {
    if (s <= l && r <= e) return tree[node];
    if (l > e || s > r) return 0;
 
    int m = (l + r) >> 1;
    return query(node << 1, l, m, s, e) + query((node << 1) + 1, m + 1, r, s, e);
}
 
void func() {
    compress();
 
    ll ret = 0;
    for (int i = 0; i < N; i++) {
        ret += query(1, 1, N, list[i].first + 1, N);
        update(1, 1, N, list[i].first);
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first;
        list[i].second = i;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

Java로 문제를 풀다가 의문이 든게 있는데

 

Arrays.sort(array, from, to, comparator) 메소드와

Arrays.sort(array, comparator) 메소드의 성능 차이에 대해 궁금해졌습니다.

AC를 받은 코드는 Arrays.sort(array, from, to, comparator) 메소드를 사용한 코드고,

TLE를 받은 코드는 Arrays.sort(array, comparator) 메소드를 사용한 코드입니다.

그거 말고는 차이가 없는데 결과가 다르게 나오는 상황이라.. 당황했던 기억이 있습니다.

이걸 시스템상의 문제로 짚고 넘어가도 될만한 것인지는 잘 모르겠네요. 그냥 억까라고 해야하나 이걸

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    private static int list[][];
    private static long tree[];
    private static int N;
 
    private static void compress() {
        Arrays.sort(list, 0, N, (o1, o2) -> {
            if (o1[0] == o2[0]) return o1[1] - o2[1];
            return o1[0] - o2[0];
        });
        int pre = Integer.MAX_VALUE;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (pre != list[i][0]) cnt++;
            pre = list[i][0];
            list[i][0] = cnt;
        }
        Arrays.sort(list, 0, N, Comparator.comparingInt(o -> o[1]));
    }
 
    private static long update(int node, int l, int r, int x) {
        if (x < l || r < x) return tree[node];
        if (l == r) return ++tree[node];
 
        int m = (l + r) >> 1;
        return tree[node] = update(node << 1, l, m, x) + update((node << 1) + 1, m + 1, r, x);
    }
 
    private static long query(int node, int l, int r, int s, int e) {
        if (s <= l && r <= e) return tree[node];
        if (l > e || s > r) return 0L;
 
        int m = (l + r) >> 1;
        return query(node << 1, l, m, s, e) + query((node << 1) + 1, m + 1, r, s, e);
    }
 
    private static void func() {
        compress();
 
        long ret = 0;
        for (int i = 0; i < N; i++) {
            ret += query(1, 1, N, list[i][0] + 1, N);
            update(1, 1, N, list[i][0]);
        }
        System.out.println(ret);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
        tree = new long[(N << 2) + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = i;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 4442 빌보의 생일  (0) 2024.08.01
boj 8330 순열  (0) 2024.07.21
boj 17131 여우가 정보섬에 올라온 이유  (3) 2024.04.25
boj 12895 화려한 마을  (0) 2022.09.07
boj 10167 금광  (0) 2022.09.02

23기 운영진 활동을 마무리하여 수료했고, 시니어 자격으로 첫 활동을 하게되었다.

물론 활동기간은 24년 1월 ~ 3월이었지만 회고 쓰기가 귀찮아서 미루다가 미루다가 미루다가 지금에서야 쓴다 ^^

 

모집

우선 시니어는 대체적으로 선착순으로 모집된다.

그래서 모집 신청이 열리기 5분전부터 대기해서 신청을 파바박 했던 기억이 난다.

직전 기수에 활동점수가 좋았고, 첫 시니어라서 비교적 쉽게 선발될 수 있었다.

내가 항상 넥스터즈 활동을 하면서 목표로 잡았던건 새로운 것들을 경험하기였다.

기술적인게 아니라도 상관없다. 무조건 새로운 것들을 접한다면 그것이 경험이 된다. 라는게 내 마인드다.

 

활동

우선 팀을 고를때는 주제에 대한 나의 관심도를 높게 봤던것 같다.

특정 기술에 대해 경험해보고 싶거나 내가 사용하고싶은 주제를 원했고, 그런 팀이 두팀 정도 있었다.

결과적으로는 1지망에 뽑은 팀에 선정되어 기분이 좋았다.

우선 PM님부터 기술에 욕심이 많아보였고, 발표때 컨벤션이나 코드리뷰를 언급하는걸로 봐서 진심인듯 보였다.

발표가 끝나자마자 질문도 생각하지 않고 가장 먼저 달려가서 어필만 했던 기억이 난다.

 

이번 활동에서 내가 기대했던 기술들은 web socket과 지도 api인데

지도는 FE분들이 다 맡아주셨기 때문에 생각보다 할일이 줄어서 여유롭겠다고 생각했다.

 

 

그러나 그건 오산이었다.

web socket은 우리 BE들이 처음 다뤄보는 기술이었기에 생각보다 오래걸렸고,

각종 버그들을 맞이하면서 최종발표 당일까지 개발하는 결말로 마무리되었다.

 

이 회의록들을 보니 정말.. 열심히 했구나 라는 생각이 들었다.

주 1회는 오프라인으로 전직군 팀원들이 모여서 회의를 했고, 직군별로 정규적인 온라인 회의를 하거나 급할때 긴급 회의를 하기도 했다.

 

처음에는 우리 FE 개발자들이 무서웠다.

git, jira 전략과 컨벤션, 어떤 기술을 사용할지, cicd는 어떤 방식으로 할지 이런것들을 빠른 시간내에 정리하는 것들을 보면서

우리도 뒤쳐지지 않기 위해 최대한 머리를 쥐어짜내며 회의를 했던 기억이 난다.

그리고 변경사항이 적은 pr에도 코멘트가 정말 많이 달리면서 자잘한것 하나하나마저 맞춰가려는 것과 이 프로젝트에 얼마나 진심인지를 알 수 있었다.

덕분에 자극을 받을 수 있었고, 원하는 목표까지 개발할 수 있었다고 생각한다.

 

여태 3번의 기수동안 2번의 넥나잇과 1번의 넥버닝에 참여했지만 이렇게 시간이 빨리갔던 넥나잇은 처음인것 같다.

web socket을 만만하게 봤던 탓인지 생각보다 남아있는 작업들이 많다는걸 느꼈다.

양도 양이지만 handler, interceptor, exception 등 해야할 것들이 정말 많았다.

개발했다가 삭제하고 근데 그걸 다시 살리고 다시 삭제하고.. 이런 일들이 많았던것 같다.

시간이 1주일밖에 남지 않았는데 BE-FE간 socket 연결조차 되지않았어서 해결하는데 시간을 갈아넣었던것 같다.

한참 작업을 하다가 주위를 둘러봤는데 다들.. 여유롭게 놀면서 하시는것 같더라 ㅎㅎㅎ 우리만 작업해..

근데 어떡하겠어.. 좀비마냥 축 늘어져서 기계처럼 작업을 일단 해야했기 때문에 다른생각 갖지 않고 작업만 했다. 아니지.. 다른생각을 가지지 못한거야

중간에 팀원분이 보드게임을 가져와주셔서 1시간정도 리프레쉬 시간을 가졌던건 다행이라고 생각한다. 덕분에 머리가 어떻게든 돌아갔던것 같다 ^^..

 

8주라는 시간동안 정말 개발을 열심히 많이 한것 같다.

시작부터 달렸는데 마지막에도 달리고있었다..

위에서 언급한것처럼 최종발표 당일 새벽에 게더에 모여서 작업을 했었고, 발표 직전까지도 수정하고 최종배포하고 정신이 없었다.

그래도 문제를 해결하고 최종발표를 무사히 마쳐서 다행이라고 생각했다.

 

이번 활동에서 web socket을 다루긴 했지만 부족함이 많다고 느낀다.

동시편집 기능에 메시지에 유용한 stomp를 사용한 것도 그중 한가지다.

시간이 부족하다보니 일단 몇 번 해봤던 기술들을 써서 구현을 하긴 했는데

이걸 stomp를 버리는 방향으로 수정한다거나 websocket 테스트코드를 추가하는 등 앞으로 해야할게 더 많아보인다.

그리고 지금 구현되어 있는것들이 정석적인 방법은 아니라고 생각해서 더 효율적인 방법이 있는지 찾아봐야 할 것이다.

아쉽게도 취준이 겹치고 다른 일들이 있어서 추가 디벨롭을 하지 못한건 아쉽지만 충분히 다뤄볼만한 것들이라 todolist에 정리해야 될것 같다.

 

마무리

매번 프로젝트하면서 느끼지만 만족스러웠던 적은 없었던것 같다.

그만큼 프로젝트에는 진심이었고, 더 잘할 수 있었다는 아쉬움에 그랬던것 같다.

생각보다 볼륨이 컸고, 새벽늦게까지 작업하는 팀원들이 진짜 너무 고생한것 같다.

그렇게 했는데도 최종발표 당일 새벽에 1시간씩 교대로 자면서 QA 봐주고 수정하고 했던건.. 기억에 계속 남을것 같다.

작업이 늦게 끝나서 세션 장소에 가서 시연 시나리오를 짜고 테스트해봤는데 또 에러를 발견해서 발표직전까지 수정했던건 정말 아찔했다.

다른분들도 우리들의 다급한 모습을 보면서 안쓰러움을 느끼시진 않으셨을까 생각해본다 ㅎ.. 그래도 열심히 했잖아 ^^!

 

이번에도 정말 좋은 팀원들을 만났다.

웹 프로젝트였고, BE2 FE2 DE2로 총 6명으로 구성되었다.

프론트엔드 개발자분들은 시작부터 전력질주를 하며 내 동기부여를 이끌어내주셨고,

디자이너분들은 프레이머를 이용해서 반응형 웹이나 발표자료들을 만드시는걸 보고 신기했다. 디자이너는 언제나 새롭고 신기한걸 하신다.

우리 백엔드는 둘다 프로젝트를 2개씩 하고있었는데 socket과 redis의 지옥에서 헤어나오기 위한 노력을 정말 많이 해주셨다.

대부분이 넥스터즈 외에 무언가를 하고 있었음에도 이정도의 결과가 나왔으니 만족하지만 추가개발은 무산된것 같아서 아쉽긴 하다.

 

내가 직전기수에 운영진이었어서 그런지 이번 운영진들은 어떻게 하는지 관심을 가졌던것 같다.

이번기수 운영진분들도 정말 열심히 준비하고 진행도 깔끔하게 잘한다는 것을 느꼈다.

기존에 진행하던 것들을 이어서 하기도, 새로운걸로 바꿔보기도 하면서 회원들의 니즈를 맞추려고 하는 것들이 보였다.

아 물론 우리가 인수인계를 잘해준 것도 어느정도 있었겠지만 ^^^^^^

 

무엇보다도 놀랐던건 6주차에 넥밋업 세션이 진행되어 내/외부에서 강연자분들을 초청하여 발표를 진행하고, 인사이트를 얻는 시간이 있다.

내가 했을 때와는 다르게 유명한분들도 섭외가 되고, 전체적으로 퀄리티가 확 높아진 것 같은 느낌이 들었다.

이 세션에서 나는 정말 많은 인사이트를 얻었고, 마인드에 변화를 가져가는 계기가 되었다.

나중에 운영진에게 물어보니 일단 시도해봤더니 그쪽에서 수락을 해주셨다고 한다..

이번 운영진분들도 끝까지 진행 잘해주셔서 고생 많으셨다고 말씀드리고싶다.

 

22기부터 쉬지않고 활동을 했지만 다음 기수는 쉬려고 한다.

작년까지만 해도 이거 하면서 취준하면 되지~ 라는 마인드였지만 막상 하니까 쉽지않다는 것을 느꼈다.

그래서 이번에는 온전히 취준에만 집중해보려는 생각으로 25기 신청은 하지 않았다.

지금까지의 생각은 재취업을 한 이후에 다시 활동할 생각이지만 사람이라는게 언제든지 바뀔 수 있으니 가능성은 열어두려고 한다.

 

Nexters 24기

AUDY 개발한 피컵부 팀

모두 고생 많으셨습니다!

'잡담' 카테고리의 다른 글

엘리스 코드 챌린지 예선 후기  (2) 2024.07.20
6월 회고  (0) 2024.07.01
5월 회고  (1) 2024.06.07
4월 회고  (2) 2024.05.13
3월 회고  (0) 2024.04.13

+ Recent posts

티스토리툴바