백준 2025년 6월 1주차 정산

다이아3을 찍기 위해 좀 어려운 문제를 풀었다. 풀면서 도파민 충전.. 재밌다!

1월달에 병렬 이분 탐색을 공부하다 그만뒀는데 이번에 다시 도전했다. 계속 보다보니 이번엔 이해가 잘 됐다?

1396번 - 크루스칼 공

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

병렬 이분 탐색 입문 문제?라고 할 수 있다.

$x$ 정점에서 $y$ 정점으로 가는 최소 온도를 구할 때, MST를 이용하면 간단하게 구할 수 있다.

근데 $Q$개의 쿼리에 대해 모두 MST를 적용하면 시간 초과가 나기 때문에 방법을 찾아야 한다.

MST를 구할 때 몇 번째 간선까지 사용할 지 정해두고 수행했을 때 정점 간 이동이 가능한 지 판단하는 결정 문제로 바꿔볼 수 있다. 이 점을 이용해서 병렬 이분 탐색을 적용하면 시간 내에 문제를 풀 수 있다.

주의할 점은, Union Find할 때 rank를 저장해야 한다.

다음 표는 내 코드를 GPT를 이용해서 얻은 시간 복잡도

1. 간선 정렬	sort(edge)	O(M log M)
2. 병렬 이분 탐색 루프	단계 수 ≈ ⌈log₂ M⌉	각 단계마다 아래 연산 수행 → O((M + Q + N) α(N))
2-a. group 초기화	M 회	O(M)
2-b. 쿼리 mid 배치	Q 회	O(Q)
2-c. UF 배열 생성	N 개	O(N)
2-d. 간선 M개 union	M 회	O(M α(N))
2-e. 쿼리 find 2 × Q회	Q 회	O(Q α(N))

그리고 각 쿼리마다 $ [lo, hi] $ 구간을 절반씩 줄이기 때문에 최대 $ \lceil \lg{M} \rceil $ 단계가 필요합니다.

따라서 최종 시간 복잡도는 $ O\bigl((M + Q + N)\,\alpha(N)\,\times\lceil\lg M\rceil\bigr) $ 라네요.

<코드>

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

struct UnionFind {
  vector<int> parent;

  UnionFind(int x) { parent.resize(x , -1); }

  int find(int x) {
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
  }

  void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (parent[x] < parent[y]) {
      parent[x] += parent[y];
      parent[y] = x;
    } else {
      parent[y] += parent[x];
      parent[x] = y;
    }
  }
};

