https://www.acmicpc.net/problem/3665 주어진 입력이 작년의 순위이고, 순위가 바뀐 팀들이 다음 입력으로 주어질 때, 올해의 최종 순위를 구하는 문제입니다. 알고리즘은 다음과 같습니다. 1. 등수가 n m 로 edge 있는 그래프 생성 (n=1, m=2 : n < m) 이 때 모든 등수에 대해 연결, 그리고 위상정렬에 사용할 진입 차수 계산 2. 새로 받은 입력으로 기존 edge를 제거하고, 새 edge를 연결, 그리고 진입 차수 새로 계산 3. 2번까지 진행 후 만든 그래프에서 사이클 발생 시, IMPOSSIBLE 4. 그렇지 않은 경우, 위상정렬으로 순차적으로 출력 1번에서 모든 n, m에 대해 edge를 만들었으므로, 사이클이 없는 그래프라면, ..
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() { ..