b2r   7달 전

쿼리가 난이도에 미치는 영향이 엄청난가요? 연속합이라는 문제의 티어가 실버였던거 같은데 연속합 + 쿼리를 하니까 플레1이 됬었습니다

쿼리를 처리하기 위해서 만약 O(N)짜리 코드가 있었다면 O(logN)으로 최적화하는 방법 이외의 방법은 없나요? 쿼리를 처리할때 O(Q)가 항상 곱해지는데 O(Q)를 O(logQ)로 최적화 한다던가 그런건 불가능한가요?

aiden3233   7달 전

쿼리를 특정 순서로 정렬해서 쿼리 자체를 처리하는 시간을 전체적으로 줄이는 방법이 있기는 합니다. 이렇게 쿼리를 순서대로 보지 않고 원하는 순서대로 처리하는 방법을 쿼리를 오프라인으로 처리한다고 합니다. 32963번 문제를 보면 두 가지 풀이가 있는데요, 첫번째는 최댓값을 찾는 O(N) 과정을 이분탐색으로 O(logN) 으로 바꾸는 방법이고요, 두번째는 사과들을 맛 순서대로 정렬한 후 p 가 큰 쿼리부터 순서대로 답하면 계속 최댓값을 갱신해주며 쿼리 자체는 O(1) 에 처리할 수 있습니다. (투 포인터를 이용하면 총 N개의 사과들을 한번씩 확인하기 때문)

b2r   7달 전

그 오프라인 쿼리를 써도 결과적으로 시간복잡잡도에는 O(Q)가 곱해지는거 아닌가요???

그러니까 오프라인 쿼리 + 스위핑 이렇게 합쳐서 시간복잡도를 줄인다는 뜻인가요?

aiden3233   7달 전

제가 설명을 좀 추가했는데, 특정 순서대로 보면 단조성을 만들어낼 수 있어 각 쿼리를 처리하는 시간이 서로 다를 수 있지만 그 수행시간을 전부 합치면 O(N) 이거나 한 경우가 있습니다. 이런 경우에는 수행시간이 Q에 무관할 수도 있고요. 투 포인터 알고리즘도 공부해보면 좋을 것 같습니다.

aiden3233   7달 전

한번 https://www.acmicpc.net/proble... 이 문제를 직접 이분탐색 없이 풀어보세요.

b2r   7달 전

32963 이미 투포인터 안쓰고 오프라인 쿼리로 풀어보긴 했습니다

투포인터로도 풀어봤습니다

아 그리고 그때 수열과 쿼리 46 질문했던 사람입니다

aiden3233   7달 전

32963 번의 오프라인 쿼리 시간복잡도는 정렬하는 시복이 NlogN, 쿼리가 Q개이지고 두 포인터를 쓰면 시간복잡도가 N 이라서 전체적으로는 O(NlogN + Q(+N이지만 무시))인데요,  쿼리 자체를 효율적으로 만들어 QN을 QlogN 으로 줄이는 방법도 있겠지만 이렇게 쿼리를 원하는대로 정렬하는 것 만으로도 시간복잡도에 도움이 될 수 있다는 의미입니다.

b2r   7달 전

아 그러네요 감사합니다

b2r   7달 전

aiden3233님 이번 제6회 청소년 IT경시대회 중등부 2번문제가 저울(2437)+각 i마다 1번부터  i번을 사용하여 만들지 못하는 값의 최댓값을 출럭하는 온라인 쿼리 문제였는데 그러면 티어가 어느정도인가요?

아직 백준에 기출문제가 올라오지않아서 질문드립니다

aiden3233   7달 전

시험 본 동생한테 들어봤는데 g1~p5 정도 하지 않을까요

aiden3233   7달 전

솔직히 저울 풀어봤으면 근데 체감은 g2 정도까지 했을수도요. 저울이 풀이만 알면 직관과 구현이 쉬운 문제라서요.

b2r   7달 전

3,4번은 어느정도인가요?

aiden3233   7달 전

3,4번은 문제를 몰라요

댓글을 작성하려면 로그인해야 합니다.