12849번: 본대 산책

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.

www.acmicpc.net

난이도 정답률 (%) 시간 제한 (초)
Silver I 63.764 1

설계

시간 복잡도

D는 다음과 같다. (1 ≤ D ≤ 100,000)

D분 일 때, 정보 과학관에 도착해야 한다.

모든 경우를 탐색할 경우 제한 시간 내에 불가능하다. (1,000,000,007 이상이 소요되기 때문)

따라서 이전 연산 결과를 활용한 동적 계획법을 사용한다.

이 경우 시간 복잡도는 O(N) 이므로 제한 시간 1초 내에 충분하다.

 

공간 복잡도

정답은 1,000,000,007로 나눈 수 이기 때문에, 1,000,000,007 이하의 정수이다.

경우의 수를 계산할 때 이 범위를 초과할 수 있으므로 연산 과정들은 long long형으로 선언한다.

 

동적 계획법

현재 위치로 오는 경우는, 현재 위치와 연결된 위치들의 이전에 방문한 횟수들을 더한 값이다.

따라서 일반식은 다음과 같이 설정할 수 있다.

// a, b는 i와 연결되어 있는 위치
dp[n][i] = dp[n-1][a] + dp[n-1][b] ...

dp를 다음과 같이 설정한다.

dp[n][index]  // n초 후 해당 건물 위치 index로 가는 경우의 수

여기서 n이 매우 크고, n을 계산할 때는 n-1번째 값만 필요하므로 dp 배열을 1차원으로 설정한다.

여기서 정보과학관에서 출발해야 하는데, index를 다음과 같이 설정한다.

  • 0 : 정보과학관
  • 1 : 전산관
  • 2 : 신앙관
  • 3 : 미래관
  • 4 : 진리관
  • 5 : 환경직기념관
  • 6 : 학생회관
  • 7 : 형남공학관

정보 과학관에서 출발하므로 dp의 0번째는 = 1이 된다.

dp[8] = {1, 0, 0, 0, 0, 0, 0, 0}; // n = 0 일 때

탐색을 진행하면서 dp의 값들을 이전 값들을 이용해 갱신한다.

이 때 이동할 수 있는 위치는 정해져 있으므로 연결된 점들을 이용한다.

dp[0] = 1;
while (D--) {
  long long temp[8] = {
      0,
  };

  for (int i = 0; i < 8; i++) {
    temp[0] = dp[1] + dp[3];
    temp[1] = dp[0] + dp[2] + dp[3];
    temp[2] = dp[1] + dp[3] + dp[4] + dp[5];
    temp[3] = dp[0] + dp[1] + dp[2] + dp[5];
    temp[4] = dp[2] + dp[5] + dp[6];
    temp[5] = dp[3] + dp[2] + dp[4] + dp[7];
    temp[6] = dp[4] + dp[7];
    temp[7] = dp[5] + dp[6];
  }

  for (int i = 0; i < 8; i++) {
    dp[i] = temp[i] % 1000000007;
  }
}

 

테스트케이스

종류 input output
예제 10 9857

 

코드

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

 

정리

내 코드 (ms) 빠른 코드 (ms)
0 0

 

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

백준.12849.본대 산책  (0) 2021.01.26
백준.12852.1로 만들기 2  (0) 2021.01.25
백준.1197.최소 스패닝 트리  (0) 2021.01.24
큰 수 연산 (Big Integer)  (0) 2021.01.04
삼성 7699. 수지의 수지 맞는 여행  (0) 2019.12.31
삼성 9088. 다이아몬드  (0) 2019.12.27
 

12852번: 1로 만들기 2

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

www.acmicpc.net

난이도 정답률 (%) 시간 제한 (초)
Silver I 52.488 0.5

 

설계

시간 복잡도

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

 

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

  • BFS
  • 동적 계획법

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

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

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

 

공간 복잡도

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

 

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

 

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

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

 

테스트케이스

종류 input output
예제 1 2 1
2 1
예제 2 10 3
10 9 3 1
임계값 (최소) 1 0
1
임계값 (최대) 1000000 19
1000000 500000 250000 125000 62500 31250 15625 15624 7812 3906 1953 651 217 216 108 54 27 9 3 1 

 

풀이

BFS

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

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();
  }
}

 

동적 계획법

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

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

이 떄의 시간 복잡도는 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};
  }
}

 

정리

내 코드 (ms) 빠른 코드 (ms)
0 0

 

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

백준.12849.본대 산책  (0) 2021.01.26
백준.12852.1로 만들기 2  (0) 2021.01.25
백준.1197.최소 스패닝 트리  (0) 2021.01.24
큰 수 연산 (Big Integer)  (0) 2021.01.04
삼성 7699. 수지의 수지 맞는 여행  (0) 2019.12.31
삼성 9088. 다이아몬드  (0) 2019.12.27
 

1197번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이

www.acmicpc.net

난이도 정답률 (%) 시간 제한 (초)
Gold IV 39.708 2

설계

유사한 문제

시간 복잡도

정점의 개수 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;
}

정리

프림의 알고리즘 풀이

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

크루스칼 알고리즘 풀이

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

