devbelly

문제 www.acmicpc.net/problem/2517 알고리즘 세그먼트 트리, 좌표압축 풀이 현재 달리는 사람의 순서가 주어질 때, 자신의 최대등수를 출력하는 문제입니다. 자신보다 능력이 뛰어난 사람이 앞에 달리고 있으면 앞지를 수 없지만, 자신보다 능력이 낮은 사람이 앞에 달리고 있으면 앞지를 수도 있습니다. 쿼리는 달리는 순서대로 세그먼트트리를 업데이트 하며 그 순간 자신보다 앞에 있는 사람의 수를 묻고 있습니다. 누적합으로 자신앞에 있는 사람의 수를 알 수 있으므로 펜윅트리를 활용합시다. 유사한 문제가 많지만 그 문제들과 다른점은 주어지는 능력값이 굉장히 큰 수 라는 것입니다. 이는 좌표압축을 통해 해결가능합니다. 각 쿼리당 요구하는 시간복잡도는 $O(logN)$ 이므로 시간복잡도는 $O(Nlo..

문제 www.acmicpc.net/problem/18870 알고리즘 좌표압축 풀이 상대적인 크기 관계는 유지한 채, 숫자의 크기만 줄이는 테크닉입니다. 이를 위해선 두 개의 배열이 필요합니다. 하나는 원래의 원소를 담고 있는 배열, 나머지는 중복제거를 한 후의 배열입니다. 중복제거를 한 배열의 인덱스가 좌표압축의 결과가 됩니다. 코드 #include #define rep(i,n) for(int i=0;i N; rep(i, N) { cin >> arr[i]; vt.emplace_back(arr[i]); } sort(vt.begin(), vt.end()); vt.erase(unique(vt.begin(), vt.end()), vt.end()); rep(i, N) { cout