알고리즘/백준 문제풀이
-
[백준 17975번] Strike Zone알고리즘/백준 문제풀이 2022. 2. 9. 21:17
금광 (https://www.acmicpc.net/problem/10167) 문제와 동일한 문제이다. 금광에서는 금광(x, y)마다 이익 또는 손해(w)가 있지만, 이 문제에서는 스트라이크/볼 지점의 이익/손해 가 정해져있다. 입력 값이 아래와 같이 들어오는데 2 -1 -1 4 4 2 0 0 2 2 5 2 첫 번째 숫자 2 는 스트라이크인 점의 수 그리고 2개의 줄(-1, -1), (4, 4)에 스트라이크인 점의 위치 그 다음 숫자는 2 는 볼인 점의 수 그리고 2개의 줄(0, 0), (2, 2)에 볼인 점의 위치 끝으로 마지막 줄은 스트라이크 점의 이익(5)과 볼의 손해(2) 값이 주어진다. 따라서 금광 문제와 동일하게, 금광세그로 문제를 풀면된다. 금광 문제에서 xi, yi, wi 로 문제를 풀었다면..
-
[백준 23238번] Best Student알고리즘/백준 문제풀이 2022. 1. 20. 21:50
참고 : 풀이 코드는 없습니다. 힌트만 드립니다. 1. Mo's -> Query sort, delete, add 2. Student ID -> 값 / 좌표 압축 3. 압축된 값의 범위가 1 ~ 10만이고, 그 값을 SQRT 로 나눔 (SQRT Decomposition) 4. SQRT 로 나눈 버킷마다 빈도수의 MAX 값 저장 5. 쿼리에 대한 답은 모든 버킷에서 빈도수의 MAX 값을 가진 버킷을 찾음. 버킷을 찾았으면 그 안에서 MAX 값을 또 찾아줌. 빈도수가 같은 값이 있으면 ID 가 더 큰 값을 찾음. O(Q) * O(sqrt + sqrt) (값 / 좌표 압축을 할 때 정렬을 해서 실제 값이 크면, 압축된 값도 크도록 해주면 구현이 편해짐) 시간복잡도 O(Q * sqrt)