알고리즘 관련 썸네일형 리스트형 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.. 더보기 좌표압축 기법 좌표압축 기법은 Problem Solving을 하다보면 정말 정말 정말 자주 쓰이는 테크닉이다. 세그트리(or BIT) 등등.. 구간 쿼리와 함께 같이 쓰이는 경우도 많고, 오프라인 쿼리등을 처리할 때 등등 많은 경우에서 유용하게 이용된다. 개념에 대한 설명을 하기 위하여 한 문제를 예시로 들어보겠다. N( 더보기 BOJ)5542 JOI 국가의 행사 문제: icpc.me/5542 쿼리에서 받는 두 도시간의 경로 중 경로에 포함 된 도시들의 축제하는 도시와의 떨어진 거리의 값들 중 최솟값이 최대가 되는 경로를 구하는 문제이다. 우선 다익스트라 알고리즘을 사용하여 각 정점들의 가중치(축제가 열리는 도시와의 최단거리)를 구해줄 수 있다. 이후 쿼리를 처리해주어야 하는데 disjoint set을 이용하여 쿼리를 처리해주려고 한다. 우선 각 쿼리 번호에 해당되는 양 끝 정점들에 쿼리 번호들을 저장해준 뒤 간선의 가중치가 큰 순서대로 간선을 정렬하여 간선을 보면서 정점을 dsu를 이용하여 병합해 줄것이다. 이 때 만약 두 정점이 같은 쿼리 번호를 가지고 있다면 해당 쿼리 번호의 답은 그 간선의 가중치가 될 것이다. 1234567891011121314151617.. 더보기 BOJ)13330 유사 팰린드롬 문제: icpc.me/13330 w를 구성할 수 있는 세타 팰린드롬의 최소 개수를 출력하는 문제이다. 이 문제를 해결하기 위하여 두가지 디피 테이블을 정의해야한다. dp1[l][r]은 l,r 구간의 u의 개수 dp2[pos]는 0~pos 의 문자열을 구성 할 수 있는 세타 팰린드롬의 최소 개수라 정의하면 n^2으로 dp2를 채우기 위해 for문을 돌릴 때 이터레이터 j에 대한 검사를 dp1으로 할 수있다. 123456789101112131415161718192021222324252627282930#include #include #include using namespace std;int n, k, l, dp[10010];int a[10010][10010];char s[10010];int func(int l.. 더보기 BOJ)13352 석양이 진다... 문제: icpc.me/13352 n개의 점들이 주어질 때 두직선만으로 모든 점을 커버가능한지 판별하는 문제이다. 얼마전 코포 B번에서 유사한 문제 http://codeforces.com/contest/849/problem/B 가 등장하였지만 코포 문제는 N^2으로 해결할 수 있었던 반면 이 문제는 N제한이 10만이기 때문에 N^2으로는 풀 수 없다. 그래서 정해를 생각해보다가 도저히 떠오르지 않아서 작년에 들었던 야매 풀이를 떠올려서 풀었다. 풀이는 랜덤하게 두 점을 뽑아서 직선을 하나 만든 다음 나머지 모든 점이 한 직선으로 놓일 수 있는지 확인한다. 여기서 나머지 모든 점이 한 직선으로 놓인다면 당연히 두직선으로 커버되는 것이니 답이 되고 안된다면 위의 행동을 반복한다. 위의 행동을 충분히 반복하였는.. 더보기 BOJ)5842 Partitioning the Farm 문제: icpc.me/5842 n*n 격자가 주어질 때 주어진 격자를 가로나 세로로 k번 분할 할 수 있다. 분할 된 각 부분들의 합의 최댓값의 최솟값을 구하는 문제이다. 최대중에 최소를 구하는 문제이므로 파라메트릭 서치로 접근할 수 있다. 다만 격자에서 처리해야하는게 좀 까다로울 수 있는데 n이 15밖에 안되므로 2^15의 모든 경우로 세로 격자를 세워준 뒤 파라메트릭 서치로 가로 격자를 세우며 답을 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include using name.. 더보기 BOJ)2337 트리 자르기 문제: icpc.me/2337 트리에서 임의의 몇개의 간선을 잘라서 크기가 m인 트리를 얻고 싶을 때 잘라야하는 간선의 최소 개수를 구하는 문제이다. 트리디피로 풀 수 있는 문제이다. 기존에는 트리 디피를 n^3의 방법으로 풀어왔지만 이번에 smu형님의 도움으로 n^2 log n으로 푸는 방법을 알게 되었다. 우선 dp테이블을 dp[here][k]를 here번 정점이 루트인 크기가 k인 트리를 만드는데 필요한 간선컷의 최솟값으로 정의하면 dp[here][k]를 어떤식으로 빌드할거냐면 here가 가지는 자식들은 여러개의 서브트리를 이룰것이다. 이 서브트리를 하나씩 병합하면서 dp[here][k]를 채울 것이다. 당연히 처음에는 dp[here][1]밖에 없을 것이다 .여기서 1은 곧 자기 자신이다 이는 0으.. 더보기 이전 1 2 3 4 5 6 7 ··· 34 다음
