본문 바로가기

분류 전체보기

BOJ)2370 시장 선거 포스터 문제:icpc.me/2370 포스터를 붙이는 순서가 주어질 때 보이는 포스터의 수를 출력하는 문제이다. 포스터의 모든 x좌표와 y좌표를 좌표압축 한 뒤 포스터를 역순으로 보면서 이미 본 포스터는 업데이트 시켜주고 내가 보이는지 여부는 이미 업데이트 된 포스터들이 나를 완전히 가리는지 확인하면 된다. 이는 세그먼트 트리를 이용하여 업데이트 된 구간의 합을 찍어냄으로 판별 가능 하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include using namespace std;int n, seg[80040], lazy[80040],.. 더보기
BOJ)3073 집으로 가는 길 문제: icpc.me/3073 집과 아이를 1:1 매칭시켜 주어야 하는데 매칭은 항상 보장되고 이때의 아이들의 최소 이동거리를 출력하는 문제이다. 1:1 매칭이 항상 보장되기 때문에 MCMF로 모델링을 하여 소스->아이->간선->집->싱크로 모델링 해주면 된다. 이 때 각 간선들의 cost를 1로 설정해주면 된다. 다만 문제에 함정이 있는데 언제 고쳐질지는 모르겠지만 입력 N,M이 20~30으로 표기되어 있지만 100 넘게 들어오는거 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879.. 더보기
BOJ)2104 부분배열 고르기 문제: icpc.me/2104 주어지는 배열에서 i~j까지의 부분 배열을 선택했을 때 (a[i]+a[i+1]+...+a[j])*(min(a[i],a[i+1]),....,a[j]) 가 최대가 되도록 i j를 선택하는 문제이다. 나이브한 풀이법으로는 i,j를 선택하는데만 O(N^2)으로 시간초과다 .. 따라서 좀 더 그리디하게 생각해보면 만약에 어떤 구간에 대해 정할 때 한 점 X를 기준으로 그 점이 최솟값이 되게 구간을 선택한다면 X를 기준으로 좌우로 최대한 X보다 큰값을 가지는 범위롤 포함하도록 배열을 선택할 수 있다. 이러한 아이디어에서 출발하여 모든 점에 대해서 이 범위를 볼건데 정렬을 해주어 작은 값부터 보면서 set에 업데이트해주어 이동가능한 lower_bound와 upper_bound를 찾아준다.. 더보기
뒤늦은 제 3회 SCPC 후기 목요일에 SCPC가 끝났다. 사실 그렇게 큰 기대를 하고 가지는 않았지만 혹시 모를 행운을 위해 플로우쪽을 준비를 해갔지만 아쉽게도 플로우 문제는 나오지 않았다 ㅠㅠ 본선에는 총 4문제가 나왔는데 1번 문제는 정말 쉬운 문제가 나왔다. 그래서 거의 시작하자마자 곳곳에서 타자소리로 어수선해졌다. 1번 문제를 빠르게 해결하고 2번 문제를 보자마자 좌절했다.. 기하라니 .. 점과 직선사이의 거리를 n^2으로 탐색하는 솔루션은 알 수 있었지만 그 이상으로 발전시키기도 힘들었고 기하는 라이브러리로만 만들어 놨지... 벡터에 관련 된 공식들이 가물가물해서 C번을 먼저 보기로 했다. C번을 보고 미디움 솔루션이 바로 떠올라서 코딩을 했다 (long long을 사용안한 초보적인 실수때매 2번이나 틀린건 비밀..) 이제.. 더보기
BOJ)2872 우리집엔 도서관이 있어 문제: icpc.me/2872 책의 순서가 주어졌을 때 책을 정렬하는데 필요한 최소 이동횟수를 출력하는 문제이다. 책을 이동하는 조건은 무조건 하나의 책을 들어서 맨위에 쌓는 방법밖에 없기 때문에 가장 뒤에 있어야 하는 책은 옮길 필요가 없다. 가장 큰 숫자부터 연속 된 숫자가 얼마나 긴 부분 증가 수열을 이루고 있는지 확인하면 된다. 1234567891011121314#include #include using namespace std;int n, a[300030], here;int main() { scanf("%d", &n); for (int i = 0; i = 0; i--) if (a[i] == here)here--; printf("%d\n", here); return 0;}Colored by Col.. 더보기
BOJ)10272 현상금 사냥꾼 김정은 문제:icpc.me/10272 왼쪽 부터 오른쪽으로 순회한 뒤 순회하지 않은 정점들을 오른쪽에서 왼쪽으로 다시 순회할 때 이동거리의 최솟값을 구하는 문제이다. 이 문제는 바이토닉 투어 문제이므로 N^2 다이나믹 프로그래밍으로 해결할 수 있다. 우선 바이토닉 투어 문제는 dp[x][y]라는 테이블을 세울 수 있다. 이 때 x.는 갈 때 y는 올 때 까지 커버한 정점들의 수 이다. 점화식을 세울 때 현재 x,y까지 커버했다면 다음에 커버해야 할 정점은 당연히 max(x,y)+1이 되므로 이 정점을 갈 때 커버할 지 올 때 커버할지만 결정해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #inc.. 더보기
L-R flow http://blog.myungwoo.kr/111 와 http://koosaga.com/134 에서 많은 부분 참고하였습니다. -간선에 lower_bound가 존재할 때 플로우를 흘릴 수 있는지 여부 확인 1. MCMF로 모델링 a->b로의 간선이 하한이 l 상한이 r일 때 a->b로 (l , -1) , (r-l ,0)으로 두가지 간선을 만들어 준 뒤 MCMF 를 돌린다면 항상 -1이 있는 쪽으로 플로우가 강제된다. 이 때 cost를 확인하여 플로우를 흘릴 수 있는 지 여부를 확인해준다. 이 때의 maxflow는 flow를 확인하여 구할 수 있다. 2. 디닉을 사용하는 방법 새로운 소스와 새로운 싱크를 만든다. 기존 싱크-> 기존 소스로 capacity가 INF인 간선을 생성한다. a->b로의 간선이 하.. 더보기
BOJ)8462 배열의 힘 문제: icpc.me/8462 시퀀스와 쿼리가 주어질 때 매 쿼리에 대한 답을 출력하는 문제이다. 쿼리는 구간이 주어지면 구간에 존재하는 모든 자연수 s에 대하여 (s 의 개수의 제곱) x s를 합한 값이다. 쿼리와 시퀀스가 10만이기 때문에 적어도 쿼리를 log나 root 시간에 처리해주고 싶지만 안타깝게도 저 쿼리를 해당 시간에 처리하기는 힘든거 같다. 하지만 쿼리 도중에 업데이트가 일어나지 않기 때문에 쿼리를 정렬한 뒤 mo's 알고리즘으로 접근한다면 해답을 얻을 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include usin.. 더보기
BOJ)3172 현주와 윤주의 재미있는 단어 게임 문제:icpc.me/3172 어떤 단어가 x가 어떤 단어 y보다 사전순으로 앞서 있으면서 y를 뒤집은 y'이 x를 뒤집은 x'보다 앞서 있다면 두 단어는 서로 좋아하지 않는다고 한다. 단어가 10만개이기 때문에 brute force로 접근한다면 시간초과를 면치 못할 것이다. 그렇기 때문에 생각을 바꾸어서 기존의 문자열 기준으로 정렬을하여 번호를 매겨준 뒤 그 번호를 가진 상태로 문자열을 다 뒤집은 후 정렬을 해주고 앞에서 부터 보면 나보다 먼저 본 문자열 중에 나보다 할당 된 번호가 큰 문자열의 수를 세주면 된다. 이는 세그먼트 트리나 펜윅 트로로 효율적으로 해결할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#in.. 더보기
BOJ)14675 단절점과 단절선 문제:icpc.me/14675 트리에서 단절선인지 단절점인지 여부를 판단하는 쿼리를 처리하는 문제이다. 단절선 단절점을 직접 구해줄 필요 없이, 트리이기 때문에 모든 선은 단절선이 된다. 트리에서 단절점 여부는 리프를 제외한 모든 노드는 단절점이 된다. 트리에서 리프판단 여부는 indegree의 개수를 세주면 된다. 1234567891011121314151617181920#include #include using namespace std;int n, m, x, y, c[100010];int main() { scanf("%d", &n); for (int i = 0; i 더보기