본문 바로가기

분류 전체보기

제이크 USB 11번가 이벤트로 100원에 구매하였다.귀엽다. 더보기
BOJ)2023 신기한 소수 문제: icpc.me/2023 N자리의 신기한 소수를 모두 출력하는 문제이다. 문제를 잘 생각해보면 N자리의 신기한 소수는 결국 N-1자리의 신기한 소수로부터 파생된다는 걸 알 수 있다. 게다가 예제를 보면 그 수가 얼마 안되기 때문에 N-1자리의 신기한 소수들에서 파생되는 수들에 대해서만 sqrt(Number)시간에 소수여부 검사를 해주면 빠르게 구해줄 수 있다. 123456789101112131415161718192021222324252627282930#include #include #include using namespace std;vector v[10];bool isp(int x) { for (int i = 2; i 더보기
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)13213 Binary Roads 문제: icpc.me/13213 N개의 정점과 E개의 간선으로 이루어진 그래프에서 0번정점에서 N-1번 정점으로의 최단거리를 구하는 문제이다. 단, 조건이 하나있는데 엣지에 패리티가 붙어있어서 0이나 1중 하나의 속성을 지닌다. 이전에 0인 엣지를 통하여 왔다면 다음에는 1인 엣지만 밟을 수 있다. 이 문제를 해결하기 위하여 각 정점을 2차원으로 생각해주면 된다. 0인 엣지를 밟고 V번 정점인 경우와 1인 엣지를 밟고 V번 정점인 경우로 나눠서 생각해주면 다익스트라를 2번 실행하는 것으로 문제를 해결해 줄 수 있다. N제한이 크긴 하지만 시간이 3초이니 제한시간 내에는 넉넉히 들어올 수 있다. 12345678910111213141516171819202122232425262728293031323334353.. 더보기
BOJ)11442 홀수번째 피보나치 수의 합 문제: icpc.me/11442 N보다 작은 모든 홀수번째 피보나치 수의 합을 구하는 문제이다. N이 너무 크기 때문에 피보나치 수의 N번째 항은 행렬 곱셈의 분할 정복으로 log 시간에 구할 수 있지만 이방법으로 모든 피보나치수를 구하는건 너무 많은 시간이 걸린다. 하지만 수를 쭉 나열해보면 Rn이 n보다 작은 모든 홀수번째 피보나치 수의 합이라고 가정한다면 R(2n)=R(2n-1)=F(2n) 이라는 공식이 나온다. 따라서 이에 대한 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include #include using namespace std;typedef long long ll;.. 더보기
BOJ)11443 짝수번째 피보나치 수의 합 문제: icpc.me/11443 N보다 작은 모든 짝수번째 피보나치 수의 합을 구하는 문제이다. N이 너무 크기 때문에 피보나치 수의 N번째 항은 행렬 곱셈의 분할 정복으로 log 시간에 구할 수 있지만 이 방법으로 모든 피보나치 수를 구하는건 너무 많은 시간이 걸린다. 하지만 수를 쭉 나열해보면 Rn 이 n보다 작은 모든 짝수번째 피보나치 수의 합이라고 가정한다면 R(2n)=R(2n+1)=F(2n+1)-1 이라는 공식이 나온다. 따라서 이에 대한 답을 구해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include using namespace std;typedef long long l.. 더보기
BOJ)5883 아이폰 9S 문제: icpc.me/5883 N개의 수로 이루어진 수열이 주어질 때 , 어떤 한가지 수를 정해서 전부 지워버린 뒤, 수열에 남은 수 중 연속 된 수의 길이가 가장 긴것을 출력하는 문제이다. 처음에 N 제한을 100만으로 봐서 생각을 좀 했지만 다시 보니 N제한이 1000이라서 N^2 으로 풀 수 있었다. set을 이용하여 모든 수를 저장해논 뒤에 하나씩 직접 지워본 뒤 수를 세주면 된다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include using namespace std;int n, x, res;int main() { scanf("%d", &n); vector vt; set st.. 더보기
CCW와 CCW를 이용한 선분 교차 판별 PS에서 종종 이용되는 선분 교차 여부 판별을 CCW를 이용하여 비교적 간단(?)하게 할 수 있는 방법을 소개하려고 합니다. 그 전에 우선 CCW에 대하여 이야기 해보겠습니다. CCW는 Counterclockwise의 약자로 풀어 해석하면 그냥 반시계 방향입니다. PS에서의 CCW는 세 점에 대한 방향성을 나타냅니다. CCW의 return 값은 보통 세가지 경우입니다. 1. 반시계 방향인 경우 2. 시계 방향인 경우 3.세 점이 평행한 경우 이렇게 세가지 경우로 분류되며 CCW는 삼각형의 면적을 구하는 공식+벡터를 이용하여 구해지게 됩니다. 해당 식에서 S가 0보다 크면 반시계 방향 S가 0보다 작으면 시계 방향 S가 0이면 세 점이 평행합니다. 이를 소스코드로 작성하면 아래와 같습니다. 1234567i.. 더보기
2017 ACM-ICPC Daejeon Regional 인터넷 예선 후기 2016년 3월 PS라는걸 처음 알게 되고 ,2016년 8월 처음으로 이걸 제대로 공부해 봐야겠다는 생각이 들었고, 2016년 12월 블로그 이름을 ACM-ICPC 상 탈 사람이라고 달아버리고, 마침내 어제 목표로 하던 ACM-ICPC 대전 리저널 본선으로 가는 티켓을 따기 위한 인터넷 예선을 치루게 되었다. SCPC, 카카오 코드 페스티벌 등.. 이제 대회 경험이 꽤 생겼지만 이렇게 가슴이 떨린적은 처음인것 같다. 처음부터 이 대회를 목표로 공부를 시작하였으니 그런듯 하다 .. 2시에 대회가 시작된 뒤 등록 문제가 바뀐 걸 인지 못해서 엉뚱한 답안을 작성할 뻔 했지만 팀원들이 잘 지적해주어서 제대로 고쳐서 냈다. 초반 스퍼트는 굉장히 좋았다.. 아니 솔찍히 기대 이상이였다. 우리가 4문제를 풀어낸 시간.. 더보기
좌표압축 기법 좌표압축 기법은 Problem Solving을 하다보면 정말 정말 정말 자주 쓰이는 테크닉이다. 세그트리(or BIT) 등등.. 구간 쿼리와 함께 같이 쓰이는 경우도 많고, 오프라인 쿼리등을 처리할 때 등등 많은 경우에서 유용하게 이용된다. 개념에 대한 설명을 하기 위하여 한 문제를 예시로 들어보겠다. N( 더보기