알고스팟 ANNIETIBBER

애니 티버가 서로 봤을 때 좌우 관계가 반대인 쌍의 수를 세는 문제이다.

각도로 정렬하면 답이 되는 경우는, 정렬된 배열 상에서 애니가 기준으로 보는 별의 왼쪽에 있는 별이 티버 배열에선 오른쪽에 있는 경우이다. 이는 inversion의 수와 같다.

머지소트를 짜거나, 구간합을 계산할 수 있는 자료구조를 쓰면 된다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기

Union-Find, Disjoint Set

상호배타적 집합( 서로소집합 )을 표현할때 쓰는 자료구조. 초기에 모든 노드의 부모노드를 자기자신으로 초기화한다. find연산 어떤 노드가 포함된 집합이 어딘지 알기 위해서는 그 노드 자신이 부모노드인 노드가 나올때가지 노드의 부모노드를 타고 올라간다. 이때 이 노드가 그 집합을 대표하는 노드가 되며 만약 어떤 다른 두 노드를 find연산한 결과가 같다면 그 둘은 같은 집합안에 있다. 나중에 find연산시 드는 시간을 줄이기 위해 path compression을 사용 할 수 있다. (return parent[x] = findSet(parent[x])로 부모노드를 바로 이어준다.) union연산 두 집합을 합치는 연산, 어떤 한 집합을 대표하는 노드의 부모노드를 다른 한쪽의 대표노드로 바꿔주면 된다. 이때 find연산시 지나가는 노드 숫자를 줄이기 위해 rank를 비교하여 그에 따라 어떤 집합이 parent가 될지 정한다. (path compression때문에 정확한 rank를 보존 할 수는 없다.) 관련문제 https://www.acmicpc.net/problem/1717 https://www.acmicpc.net/problem/1197 https://www.acmicpc.net/problem/1976 http://codeforces.com/problemset/problem/500/B void init (){ for(int i=0;i<n;++i) parent[i]=i; } int findSet (int x){ if(x==parent[x]) return x; return parent[x] = findSet(parent[x]); } void unionSet (int a, int b){ a = findset(a); b = findSet(b); if(a==b)return; if(rank[a]>rank[b]) parent[b] = a; else
계속 읽기