이쪽은 그냥 내가 풀다가 죽어라 헷갈리는 부분이나
새로 배우면서 흥미롭다 싶은부분 메모하는 글들이기때문에
작성방법이 묘할것이라 생각함.
세그트리 밀다가 만난 문제 유형
정렬은 그냥 무지성 std::sort 박아서
정렬을 한번쯤 정리해두는게 좋을것 같았다.
해당 유형의 문제로는
1517번, 23336번, 10090번 등등이 있다
머지소트 merge sort
머지소트는 정렬에 대해서 분할정복을 적용한 케이스라고 이해하면 되겠다.
void mergeSort(int s, int e){
if(s<e){
int mid = (s+e)/2;
mergeSort(s,mid);
mergeSort(mid+1,e);
merge(s,e);
}
return;
}cpp 로 간단하게 머지소트를 짜보았는데,
간단히 메모해두자면
분할정복해서 정렬해놓고
merge를 통해 둘이 합쳐서 하나의 정렬된 배열을 만든다.
즉 mergeSort(1,N) 을 실행하고 난 뒤의 결과값은 [1,N] 범위만이 정렬된 배열이 된다.
머지소트는 사실 이쪽보단 병합이 더 중요한듯
그냥 포인터 두개 + 합쳐진 큰범위 배열용 포인터 한개더
잡아두고
투포인터? 느낌으로다가 잘 짜보면 된다.
void merge(int s, int e){
int mid = (s+e)/2;
int ptr1 = s;
int ptr2 = mid+1;
int tmp = s;
while(ptr1 <= mid && ptr2 <= e){
if(arr[ptr1] <= arr[ptr2]) tmparr[tmp++] = arr[ptr1++];
else tmparr[tmp++] = arr[ptr2++];
}
while(ptr1 <= mid) tmparr[tmp++] = arr[ptr1++];
while(ptr2 <= e) tmparr[tmp++] = arr[ptr2++];
for(int i=s; i<=e; i++) arr[i] = tmparr[i];
return;
}while문을 통해서 대충 정렬해주고 난 뒤 모습인데
아래에 while문 두개 더 써서
깔끔하게 정렬을 끝내주는 모습이다
그다음 for문으로 배열에 복사해줌
inversion counting 알고리즘
이게 머지소트를 위에서 설명한 이유 되시겠다.
머지소트로 해결하는 방법이 있고
세그트리로 해결하는 방법이 있다고 하는데
나는 나중에 머지소트트리도 배울거같고 해서
그냥 머지소트를 써보고자 한다.
어려울것이 진짜 하나도 없고
딱 한줄만 추가하면 된다.
ans += mid - ptr1 + 1;
이게 무엇을 의미하냐면
병합 과정에서 함수에서 선을 그려놓는다고 친다면
교차점의 개수를 세는 과정에서 나온 것이다.
해당 자료그림의 마지막 단계에서
1이 가장먼저 결과값 배열에 저장될 때,
왼쪽 배열에 있는 두개의 값은 무조건 1보다 뒤에 올 수 밖에 없게 되므로
결과적으로 6과 9 저 두개의 값은 무조건 1이 만든 선과 교차점이 생긴다.
이 교차점의 개수가 왼쪽 배열의 원소 개수와 같으며,
원소개수를 (End-Start+1) 로 세서 매번 더해주면 된다.
void merge(int s, int e){
int mid = (s+e)/2;
int ptr1 = s;
int ptr2 = mid+1;
int tmp = s;
while(ptr1 <= mid && ptr2 <= e){
if(arr[ptr1] <= arr[ptr2]) tmparr[tmp++] = arr[ptr1++];
else{
ans += (ll)(mid - ptr1 + 1);
tmparr[tmp++] = arr[ptr2++];
}
}
while(ptr1 <= mid) tmparr[tmp++] = arr[ptr1++];
while(ptr2 <= e) tmparr[tmp++] = arr[ptr2++];
for(int i=s; i<=e; i++) arr[i] = tmparr[i];
return;
}이제 문제를 날먹해보도록 하자