분류 전체보기 (21) 썸네일형 리스트형 [Rust] 파일 분할, mod, use, lib.rs 모든 프로그램이 그렇듯이 프로그램이 커지면 하나의 파일로 관리하기가 불가능해집니다. 따라서 파일을 분리하고 서로 연결하는 과정이 필요합니다. cargo로 새 프로젝트를 구성합니다. cargo new greeting cd greeting 예로 인사 프로그램을 만들어 봅시다. // main.rs fn hello_ko() { println!("안녕하세요!"); } fn hello_en() { println!("Hello!"); } fn main() { hello_ko(); hello_en(); } 1. mod는 코드를 구역으로 나눕니다. // main.rs mod korean { pub fn hello_ko() { println!("안녕하세요!"); } } mod english { pub fn hello_en.. [알고리즘 문제] 백준 1443번 망가진 계산기 1443번: 망가진 계산기 (acmicpc.net) 1443번: 망가진 계산기 첫째 줄에 다솜이의 계산기가 표시할 수 있는 자리수 D와 다솜이가 하려고하는 연산의 수 P가 주어진다. D는 2보다 크거나 같고, 8보다 작거나 같은 자연수이고, P는 30보다 작거나 같은 음이아닌 www.acmicpc.net 문제 1에 2에서 9 사이의 숫자를 정해진 횟수만큼 곱해 만들 수 있는 최대의 D자리 수를 만드는 문제 아이디어 D가 최대 8자리이기 때문에 모든 경우를 구한다 해도 많은 시간이 걸리지 않습니다. 1. 백트래킹을 통해 첫 번째부터 P번째 곱할 수를 모두 탐색합니다. 2. 탐색 중 숫자가 D자리를 넘기면 해당 가지를 쳐냅니다. 3. P번째 숫자까지 도달하면, 곱한 값을 기존 답과 비교해 더 큰 수를 골라냅.. [알고리즘] 백 트래킹 백트래킹이란 조건을 만족하는 경우를 탐색하는 방법입니다. 백 트래킹이라는 단어처럼 탐색하는 과정이 길을 찾고 되돌아가는 것과 비슷합니다. 한 번 예시를 들어봅시다. 1, 2, 3으로 만들 수 있는 세 자리 숫자를 모두 출력해야 합니다. 첫째 자리 - 둘째 자리 - 셋째 자리를 순서대로 결정한다고 가정하면, 경우를 트리로 표현할 수 있습니다. 각 자리를 1, 2, 3 순서로 선택하며 내려간다고 하면, 가장 처음 도착하는 숫자는 1-1-1입니다. 1-1-1로 트리의 끝에 도착했다면, 다시 1-1로 돌아가고(백 트래킹 하고) 이번에는 2를 선택합니다. 반복하면 모든 경우를 찾을 수 있습니다. 백 트래킹의 장점은 1. 가능한 경우를 탐색하면서도 가지치기로 경우의 수를 줄이기에 용이합니다. 만약 현재 단계에서 조.. [알고리즘 문제] 백준 8905번 리트 8905번: 리트 (acmicpc.net) 8905번: 리트 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 한 알파벳을 리트로 바꿨을 때 리트의 최대 길이 k가 주어진다. (1 ≤ k ≤ 3) 둘째 줄에는 www.acmicpc.net 문제 원래 단어와 목표 단어가 주어졌을 때, 단어의 글자를 치환해 다른 단어로 바꿀 수 있는지를 묻는 문제입니다. 예를 들어 ppap를 |>|>0|>로 바꾸려면 p를 |>로, a를 0으로 치환할 수 있습니다. 만약 baa를 |>0>로 바꾼 다면, a에 매칭되는 문자를 찾을 수 없어 불가능합니다. 아이디어 문자열의 길이는 최대 15, 한 알파벳과 대응되는 문자열은 최대 3 길이를 가지니, 모든 경우를 구해 해결할 수 .. [Rust] 숫자를 입력 받기 let mut str = String::new(); std::io::stdin().read_line(&mut str).expect("failed to read from stdin"); let v = str .split_whitespace() .map(|str| str.parse::().unwrap()) .collect::(); Rust는 C++의 cin처럼 자동으로 숫자 입력을 받아주지 않기에 직접 변환을 해야 합니다. 위 코드는 "1 2 3" 입력을 [1, 2, 3] 벡터로 변환합니다. std::io::stdin().read_line(&mut str) pub fn read_line(&self, buf: &mut String) -> io::Result { self.lock().read_line(buf) .. [알고리즘 문제] 백준 1707번 이분 그래프 1707번: 이분 그래프 (acmicpc.net) 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 주어진 그래프에서 정점을 두 집합으로 분리하되, 두 집합 사이에 인접한 점이 없도록 하는 문제입니다. 아이디어 두 집합 사이에 인접한 점이 없다는 말은, 인접한 두 점은 다른 집합이라는 뜻입니다. 이를 통해 각 정점의 집합을 골라가며 그래프를 탐색하면 해결할 수 있습니다. 여기서는 BFS를 사용해보겠습니다. 1. 시작점을 임의의 집합으로 정하고 탐색을 시작합니다. 2. 자신과 인접한 점은 다른 집합으로 표시.. [알고리즘 문제] 백준 16953번 A → B 16953번: A → B (acmicpc.net) 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 주어진 숫자 A에서 다음의 연산을 몇 번 거쳐야 B에 도달하는지 구하는 문제입니다. 1. 2를 곱한다. 2. 1을 수의 가장 오른쪽에 추가한다. (n * 10 + 1) 아이디어 연산에 규칙성이 보이지 않으니 모든 경우를 해보는 수밖에 없습니다. 그래프를 탐색하듯 1번과 2번 규칙을 각각 적용해보며 진행해 봅시다. 1. 숫자 A에서 시작합니다. 2. A에 1번 규칙을 적용시킨 경우와 2번 규칙을 적용시킨 경우를 나누어 연산 수를 재귀적으로 구합니다. 3. A는 둘 중 더 적은 수의 규칙 + 1을 통해 도달 가능합니다. 둘 모두 도달할 .. [알고리즘 문제] 백준 11660번 구간 합 구하기 5 11660번: 구간 합 구하기 5 (acmicpc.net) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 2차원 배열에서 지정한 사각형 구역 내의 합을 구하는 문제입니다. 아이디어 구간합 방법의 2차원 예입니다. 1차원 배열에서의 구간 합의 경우, 0부터 i까지의 합을 캐시하면, 구간 합은 O(1) 시간에 구할 수 있습니다. 2차원의 경우도, 같은 아이디어를 적용해 O(1) 시간에 구간합을 구할 수 있습니다. 단, 2차원이 되면서 영역을 빼고 더하는 부분이 생긴.. [알고리즘 문제] 백준 9019번 DSLR 9019번: DSLR (acmicpc.net) 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 한 수에서 여러 명령을 수행해 다른 값으로 만드는 문제다. 아이디어 만약 문제를 보고 수학 계산으로 해결할 수 있을 거라 생각했다면 함정에 빠진 것이다. 숫자 사이를 공식으로 구할 방법은 없으며, 각 숫자를 그래프의 노드로 보고 DSLR 명령을 노드 사이의 간선으로 생각한다면 BFS를 통해 둘 사이의 거리를 구할 수 있다. 1. 초기 값에서 시작하는 BFS 큐를 만든다. 2. 현재 위치에서 D, S.. [알고리즘 문제] 백준 7569번 토마토 7569번: 토마토 (acmicpc.net) 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 3차원 배열 그래프 상에서 토마토가 익는 시간을 측정하는 문제입니다. 아이디어 BFS를 사용하는 몇 가지 방법이 있겠지만, 여기서는 가장 단순한 방법을 사용합니다. 시간을 들여 직접 토마토를 익혀봅시다. 1. 처음 익은 토마토의 리스트를 만듭니다. 정확히는 다음 시간에 주변에 영향을 줄 토마토들입니다. 2. 익은 토마토의 주변에 안 익은 토마토, 즉 다음에 익을 토마토를 익히고 리스트로 만.. 이전 1 2 3 다음
