튜브튜브의 개발 저장소

설계

시간 복잡도

X는 최대 10^6인 자연수이다.

X부터 1까지 탐색을 진행할 때 다음 두가지 방법을 이용할 수 있다.

• BFS
• 동적 계획법

BFS의 경우 최악의 경우 시간 복잡도는 O(N) 이하이다.

동적 계획법의 경우 최악의 경우 시간 복잡도는 O(N) 이다.

두 방법 모두 제한시간 0.5초 내에 충분하다.

공간 복잡도

X는 최대 10^6인 자연수이다.

저장해야 되는 정보는 다음과 같다.

• 현재 노드 (index)
• 부모 노드
• 1까지 도달하는데 거치는 노드의 수

이 값 모두 int형으로 충분하다.

테스트케이스

풀이

BFS

BFS를 이용해 X에서 1까지 탐색할 수 있다.

이 때 저장해야 할 정보는 다음과 같다.

• 현재까지 거쳐온 노드의 정보

노드의 정보에서 가장 마지막에 저장되어있는 것이 현재 방문한 노드이므로 vector로만 나타낼 수 있다.

이 때 이전에 방문한 정점을 다시 방문하지 않도록 주의한다.

struct Status {
  vector<int> history;
};

queue<Status> q;
vector<int> answer;
q.push({{N}});

while (!q.empty()) {
  Status cur = q.front();
  q.pop();

  int node = cur.history.back();
  if (node == 1) {
    answer = cur.history;
    break;
  }
  if (visited[node]) continue;
  visited[node] = true;

  vector<int> new_history = cur.history;

  if (node % 3 == 0) {
    new_history.push_back(node / 3);
    q.push({new_history});
    new_history.pop_back();
  }
  if (node % 2 == 0) {
    new_history.push_back(node / 2);
    q.push({new_history});
    new_history.pop_back();
  }
  if (node - 1 > 0) {
    new_history.push_back(node - 1);
    q.push({new_history});
    new_history.pop_back();
  }
}

동적 계획법

동적 계획법을 이용하고, 각 상황별로 어느 노드에서 현재 노드로 왔는지를 기록한다.

이 떄의 시간 복잡도는 O(N)이다.

다음 자료구조에서 나타내는 정보는 다음과 같다.

• 현재 노드 (index)
• 부모 노드
• 1까지 도달하는데 거치는 노드의 수

struct Edge {
  int length; // 1까지 도달하는데 거치는 노드의 수
  int from;   // 부모 노드
};
Edge dp[1000001]; // 현재 노드 index

일반 식은 다음과 같다.

dp[i] = min({dp[i - 1].length + 1, i - 1}, {dp[i / 2].length + 1, i / 2}, {dp[i / 3].length + 1, i / 3})

현재 index에서의 dp값은 현재 index로 도달할 수 있는 3가지 경우 중에서 가장 length가 짧은 경우이다.

초기 값은 다음과 같다.

dp[1] = {0, 0};

이 방법으로 bottom-up 방식으로 풀이한다.

X가 1인 경우는 보장되므로 2부터 탐색을 진행한다.

이 때 i번째를 구할 때 i-1번쨰를 이용해 먼저 구해 초기값을 할당하지 않도록 구성한다.

for (int i = 2; i <= N; i++) {
  dp[i] = {dp[i - 1].length + 1, i - 1};
  if (i % 2 == 0 && dp[i].length > dp[i / 2].length + 1) {
    dp[i] = {dp[i / 2].length + 1, i / 2};
  }
  if (i % 3 == 0 && dp[i].length > dp[i / 3].length + 1) {
    dp[i] = {dp[i / 3].length + 1, i / 3};
  }
}

정리

설계

유사한 문제

• 백준.1922.네트워크 연결

시간 복잡도

정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)

최소 신장 트리를 구하기 위해선 크루스칼 알고리즘과, 프림 알고리즘이 존재한다.

각 경우 시간 복잡도는 다음과 같다.

• 크루스칼 : O(E*log_2(E))
• 프림 : O(E*log_2(V))

두 경우 모두 제한시간 2초 내에 충분하다.

공간 복잡도