void solve() {
  int N, M; cin >> N >> M;
  vector<array<int, 3>> edge(M);
  for (int i = 0; i < M; i++) {
    int x, y, z; cin >> x >> y >> z;
    edge[i] = {z, x, y};
  }
  sort(all(edge));
  int Q; cin >> Q;
  pair<int, int> query[Q];
  for (int i = 0; i < Q; i++) cin >> query[i].first >> query[i].second;
  vector<int> lo(Q, 0), hi(Q, M - 1);
  vector<int> group[M];
  vector<pii> ans(Q, {-1, -1});
  int cnt = 0;
  while (1) {
    for (int i = 0; i < M; i++) group[i] = {};
    bool cont = false;
    for (int i = 0; i < Q; i++) if (lo[i] <= hi[i]) {
      cont = true;
      group[(lo[i] + hi[i]) / 2].push_back(i);
    }
    if (!cont) break;
    UnionFind uf(N + 1);
    for (int i = 0; i < M; i++) {
      auto [cost, x, y] = edge[i];
      uf.merge(x, y);

      for (auto idx : group[i]) {
        int pa = uf.find(query[idx].first), pb = uf.find(query[idx].second);
        if (pa == pb) {
          hi[idx] = i - 1;
          ans[idx] = {cost, -uf.parent[pa]};
        } else lo[idx] = i + 1;
      }
    }
  }
  for (auto [x, y] : ans) {
    if (x == -1) cout << "-1\n";
    else cout << x << ' ' << y << '\n';
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

16074번 - Mountaineers

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

이 문제는 격자판의 한 지점에서 다른 지점으로 이동하는 경로들 중에서 최고 고도가 가장 작은 것을 찾는 문제다. 이것도 생각해보면 크루스칼 공 문제랑 별반 다르지 않다는 것을 알 수 있다. 그저 격자판으로 바뀌었다는 것 뿐.. 그래서 MST를 사용하기 위해서 격자판을 Edge 리스트로 변환해주었다.

격자판 행과 열 개수도 500이하로 작기 때문에 크게 시간을 고려하지 않아도 됐다.

<코드>

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

struct UnionFind {
  vector<int> parent;

  UnionFind(int x) { parent.resize(x , -1); }

  int find(int x) {
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
  }

  void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (parent[x] < parent[y]) {
      parent[x] += parent[y];
      parent[y] = x;
    } else {
      parent[y] += parent[x];
      parent[x] = y;
    }
  }
};

void solve() {
  int N, M, Q; cin >> N >> M >> Q;
  int arr[N + 1][M + 1];
  for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) cin >> arr[i][j];
  vector<array<int, 3>> edge;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      if (j <= M - 1) edge.push_back({max(arr[i][j], arr[i][j + 1]), (i - 1) * M + j, (i - 1) * M + j + 1});
      if (i <= N - 1) edge.push_back({max(arr[i][j], arr[i + 1][j]), (i - 1) * M + j, i * M + j});
    }
  }
  sort(all(edge));
  vector<int> group[sz(edge)];
  vector<int> lo(Q, 0), hi(Q, sz(edge) - 1), ans(Q);
  pii query[Q];
  for (int i = 0; i < Q; i++) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    query[i] = {(a - 1) * M + b, (c - 1) * M + d};
    if (query[i].first == query[i].second) {
      ans[i] = arr[a][b];
      lo[i] = INF;
    }
  }
  while (1) {
    for (int i = 0; i < sz(edge); i++) group[i] = {};
    bool cont = false;
    for (int i = 0; i < Q; i++) if (lo[i] <= hi[i]) {
      cont = true;
      group[(lo[i] + hi[i]) / 2].push_back(i);
    }
    if (!cont) break;
    UnionFind uf(N * M + 1);
    for (int i = 0; i < sz(edge); i++) {
      auto [cost, x, y] = edge[i];
      uf.merge(x, y);
      for (auto idx : group[i]) {
        int pa = uf.find(query[idx].first), pb = uf.find(query[idx].second);
        if (pa == pb) {
          hi[idx] = i - 1;
          ans[idx] = cost;
        } else lo[idx] = i + 1;
      }
    }
  }
  for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

16902번 - mex

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

수열 A에 속한 각각의 원소를 x와 xor한다. 근데 수열 A에 있는 모든 원소에 대해 계속 xor하면 시간초과.. 그러면, xor 값이 계속 누적된다는 점을 이용해야 한다는 건데..

즉, $ mex(A \oplus accXor) $를 구해야 한다.

$ A_i \le 300\,000 \lt 2^{19} $이므로 최상위 비트(MSB)부터 최하위 비트(LSB)까지 개수를 세고, 이진 트라이를 이용해서 풀이했다. 수열 A의 모든 수에 대해 각 $i$단계($2^i$)마다 등장하는 비트 0과 1의 개수를 저장하면 되는 거라 세그먼트 트리를 이용해서 똑같이 풀 수 있다.

mex를 구하려면, 깊이 $i$의 0의 개수가 $2^i$보다 작으면 그 아래쪽에 빈 수가 있는 것이고 같으면 반대쪽을 탐색하면 된다. 그런데, $accXor$의 $i$번째 비트가 1이면 트라이의 깊이 $i$의 0과 1이 바뀌었다는 것을 이용해서 답을 구하면 된다.

설명이 매우 불친절한데, 어떻게 써야할지 잘 모르겠다.. 설명하기 어렵다.. 코드로 이해하는게 빠를지도.

<코드>

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

int tree[1 << 20];
bool chk[1 << 20];
void insert(int x) {
  if (chk[x]) return;
  chk[x] = 1;
  int node = 1;
  for (int i = 18; i >= 0; i--) {
    int bit = (x >> i) & 1;
    tree[node = node * 2 + bit]++;
  }
}

int getMex(int x) {
  int node = 1;
  int mex = 0;
  for (int i = 18; i >= 0; i--) {
    int bit = (x >> i) & 1;
    node = node * 2 + bit;
    if (tree[node] >= (1 << i)) {
      node ^= 1;
      mex |= (1 << i);
      if (tree[node] == 0) break;
    }
  }
  return mex;
}

