반짝반짝 도화지

https://www.acmicpc.net/problem/17397 17397번: FLEX 인호는 3일동안 각각 3, 2, 1만 원을 지출할 예정이고, 추가로 사용 가능한 잔액 1만 원이 남아있다. 원래는 총 2만큼의 박탈감을 느껴야 하지만 마지막 날에 1만 원을 추가한다면, [3, 2, 2]가 되�� www.acmicpc.net 문제를 딱 보고 그리디적인 생각이 떠올랐다. 특히 score가 제곱에 비례하므로, 전 날과의 지출 차이가 큰 날일수록 여윳돈을 투자했을 때의 이득이 높아지게 된다. 그런데 생각해보니 뭔가 애매한 감이 있었고, 입력 크기를 보니 동적계획법으로 풀 수 있는 문제였다. O(NMC^2) 그렇게 AC를 받은 후, 다시 그리디 풀이를 열심히 생각해봤다. 무조건 전 날과의 차이만 보고 여윳..

이번 학기에 듣는 수업 중 Rust라는 언어를 사용하는 프로젝트 과목이 있다. Rust 공식 사이트에서 제공하는 학습용 온라인 책 "The Rust Programming Language"를 통해 Rust를 공부하고, 기억해야 할 내용을 정리하려고 한다. "The Rust Programming Language": https://doc.rust-lang.org/book/title-page.html The Rust Programming Language - The Rust Programming Language by Steve Klabnik and Carol Nichols, with contributions from the Rust Community This version of the text assumes yo..

0. 요약 트리에서 서브트리에 대한 쿼리, 경로에 대한 쿼리가 주어질 때, 이를 배열의 구간에서 특정 횟수만큼 등장하는 원소에 대한 쿼리로 변형할 수 있다. => Mo's Algorithm 적용 가능한 꼴! 1. 트리 펼치기 트리를 펼치는 것은 보통 트리를 노드 번호의 수열로 나타내는 것을 뜻하며, 그 목적에 따라 다양한 방법이 존재한다. 이 글에서는 트리에서 Euler tour를 돌면서(dfs를 수행하면서) 각 정점을 처음 방문했을 때 / 마지막으로 방문했을 때 배열에 기록하는 방법을 이용하고자 한다. 예를 들어 위와 같은 트리에서 1번을 root로 하여 dfs를 수행하되 번호가 작은 정점을 먼저 방문한다고 하자. 단순히 정점을 방문하는 순서는 1, 2, 3, 4, 5, 6, 7, 8, 9지만, 각 정..

KMP 알고리즘은 문자열 S에서 패턴 P를 선형 시간에 찾는 알고리즘이다. S와 P의 길이를 각각 n, m이라고 하자. 가장 간단하게 S의 모든 지점에서 시작해보면서 P와 비교하는 방법은 O(NM)의 시간복잡도를 가진다. 이 때 어디에서 시작해서 어디까지 일치했는지에 대한 정보를 토대로 다음에 시작할 위치를 효과적으로 소거할 수 있으며, 이것이 KMP 알고리즘의 핵심 아이디어이다. 1. KMP 알고리즘 위 그림은 P의 처음 다섯 문자가 일치했으며, 여섯 번째 문자에서 불일치가 발생한 경우를 나타내고 있다. O(NM)의 방법에서는 이 경우 P를 오른쪽으로 한 칸 움직인 후 첫 문자부터 다시 비교를 시작한다. 하지만 일치했던 문자열 "abcab"의 접두사이면서 접미사인 최대 길이 문자열이 "ab"라는 점을 ..