가중치 C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어지며

이는 int형으로 충분하다.

최소 스패닝 트리 (Minimum Spanning Tree, MST)

최소 스패닝 트리의 정의는 그래프에서 그래프의 모든 정점을 연결하는 트리이다.

이 때 사이클이 존재하지 않도록 모든 정점을 간선으로 연결한다.

또한 모든 간선의 가중치는 최소값이 되어야 한다.

프림의 알고리즘

시간 복잡도 O(E*log_2(V))

우선 순위 큐를 이용해 간선의 가중치가 낮은 간선부터 순회한다.

이때 해당 간선의 목적지를 이미 방문한 경우 이를 건너 뛴다.

이전에 목적지를 이미 방문했다는 것은 현재 간선보다 가중치가 낮다는 것을 의미하기 때문이다.

즉 가중치가 낮은 간선들부터 순회해 MST를 생성한다.

따라서 처음에는 임의의 점에 속해있는 간선들을 전부 우선순위 큐에 넣고 탐색해야 한다.

struct Edge {
  int vertex, cost;
};

struct Status {
  Edge edge;

  bool operator<(const Status &b) const {
    return edge.cost > b.edge.cost;
  }
};

priority_queue<Status> pq;
vector<bool> visited(V + 1, false);

// 한 정점에서 시작하는 모든 간선을 우선순위 큐에 집어넣음
visited[1] = true;
for (Edge cur : graph[1]) {
  pq.push({cur});
}

long long answer = 0;

while (!pq.empty()) {
  Status cur = pq.top();
  pq.pop();
  Edge edge = cur.edge;

  if (visited[edge.vertex]) continue;
  visited[edge.vertex] = true;

  answer += edge.cost;

  for (Edge next : graph[edge.vertex]) {
    pq.push({next});
  }
}

크루스칼 알고리즘

시간 복잡도 O(E*log_2(E))

무향 연결 가중 그래프에서 간선의 가중치의 합이 최소인 트리를 구하는 것이다.

MST에는 사이클이 없음에 유의한다.

1. 모든 간선의 연결 상태를, 가중치에 따라 오름차순으로 정렬한다.
2. 모든 간선들을 순회하며 탐색한다.
3. MST에 현재 간선을 포함했을 때 사이클이 생기는지 확인한다.
4. 사이클이 생기는 경우 포함하지 않는다.
5. 사이클이 생기지 않는 경우 MST에 해당 간선을 추가한다.

이 경우 자동적으로 cost가 낮은 간선들로만 이루어진 MST를 생성할 수 있다.

여기서 사이클이 생기는지의 여부는 union find (disjoint set)을 이용해 판단할 수 있다.

트리의 정점이 낮은 쪽을 부모로 한다고 했을 때, 두 정점에서 찾은 부모가 같은 경우 사이클이 있다고 판단한다.

struct UnionFind {
  vector<int> cycleTable;

  UnionFind(int size) {
    cycleTable.resize(size + 1);

    for (int i = 1; i <= size; i++) {
      cycleTable[i] = i;
    }
  }

  int findParent(int index) {
    if (cycleTable[index] == index) {
      return index;
    } else {
      int p = findParent(cycleTable[index]);
      cycleTable[index] = p;

      return cycleTable[index];
    }
  }

  void merge(int a, int b) {
    int aRoot = findParent(a);
    int bRoot = findParent(b);

    if (a < b) swap(aRoot, bRoot);
    cycleTable[aRoot] = bRoot;
  }
};

간선은 자동으로 오름차순으로 정렬되어야 하며, 다음과 같은 형태이다.

struct Edge {
  int from, to, weight;

  bool const operator<(const Edge &b) const {
    return weight < b.weight;
  }
};

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

for (Edge l : edges) {
  if (unionfind.findParent(l.from) == unionfind.findParent(l.to)) continue;

  unionfind.merge(l.from, l.to);
  sum += l.weight;
}

정리

프림의 알고리즘 풀이

크루스칼 알고리즘 풀이

고생한 점

V와 E를 입력받고, 간선들을 입력 받을 때 V의 크기만큼 입력받도록 잘못 로직을 구성했었음