https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 자동완성 기능이 있는 사전을 이용해 주어진 문자열들을 만들기 위해서는 몇 개의 알파벳을 입력하여야 하는가의 문제입니다. ex) hello, hell -> h 입력 시 hell 까지 자동 완성, hello, hell, he -> h 입력 시 he 까지 자동완성, l 입력 시 hell 까지 자동완성 트라이를 이용하여 다음과 같이 풀 수 있습니다. 1) 입력으로 주어진 문자열의 마지막에 . 을 추가한다. (..
https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net (회사에서 프로그래밍 시험을 보는데 C/C++, Java 만 있어서 C++로 다시 연습 중이다.) (처음에는 자식 노드한테 번호를 순차 부여해서 - ex. (1, 2), (1, 3), 연결 시, 1 -> "1", 2 -> "10" , 3 -> "11", (2, 4), (2,5) 연결 시, 4 -> "100", 5 -> "101", .... prefix 일치 여부로 풀려고 했으나 끝없는 메..
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. 모든 상..