Wiki Index

Solution rust soulution Memo 그리디는 매번 반복하지만, 그리디로 풀린다는 감각을 갖는게 어렵고 헷갈리는 것 같다. 대신 확실해지면 구현은 쉽다. 종료시간, 시작시간 순으로 스케줄을 정렬하고 종료시간이 가장 빠른 순으로 마지막 원소와 valid하여 결과에 추가, 마지막으로 결과 배열을 반환한다. // Baekjoon - 1931 // https://www.acmicpc.net/problem/1931 use std::io::{self, Read, Write}; fn main() { let mut stdin = io::stdin().lock(); let mut stdout = io::stdout().lock(); let mut input = String::new(); stdin.read_to_string(&mut input).unwrap(); let mut lines = input....

Solution rust soulution Memo 뭔가 갑자기 그래프 dfs문제가 나오길래 다른 좋은 방법이 있나 하고 찾아봄 나는 dfs를 풀었다. 아마 백트래킹때문에 완탐으로 분류된듯? // Baekjoon - 1987 // https://www.acmicpc.net/problem/1987 use std::io::{self, Read, Write}; const DY: [i32; 4] = [-1, 0, 1, 0]; const DX: [i32; 4] = [0, 1, 0, -1]; fn main() { let mut stdin = io::stdin().lock(); let mut stdout = io::stdout().lock(); let mut input = String::new(); stdin.read_to_string(&mut input).unwrap(); let mut lines = input....

Solution rust soulution Memo 점화식을 세우는 전형적인 dp 문제 n이 홀수면 채울 수 없으므로 바로 0 출력 n = 2일 때 기본 케이스는 3가지 n = 4일 때는 기본 케이스 3 * dp[2] + 특이 케이스(2) 1개 → 총 11개 점화식은 dp[n] = dp[n - 2] * 3 + (dp[n - 4] + dp[n - 6] + … + dp[0]) * 2 와 같음 특이 케이스는 n이 4 이상일 때부터 등장하며, 매번 2씩 곱해진다 dp[0] = 1을 기준으로 초기값 설정하는 것이 핵심 (dp[0]은 안씀) 반복문은 짝수 단위로만 진행되어야 하므로 step_by(2) 사용해야 한다 // Baekjoon - 2133 // https://www....

Solution rust soulution Memo Rust는 브루트포스(백트래킹)로도 종종 통과되길래 처음에는 그렇게 접근했지만, 이 문제에서는 시간 초과가 발생함. (주석 처리한 부분이 그 코드) 이 문제는 전형적인 0-1 Knapsack 문제다. 핵심 아이디어: 모든 비용(코스트)에 대해 만들 수 있는 최대 메모리 바이트를 dp로 구함 이 dp 배열에서 target_bytes 이상을 만족하는 최소 비용을 찾아냄 dp[i]는 비용이 i일 때 확보 가능한 최대 메모리를 의미함 최종적으로 dp 배열을 순회하면서 target_bytes 이상 확보되는 지점 중 가장 작은 비용(cost)을 answer로 출력 // Baekjoon - 7579 // https://www....

Solution rust soulution Memo 전형적인 dp fibo 문제 사실 이런건 dp로의 의의보다는 그냥 문제의 요구사항을 수학적으로 피보나치를 요구하는게 맞는지 확인하면 끝인것같다. // Baekjoon - 11726 // https://www.acmicpc.net/problem/11726 use std::io::{self, Read, Write}; fn main() { let mut stdin = io::stdin().lock(); let mut stdout = io::stdout().lock(); let mut input = String::new(); stdin.read_to_string(&mut input).unwrap(); let mut lines = input.lines(); let n: usize = lines.next().unwrap().parse().unwrap(); if n == 1 { writeln!(stdout, "1").unwrap(); return; } let mut dp = vec!...

Solution rust soulution Memo dp문제 생각이 꼬이면 빅트롤을 한다. 주석의 풀이가 틀렸지만 이상한짓을 한 코드 기본적으로 수열, dp, psum을 생각하며 조급하게 굴다가 의미없는짓을 세번이나 했다. 복기하면 psum을 구할 필요가 없었다. 구간합중 가장 큰 수열값으로 브루트포스 풀이를 했다. 직전 구간합과 지금 구하고자 하는 값과의 연관관계에 집중을 전혀 하지 못했다. // Baekjoon - 1912 // https://www.acmicpc.net/problem/1912 use std::cmp::max; use std::io::{self, Read, Write}; fn main() { let mut stdin = io::stdin().lock(); let mut stdout = io::stdout()....

Solution rust soulution Memo 부르트 포스 문제 구현이 귀찮지만 입력이 제한되어있다. 브루트포스 말고 다른 방법이 안떠오르면 바로 진행하면 됨 // Baekjoon - 3085 // https://www.acmicpc.net/problem/3085 use std::cmp::max; use std::io::{self, Read, Write}; fn main() { let mut stdin = io::stdin().lock(); let mut stdout = io::stdout().lock(); let mut input = String::new(); stdin.read_to_string(&mut input).unwrap(); let mut lines = input.lines(); let n: usize = lines.next().unwrap().parse().unwrap(); let mut board: Vec<Vec<char>> = vec![]; for _i in 0....

파이썬 PS 1단계: 기초 문법 완전정복 📥 1. 입출력 처리 기본 입력 # 한 줄 입력 n = int(input()) s = input() a, b = map(int, input().split()) # 여러 줄 입력 arr = [] for _ in range(n): arr.append(int(input())) # 리스트 한번에 입력 numbers = list(map(int, input().split())) 빠른 입력 (sys.stdin) import sys input = sys.stdin.readline # 주의: readline()은 개행문자를 포함하므로 n = int(input()) # 숫자는 자동으로 개행문자 제거 s = input()....

Rust Iterator 인터페이스 종합 1. 핵심 트레이트 Iterator 트레이트 pub trait Iterator { type Item; fn next(&mut self) -> Option<Self::Item>; // ... 여러 기본 구현 메서드들 } IntoIterator 트레이트 pub trait IntoIterator { type Item; type IntoIter: Iterator<Item = Self::Item>; fn into_iter(self) -> Self::IntoIter; } FromIterator 트레이트 pub trait FromIterator<A> { fn from_iter<T>(iter: T) -> Self where T: IntoIterator<Item = A>; } 2. 반복자 생성 메서드 기본 컬렉션 반복자 iter(): 불변 참조 반복자 (&T) iter_mut(): 가변 참조 반복자 (&mut T) into_iter(): 소유권 이전 반복자 (T) 범위 반복자 // 범위 문법으로 반복자 생성 let range = 1....

Solution rust soulution Memo 문제 자체는 브루트포스의 느낌이 났고 구현만 신경쓰면 될 것 같았다. O((N-7) * (M-7) * 128), n,m 상한이 50이다 // Baekjoon - 1018 // https://www.acmicpc.net/problem/1018 use std::{ cmp::min, io::{self, Read, Write}, }; fn main() { let mut stdin = io::stdin().lock(); let mut stdout = io::stdout().lock(); let mut input = String::new(); stdin.read_to_string(&mut input).unwrap(); let mut lines = input.lines(); let mut iter = lines.next().unwrap().split_whitespace(); let m: usize = iter.next().unwrap().parse().unwrap(); let n: usize = iter....