내 코드 (ms) 빠른 코드 (ms)
68 12

고생한 점

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

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

백준.12849.본대 산책  (0) 2021.01.26
백준.12852.1로 만들기 2  (0) 2021.01.25
백준.1197.최소 스패닝 트리  (0) 2021.01.24
큰 수 연산 (Big Integer)  (0) 2021.01.04
삼성 7699. 수지의 수지 맞는 여행  (0) 2019.12.31
삼성 9088. 다이아몬드  (0) 2019.12.27

큰 수 연산

숫자가 매우 큰 경우에 사칙연산을 수행하는 경우 변수의 범위를 초과한다.

따라서 문자열로 치환해 연산을 수행해줘야 한다.

각 언어별 큰수연산(정수, 실수) 연산 지원은 다음과 같다.

언어 큰 정수 큰 실수
Java java.math.BigInteger java.math.BigDecimal
Python int decimal.Decimal
Javascript bigint  
C++ cpp_int (boost) cpp_dec_float (boost)

일반적으로 배열의 성질을 이용해 구한다.

덧셈

string bigNumberAdd(string a, string b) {
  int carry = 0;
  string result = "";

  while (!a.empty() || !b.empty() || carry) {
    if (!a.empty()) {
      carry += a.back() - '0';
      a.pop_back();
    }

    if (!b.empty()) {
      carry += b.back() - '0';
      b.pop_back();
    }

    result += ((carry % 10) + '0');
    carry /= 10;
  }

  reverse(result.begin(), result.end());
  return result;
}

뺄셈

bool isSmaller(string a, string b) {
  int lengthA = a.length(), lengthB = b.length();

  if (lengthA < lengthB) {
    return true;
  }
  if (lengthB < lengthA) {
    return false;
  }

  for (int i = 0; i < lengthA; i++)
    if (a[i] < b[i]) {
      return true;
    } else if (a[i] > b[i]) {
      return false;
    }

  return false;
}

string bigNumberSub(string str1, string str2) {
  if (isSmaller(str1, str2)) {
    swap(str1, str2);
  }

  string result = "";
  int n1 = str1.length(), n2 = str2.length();

  reverse(str1.begin(), str1.end());
  reverse(str2.begin(), str2.end());

  int carry = 0;

  for (int i = 0; i < n2; i++) {
    int sub = ((str1[i] - '0') - (str2[i] - '0') - carry);

    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else
      carry = 0;

    result += (sub + '0');
  }

  for (int i = n2; i < n1; i++) {
    int sub = ((str1[i] - '0') - carry);

    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else {
      carry = 0;
    }

    result += (sub + '0');
  }

  reverse(result.begin(), result.end());
  return result;
}

7699. 수지의 수지 맞는 여행

링크

난이도 : d4
정답률 : _51%

설계

자료구조

이미 방문한 알파벳은 방분하지 않으므로 visited['Z' - 'A'] 를 만들어 사용한다.

backtracking

이미 정답의 max를 구한 경우, 더이상 탐색하지 않아도 된다.

가능한 max의 경우는 입력된 지도의 알파벳 종류 + 1이다.

따라서 dfs 함수에 다음 코드를 추가해준다

if (answer > MAX) {
  return;
}

정리

내 코드 빠른 코드
18 ms 18 ms

내 코드가 제일 빠른 코드이다.

고생한 점

처음에 BFS로 풀려고 한 경우 계속 시간초과가 발생했다.

DFS로 바꾼 뒤 완전탐색을 수행했을 때 약 3초정도의 시간이 걸렸다.

코드

#include <algorithm>
#include <iostream>

using namespace std;

struct axis {
  int y, x;
};

axis moves[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char map[20][20];
int answer, R, C, MAX;
bool visited['Z' - 'A'];

void clear() {
  for (int i = 0; i < 'Z' - 'A'; i++) {
    visited[i] = 0;
  }
  answer = 1, MAX = 0;
}

void dfs(axis current, int count) {
  answer = max(answer, count);

  if (answer > MAX) {
    return;
  }

  visited[map[current.y][current.x] - 'A'] = 1;

  for (int dir = 0; dir < 4; dir++) {
    axis next = current;
    next.x += moves[dir].x;
    next.y += moves[dir].y;

    if (next.y < 0 || next.y >= R || next.x < 0 || next.x >= C ||
        visited[map[next.y][next.x] - 'A']) {
      continue;
    }

    dfs(next, count + 1);
  }

  visited[map[current.y][current.x] - 'A'] = 0;
}

void solution(int test_case) {
  clear();
  cin >> R >> C;

  bool alphabets['Z' - 'A'] = {
      0,
  };

  for (int y = 0; y < R; y++) {
    for (int x = 0; x < C; x++) {
      cin >> map[y][x];
      alphabets[map[y][x] - 'A'] = 1;
    }
  }

  for (bool b : alphabets) {
    b ? MAX += 1 : MAX;
  }

  dfs(axis{0, 0}, 1);

  cout << "#" << test_case << " " << answer << "\n";
}

int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int T;
  cin >> T;

  for (int test_case = 1; test_case <= T; test_case++) {
    solution(test_case);
  }

  return 0;
}

+ Recent posts