Segment Tree5 [자바, C++] 백준 2042 - 구간 합 구하기 (java cpp) 문제 : boj2042 필요 알고리즘 개념 펜윅 트리, 세그먼트 트리 등 펜윅 트리, 세그먼트 트리 등 구간 쿼리 알고리즘(자료구조)를 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 펜윅 트리, 세그먼트 트리 등으로 풀 수 있는 기본형태의 문제이다. 펜윅 트리로 풀려면 작성해둔 펜윅 트리 글에서 '기본 : 펜윅 트리' 부분을 읽어보면 이 문제를 풀 수 있다. 코드(C++ 펜윅 트리) : github.. 2022. 8. 12. 백준 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. 이전 1 다음
