sqrt decomposition5 백준 10090 자바 - Counting Inversions (boj 10090 java) 문제 : boj10090 n개를 입력받으면서 매번 입력받은 값이 k라 하면, 매번 이전까지 나온 수 중 k보다 큰 수가 몇 번 나왔는지만 알면 된다. 머지소트트리, 세그먼트트리, 제곱근 분할법이 이걸 알 수 있는 자료구조들이다(물론 더 있을 수 있다). 별다른 응용없이 해당 자료구조 중 아무꺼나 적용하면 풀리는 문제라 셋 중 맘에 드는걸로 검색해서 배워보자! 개인적으로 구현 난이도는 제곱근 분할법 < 머지소트트리 2022. 4. 8. 백준 5419 자바 - 북서풍 (boj 5419 java) 문제 : boj5419 1. 일단 모든 쌍을 직접 확인해보자! (brute force) n개의 정점 모두에 대해 모든 쌍을 확인하면서 조건을 만족하는지 확인해보면 된다. 이 경우 코드는 아래와 같이 될 것이다. 물론 이대론 O(N^2)이 되므로 시간 내에 통과할 수 없다! 어쨌든 어떠한 점이 자신보다 x가 작거나 같고, y가 크거나 같은지 확인하면 될 것임을 알 수 있다. ArrayList arr = new ArrayList(); void add(Island island) { arr.add(island); } long getAnswer() { long cnt = 0; for (int i = 0; i < arr.size(); i++) { for (int j = i+1; j < arr.size(); j++).. 2022. 3. 31. 백준 13537 자바 - 수열과 쿼리 1 (BOJ 13537 JAVA) 문제 : boj13537 기본적으로 알고 있어야 하는 알고리즘 기법들이 좀 있어야 이해할 수 있는 풀이 입니다. 모르는 알고리즘이 있다면 별도로 공부하셔야 이해하실 수 있습니다. 결국 통과된 풀이에 쓰인 오프라인 쿼리는 사실 어차피 값이 변경되지 않으므로, 순서를 바꿔서 쿼리를 진행하더라도 원래 위치만 안다면 순서를 바꿔서 답을 구한 후, 원래 위치에 맞게 답만 출력해주면 된다고만 이해하시면 됩니다. 제곱근 분할법은 여기를 참고하시면 될 것 같습니다. 몰라도 사실 유-명한 세그먼트 트리를 사용하면 더 효율적으로 풀 수 있습니다. (제곱근 분할법인 sqrt(N), 세그먼트 트리는 logN) 1. 시간초과 난 풀이방법 '1'은 오답노트 느낌으로 시간초과 난 풀이방법을 적은 것이니, 통과한 풀이를 보고 싶으시.. 2022. 3. 25. 백준 14428 자바 - 수열과 쿼리 16 (BOJ 14428 JAVA) 문제 : boj14428 가장 간단하게 생각할 수 있는 방법인 brute force부터 확인해보자. 10만개의 N개가 주어지고, 모든 쿼리가 '2 1 100000' 이런식이라면 O(NM)이 필요할 것이다. 따라서 시간내에 통과할 수 없다. 사실 이런식으로 중간중간 값이 변경되고, 범위에 대한 쿼리를 출력하는 유형은 대표적으로 세그먼트 트리(segment tree)를 사용하는 문제이다. 내 경우엔 조금 더 비효율적이지만, 훨씬 간단하고 구현을 이해하기 편하다고 생각되는 sqrt decompositon 방식을 사용해서 풀어봤다. 1. Sqrt decomposition 초기화 (코드의 init 함수) 이론적으론 세그먼트 트리에 비해 이해하기가 엄청 간단하다. 특정 수열이 N개의 수를 가진다면 N의 제곱근만큼 .. 2022. 2. 13. 백준 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. 이전 1 다음
