Go Gradually - Repository

[USACO Gold] Divisibility - PS(알고리즘)에서의 나눗셈

이와 같은 수학 문제는 코딩 테스트에는 잘 출제되지 않기 때문에 건너뛰는 사람들도 많지만,나는 시간복잡도 계산에 가장 강력한 인사이트를 부는 내용이 바로 이 수학 부분이라고 생각한다.그래서 이 수학 파트도 건너뛰지 않고 어느정도 설명을 진행하도록 하겠다.소인수분해 (Prime Factorization)양의 정수 a가 음이 아닌 정수 b의 약수(divisor) 또는 인수(factor)라고 불리는 것은, b가 a로 나누어떨어진다는 의미이다. 즉, 어떤 정수 k가 존재하여 b = ka가 되는 경우이다.정수 n > 1이 소수(prime)라는 것은 그 약수가 1과 n뿐일 때를 말한다.1보다 큰 정수 중 소수가 아닌 수는 합성수(composite)라고 한다. 모든 양의 정수는 유일한 소인수분해를 가진다. 즉, 소수..

k제일 큰 수에 1이 있으면?그냥 그거 쭉 늘리면 됨제일 큰 수에 1이 없으면?1이 붙은 수 중 가장 큰 수를 늘리거나큰수와의 차이만큼 낭비그 후 효율 떡상(1)중간값을 늘리거나효율 갈수록 안좋아짐이거 이분탐색 되려나?그래프가 ~자 모양이 됨효율 이김/안이김 이분탐색?몰빵보다 좋음/안좋음?이건 몰빵한테 따이는 시점 이분탐색인데중간값을 늘리는 시도를 점차 증가시켜본다?왜 그게 그렇게 되지?왜 최대 원소가 효율을 뽑기 시작하거나k 개 중 x개를 투자하면그 이후 k - x 개는 무조건 큰 수에 넣는게 제일 고효율이다문턱값을 넘으면 그 이후는 거기에 몰빵하는게 무조건 이득중간값을 올리는데 전부 몰빵하거나문턱값 안넘을거면 그냥 중간값 올리는데 몰빵이 나음그럼 중간값을 어떻게 올리지?순서가 동적으로 바뀌는데정해진 ..

트리 구조로 되어있는 숨겨진 그래프n-1 개의 간선을 찾아야 함15n 개의 쿼리를 통해n≤1000트리 구조의 특성상, 임의의 두 노드 사이의 경로는 유일하다한번에 하나씩 컴포넌트를 합쳐나가면?유니온 파인드 이용사이에 모르는 컴포넌트가 나오면?그냥 그거 찾지 뭐...?중요한건 임의의 두 컴포넌트를 "연결" 하고자 하는 것거리가 절반씩 줄어드니, logN서로 다른 두 컴포넌트 찾는 법유니온 파인드import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;//Change Class Name to ..

mex를 사용하여 입력받은 값을 최대로 만드는 문제mex는 두번 사용하면 최대로 커지므로, 이를 이용해 달성 가능한 가장 큰 값을 리스트를 순회하며 확인한다.만약 한번만 사용가능했다면 그래프 문제가 됐을 것 같다.맨날 전역에 동적 메모리 할당하고, 오랜만에 PS하느라 까먹었는데메모리 할당도 할당된 크기만큼 시간이 든다!시간복잡도 터지는것에 주의하자.import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.*;//Change Class Name to Proble..

k 번마다 전구가 on-off 됨시간 - 스타트시간/k 의 값이짝수이면 켜진 시점홀수이면 꺼진 시점무조건 모든 전구가 한번이라도 켜진 시점 이후 k시간 안에 전구가 켜져야됨이후는 반복되는 패턴(x - a_i) / k 의 패리티가 모두 짝수인 가장 작은 x최대와 최소 사이 공간이 존재하냐를 묻는 문제로 바뀜((x - a_i) / k) % 2 == 1x += k - (x - a_i) % k(x - a_i) / k % 2 == 0y = min(y, x + k - (x - a_i) % k)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import..