본문 바로가기 메뉴 바로가기

구사과

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

구사과

검색하기 폼
  • 분류 전체보기 (300)
    • 공부 (256)
    • 음악 (25)
    • 생각 (18)
  • 방명록

Dispatching (APIO 2012)

http://koistudy.net/?mid=prob_page&NO=593 1. Naive ( O(N^2lgN) ) 트리에 대한 기본적인 지식이 있으면 풀 수 있다. 서브트리의 경우의 수가 N개이니, N개의 각 경우에 대해서 내부에 있는 노드를 Greedy하게 더해서 경비병을 최대화 하면 된다.내부 노드에 있는 cost들을 그때 그때 sort해주면 N^2lgN이다. 2. Naive (...) ( O(Nlg^2N) ) 일단 그때 그때 sort해주기 보다는 priority_queue 등의 자료구조를 사용해서 서브트리에 있는 원소들을 재귀적으로 합쳐주자.이 역시 O(N^2lgN)이 걸린다. 이 때 합치는 대상이 되는 힙을 "가장 원소 개수가 많은 힙" 으로 설정해주자.약간의 커팅.... 은 무슨, 이걸로 시간..

공부 2015. 1. 31. 02:00
Bjork - Bachelorette

(Homogenic, 1997)

음악 2015. 1. 28. 11:42
루트 야매

그냥 이번에 코드포스에 나와서.버킷 등의 특별한 자료구조를 안 쓰고 O(Sqrt(N)) 의 시간복잡도를 보이는 테크닉을아는것만... 서술하겠다. 1. http://koistudy.net/?mid=prob_page&NO=1069 Naive하게 코딩했을때 O(QNlgN) 이 나온다. (사실 데이터 약해서 카운팅소트로 된대여... 비밀!)이때 쿼리를 다음과 같이 정렬해보자. (query 구조체는 s,e 값을 가진다) bool cmp(query x, query y){return x.s/SQRT == y.s/ SQRT ? (x.e < y.e) : (x.s < y.s)} start / SQRT 값이 일정할 때 end 값은 단조증가할 것이기 때문에 end의 기준에서는 1 ~ N까지의 원소를 N * SQRT 번 훑게 ..

공부 2015. 1. 19. 16:36
이전 1 ··· 92 93 94 95 96 97 98 ··· 100 다음
이전 다음
공지사항
최근에 올라온 글
  • Deep Cuts
  • Separating Hyperplanes, Lag⋯
  • The Cut-Matching Game: Expa⋯
  • 구간 최장 증가 부분 수열 쿼리 (Part 2)
Total
977,888
Today
67
Yesterday
478

Blog is powered by Tistory / Designed by Tistory

티스토리툴바