rust 연습 삼아 간단한 알고리즘 문제들을 하루 한 문제 정도 하기로 결정했습니다. 시간 날 때 rust로 사이드 프로젝트도 간단히 해볼 생각입니다. (아이디어 생각은 해놨지만 언제 할런지....) rust로 ps 자체에 대해 접근하기는 꽤 까다롭습니다. 입출력 속도 문제, 타입 문제 등이 있어 몇 개 풀어본 결과 괜찮은 방식은 use std::io::{stdin, Read}; use std::fmt::Write; fn main() { let mut input = String::new(); let mut output = String::new(); stdin().read\_to\_string(&mut input).unwrap(); let mut input = input.split\_ascii\_white..
https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 문제를 쭉 읽고 내용을 정리하면 다음과 같습니다. 1. 상어는 숫자 작은 애가 큰 애 이긴다. 2. 상어는 우선순위에 따라 빈칸으로 이동한다. 빈칸이 없으면 자신의 냄새가 있는 칸으로 우선순위에 따라 이동한다. 3. 상어는 이동한 칸에 k만큼의 냄새를 남긴다. 4. 같은 칸에 상어가 여러 마리 이동하게 되는 경우, 숫자 큰 애는 쫓겨난다. 5. 모든 상..
https://www.acmicpc.net/problem/22289 22289번: 큰 수 곱셈 (3) 첫째 줄에 정수 A와 B가 주어진다. 두 정수는 0보다 크거나 같은 정수이며, 0을 제외한 정수는 0으로 시작하지 않으며, 수의 앞에 불필요한 0이 있는 경우도 없다. 또한, 수의 길이는 1,000,000자리를 www.acmicpc.net 예전에 틀렸었다가 새로 푼 문제입니다. 틀렸던 걸 보니 FFT 코드 짠 걸로 돌렸다가 시간초과가 떴었는데 FFT를 구성하는 polynomial을 10 기준으로 poly를 만들지 않고 100 기준으로 poly를 만드니 해결되었습니다. (1000, 10000 기준으로도 해봤는데 시간초과....) 코드는 다음과 같습니다. #include #include #include #i..
https://www.acmicpc.net/problem/11025 11025번: 요세푸스 문제 3 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000) www.acmicpc.net 요세푸스 문제는 큐를 이용하여 풀어도 되고, dp를 이용해도 되고, 재귀식을 이용해 풀어도 됩니다. 하지만 현재 문제의 메모리가 매우 제한적이므로, 큐나 dp 등 큰 메모리를 사용하는 것을 사용할 수는 없고, 재귀를 이용하여도, 스택에 function call 메모리가 계속 쌓이므로 사용이 안 됩니다. 따라서 기존 요세푸스 문제 점화식을 loop로 풀어서 적용하면 됩니다. 코드는 다음과 같습니다. #include using namespace std; int main() { ..
https://www.acmicpc.net/problem/13926 13926번: gcd(n, k) = 1 자연수 n이 주어졌을 때, gcd(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 주어진 정수 n에 대해서 오일러 피 함수 값을 구하는 문제입니다. ( __int128 을 안 써서 시간초과가 뜬 거라고는 예상하지 못했다..... ) n의 최대 입력이 10^18 이므로 약 2^60 정도됩니다. 따라서 곱셈 연산 등에서는 __int128 타입으로 계산을 진행해야 합니다. 로직은 다음과 같습니다. 1. n에 대해 폴라드 로 알고리즘으로 소인수를 구한다. 2. 해당 소인수가 prime인지 여부를 밀러 라빈 소수 판정법으로 계산한다...