본문 바로가기

오프라인 쿼리11

[자바] 백준 2843 - 마블 (java) 문제 : boj2843 필요 알고리즘 개념 오프라인 쿼리 (offline query) 쿼리(질의)의 순서를 변경해서 푸는 아이디어를 생각해낼 수 있어야 한다. 분리 집합 (disjoint set) 분리 집합 개념과, 분리집합에서 집합이 합쳐지는 방향을 강제할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서는 조약돌이 멈추는 정점을 묻는 쿼리와 간선을 지우는 쿼리가 존재한다. 일반적으로 간선을 지우.. 2023. 1. 2.
[자바] 백준 16978 - 수열과 쿼리 22 (java) 문제 : boj16978 필요 알고리즘 개념 오프라인 쿼리 온라인 쿼리로 풀려면 어려운 문제지만, 오프라인 쿼리 아이디어가 떠올랐다면 훨씬 쉬워진다. 세그먼트 트리 또는 펜윅 트리 point update range query 문제로 세그먼트 혹은 펜윅 트리를 사용해 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 point update와 range query가 존재하는 문제인데, 잘 생각해보면 update와 qu.. 2022. 9. 17.
[자바] 백준 8244 - Tales of seafaring (boj java) 문제 : boj8244 자바로는 정신건강상 시도 안하는걸 추천한다. 자바론 사실상 통과 불가능한 메모리 제한이라 메모리 초과를 뚫기 위해 이상한 짓들을 많이 해야 한다. 1. 키 아이디어 기본 아이디어는 어찌보면 생각하기 어렵고 어찌보면 간단한데 다음의 그래프를 보자. 이 때 k개로 주어진 각각의 'tales that Bytensson has heard'중 하나를 Q라고 칭하겠다. 이 때 1에서 출발해서 2로 가는 최단길이는 1이다. 그럼 Q가 '1 2 1'이라면 당연히 가능하다. 그럼 '1 2 3'이나 '1 2 5'라도 가능할까? 이것도 가능하다. 왜냐면 한 번 들렸던 곳을 다시 못간다는 제한이 없으므로 다음과 같이 왔다갔다 하면 되기 때문이다. 최단거리는 1이지만, 그 이후로 1+2*n (n은 0부터.. 2022. 4. 30.
백준 13537 자바 - 수열과 쿼리 1 (BOJ 13537 JAVA) 문제 : boj13537 기본적으로 알고 있어야 하는 알고리즘 기법들이 좀 있어야 이해할 수 있는 풀이 입니다. 모르는 알고리즘이 있다면 별도로 공부하셔야 이해하실 수 있습니다. 결국 통과된 풀이에 쓰인 오프라인 쿼리는 사실 어차피 값이 변경되지 않으므로, 순서를 바꿔서 쿼리를 진행하더라도 원래 위치만 안다면 순서를 바꿔서 답을 구한 후, 원래 위치에 맞게 답만 출력해주면 된다고만 이해하시면 됩니다. 제곱근 분할법은 여기를 참고하시면 될 것 같습니다. 몰라도 사실 유-명한 세그먼트 트리를 사용하면 더 효율적으로 풀 수 있습니다. (제곱근 분할법인 sqrt(N), 세그먼트 트리는 logN) 1. 시간초과 난 풀이방법 '1'은 오답노트 느낌으로 시간초과 난 풀이방법을 적은 것이니, 통과한 풀이를 보고 싶으시.. 2022. 3. 25.
백준 20156 자바 - 기왕 이렇게 된 거 암기왕이 되어라 (BOJ 20156 JAVA) 문제 : boj20156 구현도 빡쌘편이고 함정카드도 꽤 생각하기 힘든 녀석이었다. 역시 항상 20퍼대 이하의 정답률 문제들은 항상 뭔가가 있다. 그리고 요즘 스트릭만 채운다고 실버위주로 풀다가 오랜만에 플래 풀어보니 체감이 확 된다 ㅋㅋㅋ 1. 우선 다른거 다 빼고 동일 스터디 그룹인지 어떻게 알 수 있을지 생각해보자. 이 부분은 간단하다. union-find를 사용해 disjoint set을 파악하면 된다. 입력으로 받은 B와 C가 동일한 그룹인지 확인하려면, B와 C가 같은 그룹내에 속한지 판단만 하면 알 수 있다(일반적으로 union-find를 사용했다면 결국 find(B) == find(C) 라면 동일 그룹이다). 2. 그룹이 해제는 어떻게 해요? 생각할게 너무 많아요! 그룹을 해제하는건 어렵지.. 2022. 3. 8.
백준 13547 자바 - 수열과 쿼리 5 (BOJ 13547 JAVA) 문제 : boj13547 문제에 비해 필요한 아이디어 및 구현과정은 상당히 복잡한 문제이므로 간단한 부분부터 차례대로 생각해보자. 1. 우선은 단건의 쿼리를 해결할 방법을 생각해보자. [Ai, Aj]에 존재하는 서로다른 수의 개수를 알 수 있어야 한다. 여러 방법이 있겠으나, 각 값을 표현할 메모리가 충분하다면 값의 최대 크기에 해당하는 배열을 만들어 해당 수가 나왔는지 체크하는 방법이 가장 효율적이다. 이 문제에서는 N개의 값 각각의 최대값은 1,000,000이므로 100만개짜리 boolean 배열만 있으면 된다. 100만개짜리 배열 arr이 있고, cnt라는 변수를 뒀다고 해보자. 각 쿼리에서 i와 j를 입력받았을 때 Ai부터 Aj까지 순회하며 배열에 체크한다. 이미 체크되어 있던게 아니라면 cnt를.. 2022. 1. 19.
백준 14413 자바 - Poklon (BOJ 14413 JAVA) 문제 : boj14413 1. update가 없는 쿼리 문제로, 오프라인 쿼리로 처리해도 된다. 또한 각 쿼리마다 범위가 계속 변경되는 와중에 원하는 답을 구하는 쿼리 문제이다. 따라서 mo's algorithm을 사용할 경우 효율적으로 풀 수 있다. 모스 알고리즘은 쿼리의 수가 n이고 각 쿼리 qi = (a, b)라 할 때(문제에선 l, r이었음. l이 헷갈려서 a, b로 변경하여 설명함), 모든 쿼리를 (a/sqrt(n), b) 순서로 정렬하게 된다(a/sqrt(n)은 소수점 버리고 정수로). 이 경우 각 쿼리를 정렬 후 수행 시 모든 경우에 대해 a와 b의 변화량이 최대 N*sqrt(N) 정도로 고정되고, 효율적으로 직전에 구해둔 쿼리의 데이터 중 중복되는 부분을 재사용할 수 있다. 예를들어 q1=.. 2021. 12. 11.
백준 2912 자바 - 백설공주와 난쟁이 (BOJ 2912 JAVA) 문제 : https://www.acmicpc.net/problem/2912 1. 기본적인 아이디어는 각 쿼리의 [a, b] 구간에 대해 매번 [a, b] 전체를 확인하지 않고, 이전에 확인했던 구간과 겹치는 구간은 제외하고 확인하는 것이다. 예를들어 이전에 확인했던 구간이 [1, 100]이고 이번에 확인할 구간이 [4, 95]라고 해보자. 이 때, [1, 100] 구간을 전부 확인하면 100번 + [4, 95] 구간을 전부 확인하면 92번 봐야 한다. 그럼 192번 동작해야 한다. 하지만 [1, 100] 구간의 결과에서 [1, 3] 구간을 빼고, [96, 100] 구간을 빼면 [4, 95] 구간 전체를 본 것과 동일한 결과를 얻을 수 있다. 이 경우 108번만 동작하면 된다. 2. update가 없는 쿼.. 2021. 11. 20.
백준 14897 자바 - 서로 다른 수와 쿼리 1 (BOJ 14897 JAVA) 문제 : https://www.acmicpc.net/problem/14897 확실히 나한테 아직 플래수준은 어려운것같다. 아예 모르는 알고리즘 지식을 요구하는 문제가 아닌이상 꾸역꾸역 풀긴 하는 편인데 사실 이런게 CP에서 나왔다고 치면 시간내에 절대 못푼다. 못해도 1시간 이상은 걸리는 것 같다. 오답률도 높은편 ㅠ 뭐 꾸준히 하다보면 언젠가 플래수준도 쉽게 풀겠지! 생각 과정 풀이만 보려면 아래로 쭉 내려서 '풀이 정리'로 바로 가시면 됩니다. 1. 우선 문제에서 바로바로 생각나는걸 정리했다. - 업데이트가 없는 쿼리 이므로, 쿼리 순서를 마음대로 처리해도 된다. (오프라인 쿼리) - N이 최대 100만, 배열에 포함된 수는 최대 10억이다. 이 때, 문제에서 묻는건 서로 다른 수의 개수이므로 배열에.. 2021. 11. 19.
백준 17469 자바 - 트리의 색깔과 쿼리 (BOJ 17469 JAVA) [ 백준 17469 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결해야 한다. 쿼리는 '1 a'와 같이 들어오면 간선 제거, '2 a'와 같이 들어오면 a에서 갈 수 있는 정점들에 포함된 색깔 종류의 개수를 출력해야 한다. 당연히 매번 쿼리를 진행하고 bfs나 dfs로 갈 수 있는 경로를 찾고 또 해당 노드들에 존재하는 색깔 종류를 셀 순 없다(시간초과). 그럼 일단 각 부분들을 뭘 이용해 구할 수 있을지 확인해보자. 1. 갈 수 있는 정점들 확인 : union-find를 사용한 그룹짓기 2. 각 그룹에 포함된 색깔 종류의 개수 : HashSet을 사용하면 애초에 동일한 색깔이 중복해서 안들어가니, 해당 set의 size()만 확인하면 해당 그룹에 포함된 색깔 종류의 개수를 알 수 .. 2021. 11. 4.