미분당한 적분상수

볼록 껍질은 2차원 상에 점들이 여러 개 있을 때 그것들 중 일부를 선택하여 나머지 점들을 모두 포함하는 볼록 다각형이다. 볼록 껍질을 구하는 방법은 여러 가지가 있지만 주로 O(NlogN)의 시간복잡도를 가지는 그라함 스캔(Graham's scan) 알고리즘을 사용한다. 다음과 같이 점들이 있다고 하자. 시작할 때 보통 가장 밑에 있는 점을 시작점으로 한다. 그러한 점이 여러 개 있을 때 가장 왼쪽의 점을 선택한다. 선택한 점부터 시작하여 반시계 방향으로 진행한다. (시계 방향도 가능함) 먼저 시작점으로부터 반시계방향으로 나머지 점들을 정렬해 준다. 스택에서 점들을 관리하여 Convex Hull를 만들어 줄 것이다. 스택의 최상단 점을 B, 그다음의 점을 A라고 하자. 벡터 AB에 대해 순회할 차례의 ..

금광 세그는 구간 [ L, R ] 에서 연속합의 최대를 구해주는 세그먼트 트리이다. 이름이 왜 금광이냐 하면 KOI 2014년도 중등부 4번 문제로 '금광'이란 문제가 나왔고 이때 만점자가 한 명도 없었다. 그때부터 이 테크닉이 유명해지면서 금광 세그라고 불리기 시작했다. 이 세그먼트 트리는 4가지의 값을 저장한다. 1. 왼쪽부터 시작하는 연속합의 최대 2. 오른쪽부터 시작하는 연속합의 최대 3. 그냥 구간합 4. 우리가 원하는 구간 연속합의 최대 1,2,3을 가지고 4를 구하는 느낌이라 보면 된다. 아래의 수열로 예시를 들어보자. {10, -4, 3, 1, 5, 6, -35, 12, 21, -1} 1. 왼쪽부터 시작하는 연속합의 최대 왼쪽부터 시작하는 연속합은 {10, 6, 9, 10, 15, 21, ..

tree dp 이전에 일반적인 dp에 대해 살짝 이야기하고 tree dp로 넘어가려 한다. 먼저 어떤 문제를 dp로 풀기 위해서는 다음 3가지 조건을 만족해야 한다. 1) 큰 문제를 작은 문제로 나눌 수 있다. 2) 충분히 작은 문제는 쉽게 풀 수 있다. 3) 작은 문제들의 답에서 큰 문제의 답을 구할 수 있다. 이를 만족하는 문제일 때, 작은 문제에서 구한 답을 이용해 큰 문제의 답을 구하는 게 일반적인 dp문제이다. 이제 tree dp에 대해 살펴보자. 트리는 '트리 안에 또 다른 트리(서브 트리)가 존재한다.' 라는 특징을 가지고 있다. 이는 위에서 언급한 문제를 dp로 풀기 위한 조건 1과 흡사하다. 따라서 tree dp의 dp 테이블은 이런 형태를 가진다. dp[ i ] : i를 루트 노드로 하..

컴퓨터는 수를 이진수로 표현한다. 이것을 이용해서 이진수를 자료구조로 사용하는 기법을 비트마스킹이라 한다. 0과 1로 표현하기 때문에 어떤 것의 유무를 판단할 때 사용한다. 비트 마스킹 연산은 다음과 같다. (저장 공간 변수의 이름을 bit_mask라고 하자.) '1'로 만들기 x위치의 비트를 1로 만들고 싶다면, OR( | )연산을 사용한다. bit_mask |= 1

