본문 바로가기 메뉴 바로가기

ACM-ICPC 상 탈 사람

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

ACM-ICPC 상 탈 사람

검색하기 폼
  • 분류 전체보기 (360)
    • 서버 관련 (9)
      • JS (5)
      • AmazonWebService (1)
      • Backend 지식 (3)
    • 일상 (13)
      • Daliy (1)
      • 잡담 (10)
      • 개인 (2)
    • 알고리즘 관련 (337)
      • BOJ (303)
      • UVaOJ (8)
      • SPOJ (1)
      • 알고리즘&이론 (25)
  • 방명록

에라토스테네스의 체 (6)
BOJ)13212 Random

문제: icpc.me/13212 1)주어지는 수의 1을 제외한 소인수가 모두 K보다 크면서 2)연속되는 같은 숫자가 4개 이상이 아닌지 확인하는 문제이다. 2)의 조건은 10으로 나눠주면서 연속되는 자리수의 개수를 세주면 되고 1)의 조건은 sqrt(maxNumber)보다 작은 모든 소수를 구해준 뒤 그 수들로 나눠지는 가장 작은 수가 K보다 큰지 여부를 확인해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include using namespace std;typedef long long ll;ll n, k, num;bool p[100010];vecto..

알고리즘 관련/BOJ 2017. 10. 16. 15:53
BOJ)1837 암호제작

문제: icpc.me/1837 P가 너무 크기 때문에 K를 이용하여 답을 구해내야 한다. 우선 K이하의 소수를 에라토스테네스의 체를 이용하여 구해준 뒤 P가 해당 소수들 중 하나라도 나누어 떨어지는 수가 있다면 BAD를 출력하게 된다. 12345678910111213141516171819202122232425262728293031#include #include using namespace std;char a[110];int k, p[2000000];bool chk(const char *s, int p) { int ret = 0; for (int i = 0; s[i]; i++) ret = (ret * 10 + s[i] - '0') % p; return !ret ? true : false;}int main(..

알고리즘 관련/BOJ 2017. 6. 5. 00:46
BOJ)1747 소수&팰린드롬

문제:icpc.me/1747 N보다 큰 수 중에서 소수이면서 팰린드롬인 가장 작은 수를 구하는 문제이다. 에라토스테네스의 체를 이용하여 소수들을 구해놓은 뒤 N보다 큰 수 중에서 팰린드롬인지 검사해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include using namespace std;bool p[2000001];int n;bool ck(int *a, int lo, int hi) { if (lo >= hi)return 1; if (a[lo] != a[hi])return 0; return ck(a, lo + 1, hi - 1);}bool chk(int x) { int c = -1; int a[8]; wh..

알고리즘 관련/BOJ 2017. 3. 23. 16:31
BOJ)1017 소수 쌍

문제: icpc.me/1017 N개의 수가 주어질 때 주어진 모든 수를 짝을 지을 때 모든 각각의 짝의 합이 소수가 되도록 할 때 첫 번째 수와 매칭 될 수 있는 모든 수를 구하는 문제이다. 어떤 수 a와 b가 서로 다를 경우 a+b가 소수가 되기 위해서는 a와 b가 짝수와 홀수로 나누어져야한다. 즉 우리는 짝수와 홀수로 이분 그래프 형태로 그래프를 모델링 해준 후 이분 매칭을 구해주어 n/2만큼 매칭 될 경우 1번 정점과 매칭 된 정점을 역추적 해주어 답에 넣어준 후 그 간선만 제거하고 다시 이분매칭을 실행함을 반복해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535..

알고리즘 관련/BOJ 2017. 2. 20. 16:24
BOJ)14431 소수마을

문제: icpc.me/14431 마을의 좌표가 주어질 때 두 좌표사이의 거리의 정수부분이 소수일 경우에만 이동가능한다는 조건하에 소수마을에서 A마을로 이동하는데 걸리는 최단경로를 구하는 문제이다. 에라토스테네스의 체를 이용하여 소수들을 구해준 후 거리가 소수인 정점들을 서로 간선 연결을 해준 뒤 다익스트라를 돌려서 해결하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include #include #include #include using namespace std;int getdist(pair a, pair b) { return sqrt((a.fir..

알고리즘 관련/BOJ 2017. 2. 6. 02:22
BOJ)4948 베르트랑 공준

문제: icpc.me/4948 n~2n 사이의 소수의 개수를 출력하면 되는 문제이다. 에라토스테네스의 체로 소수들을 구해 준 뒤 파셜섬의 차를 구해주면 된다. 12345678910111213141516171819202122232425#include #include using namespace std;bool p[270000];int s[270000];int n;int main() { p[0] = p[1] = true; for (int i = 2; i

알고리즘 관련/BOJ 2017. 1. 6. 13:53
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Node.js로 DynamoDB 시작⋯
  • Node.js로 DynamoDB 시작⋯
  • Express와 Apollo server⋯
  • GraphQL 스키마 작성하기⋯
최근에 달린 댓글
  • 도움이 많이 되었습니다 굳굳⋯
  • 간선의 방향을 다 거꾸로 받⋯
  • 넵 요즘은 거의 node js 만⋯
  • 문제 설명 감샇바니다. :) 'B⋯
Total
315,368
Today
35
Yesterday
199
링크
  • 민호형
  • 제주시민
  • 꼴뚜기
  • 김흿
  • 태양쓰
  • 정률이
  • 정이 형
  • stack님
  • 세지니
  • 매브레이커
  • 박트리님
  • 플즈런님
  • 맹킹
  • 송이 블로그
TAG
  • MCMF
  • 트리
  • 이분 매칭
  • MST
  • dfs
  • 그리디 알고리즘
  • 수학
  • disjoint-set
  • BFS
  • 다이나믹 프로그래밍
  • KMP
  • 힙
  • 디닉
  • 좌표 압축
  • SCC
  • 이분 탐색
  • LCP array
  • 네트워크 플로우
  • 위상 정렬
  • 세그먼트 트리
  • lazy propagation
  • 다익스트라
  • partial sum
  • lca
  • 분할 정복
  • 플로이드 워셜
  • 라인 스위핑
  • 에라토스테네스의 체
  • Suffix Array
  • brute force
more
«   2021/03   »
일 월 화 수 목 금 토
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
글 보관함
  • 2020/05 (2)
  • 2020/04 (6)
  • 2020/03 (1)
  • 2018/07 (4)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바