알고리즘 관련/BOJ 썸네일형 리스트형 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.. 더보기 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으.. 더보기 BOJ)11003 최소값 찾기 문제: icpc.me/11003 구간 n에서 ai-l+1 ~ai의 최솟값을 매번 찍어내는 문제이다. RMQ 문제로 생각하여 세그트리나 multiset을 이용한 풀이를 예전에 제출했지만 n이 너무나도 커서 tle를 맞은 후 잊고 있던 문제였지만 오늘 다른 문제에서 다이나믹프로그래밍을 공부하다가 필요에 의해 다시 풀게 된 문제이다. 이 문제는 deque를 이용하여 해결할 수 있다. 연속 된 시퀀스에서 deque에는 pair형으로 해당 값과 해당 인덱스를 가지고 있을것이다. 우리는 답을 출력할 때 deque에 삽입 되어있는 구간에서 최솟값을 출력해야 하기때문에 앞이나 뒤에 최솟값을 가지고 있어야한다. 일단 deque의 front에 최솟값을 가지고 있다고 해보자. 그러면서 만약 deque의 front의 값의 인.. 더보기 BOJ)1460 진욱이의 농장 문제: icpc.me/1460 n*n 크기의 격자에 씨를 뿌리는 방법이 주어지고 격자에서 임의의 정사각형을 선택하여 정사각형 내부의 점에 서로 다른 씨앗이 최대 2개가 되도록 정사각형을 선택할 때 가장 넓은 정사각형의 넓이를 출력하는 문제이다. 씨앗의 종류인 F의 범위가 0~7인걸 이용하여 F^2+F로 모든 경우의 씨앗을 정한다면 현재 상태에서 해당하는 씨앗이 뿌려져있는 가장 넓은 정사각형을 구하는 문제로 치환하여 풀 수 있다. 이는 다이나믹 프로그래밍을 이용하여 n^2에 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std;int res, a[10.. 더보기 BOJ)13548 수열과 쿼리 6 문제: icpc.me/13548 길이가 N인 수열이 주어질 때 구간 i j 사이에 가장 많이 등장한 수가 몇번 등장했는지 출력하는 문제이다. 이 문제를 온라인으로 수행하려고하면 굉장히 힘들어 보인다. 하지만 업데이트가 이루어지지 않기 때문에 오프라인 쿼리 문제로 변형시켜서 풀어볼 수 있다. 따라서 이 문제를 mo's algorithm을 이용하여 풀건데 가장 많이 등장하는 수를 결정해야 하기 때문에 현재까지 가장 많이 등장하는 수를 계속 가지고 있어야하고 각각의 수가 몇번 등장하였나 배열을 a, i번 등장한 수가 몇개 있나 배열을 b에 각각 저장해두면 현재 쿼리의 답이 x면 만약 add로 인하여 추가 된 b가 x보다 크다면 x를 증가시켜주고 erase로 인하여 x만큼 등장한 수가 없어진다면 x를 감소시켜주.. 더보기 이전 1 2 3 4 5 6 7 ··· 31 다음