Rust의 기본 라이브러리에서 제공하지 않지만, BOJ 환경에서 추가로 사용할 수 있는 기능을 소개합니다. Rust에는 extern 키워드를 사용한 FFI (Foreign Function Interface) 기능이 존재합니다. 이를 통해서 시스템에 존재하는 공유 라이브러리를 불러와 그 안의 함수(혹은 변수)를 가져와 사용할 수 있습니다. #[link(name = "my_library")] extern "C" { fn some_function() -> bool; } 위 코드는 rustc로 컴파일 시에 -lmy_library 옵션을 링커에게 전달하고, 시스템에 libmy_library.so가 있다면 컴파일이 성공합니다. 또한 런타임에 libmy_library.so에서 some_function() 함수를 불러오게 됩니다....
그래프 구조를 어떻게 나타낼 수 있는지 알아보겠습니다. 2022-04-21 수정: 잘못된 인접 배열 그림을 수정했습니다. 인접 행렬 (Adjacency Matrix) 그래프를 2차원 배열 형태로 표현하는 방법으로 인접 행렬이 있습니다. 인접 행렬 $a$에 대해서, $a[i][j]$의 값은 $i$와 $j$가 연결되어 있으면 1, 아니면 0을 가집니다. 방향성이 없는 경우 $a[i][j]$와 $a[j][i]$는 같습니다. 그래프에 따라서 가중치가 있는 경우 1 대신 가중치를 담을 수도 있고, 같은 끝점에 대해서 여러 개의 간선이 있는 경우 간선의 개수를 담을 수도 있습니다....
연속 부분합을 모두 살피기 위해서는 $O(N^2)$ 시간이 걸립니다. 좀 더 빠른 풀이가 필요합니다. 수열의 모든 수가 자연수이기 때문에, 연속된 수의 길이가 늘어나면 부분합은 반드시 증가합니다. 오른쪽 끝이 $1, 2, \cdots, i$번째 수인 부분합을 모두 살펴봤다고 하고, $j$번째 수부터 $i$번째 수까지의 합이 $S$ 이상인 최대의 $j$를 찾았다고 합시다. 그러면 $j$번째 수부터 $i + 1$번째 수까지의 합은 반드시 $S$ 이상이므로, 오른쪽 끝이 $i + 1$번째 수인 부분합을 살펴볼 때는 왼쪽 끝을 $j + 1$부터 하여 살펴보면 충분합니다....
단계적으로 최소비용을 구해나간다는 문제의 서술로부터 다이나믹 프로그래밍을 떠올릴 수 있었습니다. $C(i, j)$를 인덱스 $i$부터 $j$까지 파일을 합하는 최소 비용이라 정의하면, $$C(i, j) = \min_{i \le k \lt j}[C(i, k) + C(k + 1, j)] + \sum_{n = i}^{j} \mathrm{Size}[n]$$ $\mathrm{Size}[i..j]$는 부분합을 이용해 $O(1)$만에 구할 수 있으므로 전체 시간복잡도는 $O(K^3)$이 됩니다. 코드 use std::fmt::Write; use std::io::{stdin, Read}; fn main() { let mut input = String::new(); stdin().read_to_string(&mut input).unwrap(); let mut output = String::new(); let mut input = input....
Lazy Propagation을 이용한 세그먼트 트리로 접근하기에는 피보나치 수의 합을 빠르게 구할 수 없을 것 같습니다. 모든 쿼리를 적용한 후의 결과만 출력하면 되기 때문에 모든 쿼리를 한 번에 처리하는 방법을 떠올리려 했습니다. 이전 항과 다음 항을 이용하여 피보나치 수를 구해나갈 때, $i$번째 항을 계산하는 중 $i = l$인 쿼리가 존재한다면 다음 항 값에 $1 (= F_1)$을 더해줍니다. $i = r$인 쿼리가 존재한다면 이전 항에서 $F_{r - l}$을, 다음 항에서 $F_{r - l + 1}$을 빼 주면 최종 수열을 구해나갈 수 있습니다....
원이 교차하지 않으므로 접하는 경우만 생각하면 됩니다. 원의 지름 끝이 원들에 의해 연결되어 있다면 영역이 2개로 나뉘고, 그 외의 경우에는 1개가 생깁니다. 연결성 확인은 서로소 집합 자료구조를 통해 쉽게 할 수 있지만, x좌표의 범위가 넓어 좌표 압축이 필요합니다. 압축에 O(NlogN), 죄표를 검색하는 데 O(logN), 연결성 확인에 O(log*N)이므로 O(NlogNlog*N)에 해결할 수 있습니다. 코드 use std::io::{stdin, Read}; fn main() { let mut input = String::new(); stdin().read_to_string(&mut input).unwrap(); let mut input = input.split_ascii_whitespace(); let n = input....
자갈도로 K개를 포함하는 스패닝 트리를 찾는 문제입니다. 불가능한 경우를 일단 거르기 위해 자갈 도로를 최대한 사용해서 만들 수 있는 트리를 살펴봤습니다. 이 트리의 간선이 K개 미만이면 K개의 무료 자갈 도로를 사용했을 때 오직 하나의 무료도로로 이루어진 경로가 있다는 조건에 위배됩니다. 또한 이 트리의 정보를 최대한 이용할 수 없을까 생각하다가 아이디어를 떠올렸습니다. 어떤 콘크리트 도로가 이 트리에서 이미 이어진 두 정점을 잇는다면, 임의의 자갈 도로를 제거하고 이 콘크리트 도로를 추가하는 것으로 정점 간 연결성을 유지하되 자갈 도로의 개수를 하나 줄일 수 있다는 것입니다....
탐색 최적화보다는 구현이 중심인 문제입니다. 각 테트로미노에 대해서 확인해야 할 좌표를 전처리해두고 합의 최댓값을 구했습니다. 코드 use std::io::{stdin, Read}; static TETROMINOES: [[(usize, usize); 4]; 19] = [ // I [(0, 0), (0, 1), (0, 2), (0, 3)], [(0, 0), (1, 0), (2, 0), (3, 0)], // O [(0, 0), (0, 1), (1, 0), (1, 1)], // L [(0, 0), (1, 0), (2, 0), (2, 1)], [(1, 0), (1, 1), (1, 2), (0, 2)], [(0, 0), (0, 1), (1, 1), (2, 1)], [(0, 0), (1, 0), (0, 1), (0, 2)], // J [(0, 1), (1, 1), (2, 1), (2, 0)], [(0, 0), (0, 1), (0, 2), (1, 2)], [(0, 0), (1, 0), (2, 0), (0, 1)], [(0, 0), (1, 0), (1, 1), (1, 2)], // S [(0, 1), (1, 1), (1, 0), (0, 2)], [(0, 0), (1, 0), (1, 1), (2, 1)], // Z [(0, 0), (0, 1), (1, 1), (1, 2)], [(0, 1), (1, 1), (1, 0), (2, 0)], // T [(0, 0), (0, 1), (0, 2), (1, 1)], [(0, 0), (1, 0), (2, 0), (1, 1)], [(0, 1), (1, 0), (1, 1), (1, 2)], [(0, 1), (1, 1), (2, 1), (1, 0)], ]; fn main() { let mut input = String::new(); stdin()....
주어진 규칙에 따라 시뮬레이션하는 문제입니다. 현재 위치와 방향을 관리하면서 회전을 처리하는 것이 중요하다고 생각합니다. 한편 규칙이 어느 정도 혼란을 줄 수 있게 서술되어 있는 것 같아 주의가 필요해 보입니다. 코드 use std::io::{stdin, Read}; fn main() { let mut input = String::new(); stdin().read_to_string(&mut input).unwrap(); let mut input = input.split_ascii_whitespace().map(str::parse).flatten(); let n = input.next().unwrap(); let m = input.next().unwrap(); let mut r = input.next().unwrap(); let mut c = input.next().unwrap(); let d = input.next().unwrap(); let mut grid = Matrix(input....
경우의 수 문제라서 일단 DP로 접근해 봤습니다. 합이 N이 되도록 정수를 배열하면, 마지막 수가 0인 경우 마지막 수가 1인 경우 ⋯ 마지막 수가 N인 경우 로 나뉘게 됩니다. $f(N, K)$: 0부터 $N$까지의 정수 $K$개를 더해서 합이 $N$이 되는 경우의 수일 때 각 경우에 마지막 수가 확실히 정해지므로 $K$는 1 줄고, $N$은 마지막 수만큼 줄어듭니다. 이를 식으로 나타내면 $f(N, K) = f(N - 0, K - 1) + f(N - 1, K - 1) + \cdots + f(N - N, K - 1)$...