void solve() {
  int n, m; cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    insert(x);
  }
  int accXor = 0;
  while (m--) {
    int x; cin >> x;
    accXor ^= x;
    cout << getMex(accXor) << '\n';
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

18798번 - OR과 쿼리

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

$\lor$(bitwise OR)의 특성을 잘 이용해야 한다. 더해지는 방향으로만 수가 변화한다. 다시 말해, 각 비트는 "0 → 1" 로만 변하고 "1 → 0" 으로는 절대 돌아가지 않는다.

그러면 $\lor X$를 할 때, $X$를 각 비트마다 쪼개서 업데이트를 시도할 수 있다. $int$범위 내에서 특정 구간에 대해 약 30번만 업데이트를 진행하면 된다는 것을 의미한다. 특정 구간 내에 이미 해당 비트가 업데이트 됐으면 더이상 진행할 필요가 없다.

최악의 경우 업데이트 시간복잡도 $ O(30NlgN) $ 로 시간 내에 들어온다.

세그 트리의 각 노드는 구조체를 이용해서 관리했다. 해당 구간 전체를 $or$한 값, $and$한 값, $K$와 동일한 개수

<코드>

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

int N, K;

struct Node {
  int orV, andV;
  int cnt;

  Node() : orV(0), andV(~0), cnt(0) {}
  Node(int x, int y, int z) : orV(x), andV(y), cnt(z) {}
};

void updateNode(Node &p, Node &left, Node &right) {
  p.orV = left.orV | right.orV;
  p.andV = left.andV & right.andV;
  p.cnt = left.cnt + right.cnt;
}

struct SegTree {
  vector<Node> arr;
  int size = 1, start;

  SegTree(int x) {
    while (size < x * 2) size *= 2;
    start = size / 2;
    arr.resize(size);
  }

  void init() {
    for (int i = start - 1; i >= 1; i--) {
      updateNode(arr[i], arr[i * 2], arr[i * 2 + 1]);
    }
  }

  void update(int node, int L, int R, int l, int r, int val) {
    if (r < L || R < l) return;
    if (arr[node].andV & val) return;
    if (l == r) {
      arr[node].andV = arr[node].orV |= val;
      arr[node].cnt = arr[node].orV == K;
      return;
    }
    int mid = (l + r) / 2;
    update(node * 2, L, R, l, mid, val);
    update(node * 2 + 1, L, R, mid + 1, r, val);
    updateNode(arr[node], arr[node * 2], arr[node * 2 + 1]);
  }

  int query(int node, int L, int R, int l, int r) {
    if (r < L || R < l) return 0;
    if ((arr[node].orV & K) != K) return 0;
    if (L <= l && r <= R) return arr[node].cnt;
    int mid = (l + r) / 2;
    return query(node * 2, L, R, l, mid) + query(node * 2 + 1, L, R, mid + 1, r);
  }
};


void solve() {
  cin >> N >> K;
  SegTree st(N);
  for (int i = 0; i < N; i++) {
    int x; cin >> x;
    st.arr[st.start + i] = Node(x, x, x == K);
  }
  st.init();
  int Q; cin >> Q;
  while (Q--) {
    int op, l, r; cin >> op >> l >> r;
    l--; r--;
    if (op == 1) {
      int val; cin >> val;
      for (int bit = 1; val; val >>= 1, bit <<= 1) if (val & 1) {
        st.update(1, l, r, 0, st.start - 1, bit);
      }
    } else {
      cout << st.query(1, l, r, 0, st.start - 1) << '\n';
    }
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

'알고리즘 > 백준' 카테고리의 다른 글

백준 1949번 - 우수 마을 [C++] (0)	2025.12.21
백준 1464번 - 뒤집기 3 [C++] (0)	2025.12.19
백준 15961번 - 회전 초밥 [JAVA] (0)	2025.04.04
백준 27172번 - 수 나누기 게임 [C++] (3)	2025.01.02
백준 17404번 - RGB거리 2 [C++] (1)	2025.01.01

백준 2025년 6월 1주차 정산

1396번 - 크루스칼 공

16074번 - Mountaineers

16902번 - mex

18798번 - OR과 쿼리

'알고리즘 > 백준' 카테고리의 다른 글

카테고리별로 찾아보기

보호된 글

티스토리툴바