시나위

Rust로 추리게임(guessing game)을 만들면서 대략적인 문법을 공부해보고 그나마 잘하는 파이썬과 비교하면서 뭐가 다른지 비교해본다. 빠르게 프로젝트를 생성하고 전체 코드를 비교해보자 // Cargo.toml [dependencies] rand = "0.8.5" // main.rs use std::{cmp::Ordering, io}; use rand::Rng; fn main() { println!("Guess the number!"); let secret_number = rand::thread_rng().gen_range(1..=100); loop { println!("Please input your guess."); let mut guess = String::new(); io::stdin() ..

https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 트리 문제이다. 트리를 만들고 순회하면 된다. 특정 노드의 부모가 가진 색깔과 노드가 원하는 색깔이 다른 경우 1 을 더한값을 계속 올려주면 된다. import sys; input = sys.stdin.readline sys.setrecursionlimit(10**9) def order(cur_node, cur_color, parent, adj_list, color): ret = 0 if..

https://www.acmicpc.net/problem/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net 트리 문제이다. 입력으로 주어지는 값은 양방향 그래프이고 인접리스트를 사용해서 노드끼리 연결 시킨다. 그리고 트리를 순회할때 parent 노드와 다른 번호의 노드만 순회를 하면 leaf 노드를 찾을수 있다. leaf node를 찾으면 1을 리턴해주고 이 값들을 모두 더해주면 leaf 노드의 개수를 찾을수 있다. import sys; input = sys.s..

https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 문자열 문제이고 정규표현식(regex, regular expression)으로 풀었다. 쉽게 풀줄 알았으나 match를 사용하면 패턴을 제대로 찾지 못하는 값들이 있었다. 예를 들면 '100111001' 이런 문자열이 들어왔을 때 '10011' '1001' 로 나눌수 있기 때문에 True 값이 나와야한다. 하지만 정규 표현식은 탐욕적으로 값을 구하기 때문에 '100+1+' 패턴중 가장 ..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net Union find 알고리즘을 사용하는 문제이다. 두 노드를 받아서 연결을 시키고, 친구가 될수 있는 최소 비용도 같이 갱신한다. 모든 노드를 받은 후 전체적으로 각 노드의 root값을 한번 더 갱신하고, 각 트리의 루트 비용를 더하면 된다. # import sys; input = sys.stdin.readline from collections imp..

https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net 문자열은 파이썬이 편하다. 마지막에 f가 있을거라 예상해서 f를 기준으로 단어를 나눴다(인덱스만 저장). 그리고 각각의 인덱스를 기준으로 4의 배수인지 확인하면 wwwoolllfff 같이 중간에 하나 빠져있는 단어들을 제거할수 있다. 그다음은 wlof 와 같은 단어를 제거한다. 나누어진 단어의 길이를 4로 나누면 한 단어당 나와야하는 알파벳의 갯수가 나온다. 이 개수로 wolf 각각 문자열을 곱하고 더해서 단어를 만들고 원래 기존의 단어와 비교하면 제거할수 있다. 여기까지..

https://www.acmicpc.net/problem/1942 1942번: 디지털시계 디지털시계는 일반적으로 시각을 “hh:mm:ss”의 형태로 표현한다. hh는 00 이상 23 이하의 값을, mm과 ss는 00 이상 59 이하의 값을 가질 수 있다. 이러한 형태의 시각에서 콜론(“:”)을 제거하면 “hhm www.acmicpc.net 손 풀려다가 방향을 잘못잡아 어렵게 푼 문제이다. 시간이 주어졌을때 각 구간에서 3의 배수인 시계 정수의 개수를 구하는 문제이다. 이걸 어떻게 풀지 고민하다가 DP 처럼 딕셔너리 자료형을 사용해서 모든값을 구하는 방향으로 했다. 반복문으로 00:00:00 부터 23:59:59 까지 다 구하면 될줄 알았으나 time_dict[num1-1]에서 key error가 떠서 마..

https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구슬탈출 2와 같은 문제이고 최소 거리일때의 경로까지 같이 출력해야한다. 구현한 알고리즘은 다음과 같다. 1) 입력을 받으면서 R, B, O의 위치를 저장한다. 2) BFS를 사용해서 시뮬레이션을 돌린다. 2-1) 먼저 움직이는 구슬을 찾는다. 2-2) 움직인다. 2-3) 파란 구슬이 빠진 경우 다음 방향을 탐색한다.(continue) 2-4) 빨..

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 특정 노드를 정점으로 하는 서브 트리의 정점의 개수를 구해야한다. 무방향 그래프를 받아서 연결시켜주고, 루트 노드에서 시작해서 후위 순회로 자식 노드의 개수를 더해주면 된다. 이때 visit 로 방문했는지도 체크하고 해당 노드에서 자식 노드의 개수를 저장한다. 순회가 끝나면 visit에 자식 노드의 개수가 저장되어있으므로 특정 노드를 ..

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net nCk = n! / {(n-k)! * k!} (mod bignum)이다 곱셉에선 모듈로 연산이 각각 들어가도 되었지만 나눗셈도 가능한지 몰랐다. 그래서 구글링을 했고 페르마의 소정리라는 것을 알게 되었다. 모듈로 연산에 쓰이는 값이 소수인경우 곱셉의 역원으로 b^-1 (mod pn) = b^(pn-2) (mod pn)가 된다. 1,000,000,007 이란 값은 소수이므로(이것도 구글링해봤다.) nCk 또한 페르마 소정..