본문 바로가기

전체 글

 (22)
[알고리즘] 백 트래킹 백트래킹이란 조건을 만족하는 경우를 탐색하는 방법입니다. 백 트래킹이라는 단어처럼 탐색하는 과정이 길을 찾고 되돌아가는 것과 비슷합니다. 한 번 예시를 들어봅시다. 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) ..

티스토리툴바