분류 전체보기 썸네일형 리스트형 BOJ)5846 Tractor 문제: icpc.me/5846 n^2의 격자에서 한 점에서 4방향으로 일정 조건(둘의 차이가 k이하이면 이동 가능)을 만족하면 이동가능할 때임의의 한점을 잡아 반 이상의 격자를 순회할 수 있는 최소의 k를 찾는 문제이다. 최대중의 최소를 구하는 문제이므로 파라메트릭 서치를 생각해볼 수 있다.이 때 k를 mid값으로 정해놓은 뒤에 만족 여부를 확인하게 되는데만족여부는 dfs를 통하여 확인할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace std;int n, a[555][555], b[555][555];int dx[] = .. 더보기 BOJ)5849 Cow Crossings 문제: icpc.me/5849N개의 2점이 주어진다.a[i]와 b[i]인데 이 문제는 각 (a[i],0)과 (b[i],1) 두 점을 잇는 N가지 직선들 중 다른 어떤 직선과도 겹치지 않는 직선의 수를 세는 문제이다.N^2으로 완전 탐색을 하는 방법으로는 해결이 불가능하니, 보통 이러한 류의 문제에서는 스위핑을 이용하게 되는데우선 a[i]를 기준으로 정렬을 해보자.그러고 a[i]가 증가하는 순서대로 보면 이러한 생각을 하게 될 수 있다.내가 이전에 본 직선들의 b[x]의 좌표 중에 나의 b[i]보다 하나라도 큰 수가 있다면 나는 이전에 업데이트 된 직선에 의해서 겹치는 직선이 된다는 걸 알 수 있다.이러한 원리로 우선 a[i]가 증가되는 순서로 안되는 직선들을 걸러준다.하지만 이렇게 처리하면 몇가지 직선이.. 더보기 제이크 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.. 더보기 이전 1 2 3 4 5 6 7 ··· 36 다음
