PS/Problem Solving(124)
-
Codeup/코드업 3180 간단한 문제 풀기 위해 공부 했던 것들
코드업 3180 간단한 문제 첫째 줄에 수열의 길이 $N$이 주어진다. $(1 \le N \le 3*10^{5})$ 둘째 줄에 $A_{1}, A_{2}, ..., A_{N}$이 주어진다. $(-10^{9} \le A_{i} \le 10^{9})$ 셋째 줄에 질의의 개수 $M$이 주어진다, $(1 \le M \le 3*10^{5})$ 넷째 줄부터 쿼리가 한줄에 하나씩 주어진다. $(1 \le i \le j \le N, -10^{9} \le x \le 10^{9})$ codeup.kr https://codeforces.com/blog/entry/52477 qoo2p5 의 말이 핵심 How to find frequency of a given element in a range? - Codeforces codef..
2020.03.26 -
내가 보려고 만든 소인수분해 방법 정리글
https://booknu.github.io/2019/01/17/오일러의 체 오일러의 체 - 빠른 소인수분해, 소수 찾기 Content Similar Posts Comments booknu.github.io 이게 정말 효율적인 소수 판별법인데 주기적으로 복습하지 않으면 그 논리를 계속 까먹는다. 출처는 위 링크 코드 설명 spf[x] : x의 가장 작은 소인수 spf[x]==x 이면 x는 소수 pn: 지금까지 찾은 소수의 개수 pr[x] : x-1번째 소수 123456789101112131415#define FOR(i, f, n) for(int (i) = (f); (i) = pr[j]임을 확신할 수 있다. spf 를 이용하면 소인수 분해를 빠르게할 수 있다. 1234while(x!=1){ printf("..
2020.02.26 -
CodeUp에서 기억나는 문제
*코드업에서 실행시간/코드 길이(시간 같을 경우) 1등인 문제 목록 (2020년 4월 24일) 개인적으로 4533 보물섬 과 4714 키 순서 문제가 레전드. https://codeup.kr/problem.php?id=2102 배수 (Hard) $0$과 $1$로 이루어진 $N$의 배수 중 가장 작은 자연수를 출력한다. 이때 출력되는 자연수의 맨 앞자리는 $1$이어야 한다. 조건을 만족하는 자연수가 unsigned long long형의 범위에 없을 경우 $0$을 출력한다. codeup.kr https://codeup.kr/problem.php?id=2782 편의점 가는 길 1 $(1,1)$에서 $(w,h)$ 까지 도달하는 최단 경로의 수를 $1,000,000,000$으로 나눈 나머지를 출력하시오. code..
2020.02.20 -
강 건너기 문제
※이 글은 사람이 10명 이하일 때의 알고리즘입니다. Large 문제의 해법은 0000 원하는 상태 ==> 1111 이 된다. 탐색 알고리즘 n이 7 이하이기 때문에 사람들이 분포될 수 있는 경우의 수는 2^7 * 2(배의 위치) = 256 으로 매우 작다. 그렇기 때문에 브루트 포스 (DFS)로 충분히 해결될 수 있을 것이라 보았지만 웬걸, 83퍼에서 시간 초과가 걸리고 말았다. 다시 생각해보니 256개의 정점이 있는 것이더라.. 일반적인 DFS로 풀 경우 지수함수에 비례하는 시간이 걸리므로 시간 초과가 날 수 밖에 없다. 그럼 지금 구해야 하는 것은 가중치 그래프에서의 최단 거리이다. 그렇다면 역시 다익스트라 알고리즘을 사용하자. 아래 풀이를 이해하기 위해서는 다익스트라 알고리즘에 대한 기본적인 이해..
2020.02.02