1. 그래프의 간선들을 가중치 기준으로 오름차순 정렬한다. 2. 정렬된 간선들을 차례대로 채택하여 그래프를 만들어간다. 3. 사이클이 형성될 경우 그 간선은 채택되지 않는다. *사이클 체크는 유니온 파인드(Union-Find)로 4. 이 과정을 반복하면, 최소 스패닝 트리가 된다. 정점의 개수 V, 간선의 개수 E 일때, 시간 복잡도는 유니온 파인드에서 O(V)라고 해도, 간선을 정렬할 때 이미 O(ElogE)이기 때문에 크루스칼의 시간 복잡도는 보통 O(ElogE)라 한다 총 가중치 합이 46인 스패닝 트리가 만들어진다. 코드(c++) #include using namespace std; #define Pair pair vector parent; vector graph; int n; // 사이클 체크 ..

10986 나머지 합(acmicpc.net) 어떤 수열의 부분합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제이다. 모든 부분합에 대해서 경우의 수를 세어주면 O(N2)의 시간에 해결할 수 있다.하지만 N의 범위가 106까지 이므로이 시간 복잡도로는 문제를 해결할 수 없다. A의 누적합 배열을 prefix라 하고잘 생각해 보면 우리가 원하는 경우는(prefix[j] - prefix[i-1])%m == 0인 경우이다. (i  이를 풀어보면prefix[j]%m - prefix[i-1]%m == 0prefix[j]%m == prefix[i-1]%m을 얻을 수 있다. 서로 나머지가 같은 것을 선택하면 서로 상쇄하기 때문에(부분합을 구할때 prefix[j] - prefix[i-1] 를 하는 것을 생각해보면 ..

2143 두 배열의 합(acmicpc.net) A,B 두 배열이 주어지고이 두 배열의 부분합의 합이 T가 되는 경우를 구하면 되는 문제이다. 이 문제의 해결 방법으로는 누적합+이분탐색, 누적합+map 정도 있는 것 같다.좀 더 직관적이라고 생각하는 누적합+map 풀이에 대해 설명하겠다. N의 범위가 1이므로 상당히 여유롭다.이 단서를 가지고 조금 무식하게 접근해 볼 것이다. 부분합의 대한 정보를 사용해야하므로당연히 A와 B의 누적합을 필요로 한다. naïve하게 모든 경우를 다 구해볼 경우에는 통과가 가능할까 생각해보자.vector Aprefix, Bprefix;for(int i=0; iA배열에서의 모든 부분합을 구할 때 O(N2)B배열에서의 모든 부분합을 구할 때 O(N2)이 두 경우에 대해 모든 조합..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net dp로 풀 수 있는 문제이다. 다만 여기에는 생각할 것이 조금 많아서 좀 어려운 편이다. 이 문제는 포도주를 연속으로 3개 이상은 마시지 않으면서 최대한 많이 마셔야 한다. 이 "연속으로 3개 이상은 불가" 라는 조건이 꽤 까다로운데 이건 (2579 계단 오르기)를 풀어봤으면 쉽게 해결책을 떠올릴 수 있다. (두 단계 이전의 값을 이용하여 현재 값을 채운다) 문제를 풀기 위해 생각을 하다 보면 문제..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net dp로 풀 수 있는 문제이다. 문제의 난이도 표기가 다른 문제들에 비해 높은 편이지만 dp 테이블의 정의를 정확히 정의해 준다면 이 문제는 굉장히 쉬워진다. 문제에서 요구하는 사항을 보자. 이웃하는 집은 색이 같지 않아야 한다. 집을 칠하는 최소 비용을 구하자. 그럼 이 조건들을 보며 dp 테이블을 어떻게 정의할지 생각해 보자. i번째 집을 선택해야 하는 단계라고 가정하자. ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net dp로 풀 수 있는 대표적인 문제이다. 이 문제에서 요구하는 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 마지막 도착 계단은 반드시 밟아야 한다. 여기서 문제는 2번 조건이다. 다른 문제처럼 점화식을 세우려고 보니까 2번 조건 때문에 쉽게 되지 않는다. 여기서 한 번 더 생각해 준다. 보통 다른 문제들은 한 단계 이전의 값을 이용해 ..