본문 바로가기

전체 글

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 더보기
BOJ)14426 접두사 찾기 문제: icpc.me/14426 N개의 문자열로 이루어진 집합 S가 주어질 때 M개의 문자열 중에서 집합 S에 포함 된 문자열 중 하나 이상의 접두사인 문자열들의 수를 출력하는 문제이다. 문자열의 길이가 짧음을 이용하여 트라이를 사용하여 문제를 해결 할 수 있다. N개의 문자열을 모두 트라이에 삽입해준 뒤 문자열 X에 대해 검색을 한다고 가정하면 X가 끝날 때 까지 트라이에서 계속 탐색이 가능하면 true를 중간에 경로가 없다면 false 를 return하도록 구현해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include using namespace std;int n, m;ch.. 더보기

티스토리툴바