1. 문제 다음과 같은 문제를 생각해보자. 크기가 1인 집합이 N개 있고 각 집합은 1부터 N까지 각각을 원소로 갖는 집합이다. {1}, {2}, {3}, ... , {N} 이 집합을 합치는 연산을 반복하여 최종적으로 {1,2,3,...,N}이 되게 하고 싶다. 생각할 수 있는 방법은 {1}을 {2}에 넣어서 {1,2}로 만들고, {1,2}를 {3}에 넣어서 {1,2,3}으로 만들고.. {1,2,3}을 {4}에 넣어서 {1,2,3,4},...를 반복하면 {1,2,3,4,..,N}이 된다. 결국 i번 집합을 i+1번 집합에 넣는 과정을 N-1번 반복하면 되는 것이다. ------------------------------------------------------------------------------..
1. 문제 C - Consecutive (atcoder.jp) C - Consecutive AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 매번 부분 문자열을 찾고, 거기서 연속해서 발생하는 문자의 수를 찾으면 당연히 시간초과가 날 것인데, 주어진 문자열에서 0번부터 어떤 위치 i까지 나타나는 연속해서 발생하는 문자의 개수를 누적합 배열로 미리 구해놓는다 예를 들어 mississippi라고 한다면, count = [0]*(n+1), before = ''으로 초기화해두고, i = 1부터 n까지 순회해서, s[i-..
1. 문제 E - Modulo MST (atcoder.jp) E - Modulo MST AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 단순하게 최소 스패닝 트리를 바로 찾으면, cost 자체는 최소일지 몰라도 그것을 modulo로 나눈 값이 최소라는 보장은 없다 다행히 정점 N
1. 문제 D - Square Permutation (atcoder.jp) D - Square Permutation AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 주어진 정수 문자열의 순열이 어떤 정수의 제곱수가 될때, 그러한 순열의 개수를 구하는 문제. 길이 제한이 13이라고 해도 모든 순열을 찾고, 각 순열이 어떤 수의 제곱수인지 검사하면 매우 느리다 1) 만약 길이 N인 s의 순열이 X의 제곱수가 될려면, X는 아무리 커봐야 $\sqrt{10^{N}}$이다. 그러므로 0부터 $\sqrt{10^{N}}$까..
1. 문제 E - Good Graph (atcoder.jp) E - Good Graph AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 그대로 구현하면 바로 시간초과 당하는데 조금만 생각하면 상당히 간단한 문제가 된다 N개의 정점을 가지고 M개의 간선을 가지는 그래프 G가 주어지는데 모든 i = 1,2,3..,k에 대하여 G에 존재하는 두 정점 $x_{i}, y_{i}$가 서로 연결되어 있지 않다면, G가 good 그래프이다. 이 때, Q개의 query가 주어지는데, 그래프 내의 두 정점 $p_{i}, q_{i..
1. 문제 C - AtCoder Cards C - AtCoder Cards AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 문제는 요약하자면 두 문자열이 주어지는데, @는 a,t,c,o,d,e,r중 하나로 바꿀 수 있다. 두 문자열을 적절하게 배열시켰을때, 서로 같게 만들 수 있느냐? 불가능하느냐? 딱 봤을때는 도저히 모르겠더라.. 최대 길이가 2*10^5인게 압박 브루트포스로 하면 당연히 시간초과일거고 근데 계속 보면서 생각해보니까 그리디적으로 사고했을때 두 문자열의 구성이 같으면 결국에 서로 같게 만들 수 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
