1. counting inversion problem inversion이란 배열 A에 대하여 자기보다 뒤(index가 큰 쪽)에 있으면서 자기보다 값이 작은 A[j]를 뜻한다. 수학적으로 i A[j]를 만족하는 (i,j)의 개수를 세는 문제이다. 단순하게 세면 $O(N^{2})$이지만 실제 위치보다 전후 관계만 본다는 점을 관찰한다면, 2,X,X,X,X,X,X,X,X,1이더라도 2와 1은 inversion이고, 2,1,X,X,X,X,X,X,X,X,...더라도 2와 1은 inversion이다. 또한 다음 그림과 같이 화살표들의 교점의 개수와 동일하다. 두 수가 서로 inversion이면 교점이 하나 생기기 때문이다. 2. 해법 위 그림에서 볼 수 있는대로, 병합정렬을 하면 자연스럽게..
1. 병합정렬(merge sort) 여러개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘을 활용함 주어진 자료를 최소 단위의 문제까지 나눈 다음에 차례대로 정렬해가면서 최종 결과를 얻어내는 방식 시간복잡도는 O(nlogn) 2. 개요 - 간단한 과정 - [69,10,30,2,16,8,31,22]를 병합정렬한다면?? 2-1) 분할과정 절반씩 자료를 왼쪽, 오른쪽으로 나눠가고 더 이상 쪼갤 수 없을때까지 반복해서 나눈다 2-2) 병합과정 가장 밑단의 왼쪽 부분집합과 오른쪽 부분집합의 원소 크기를 서로 비교하여 정렬하여 병합시키고, 최종 1개로 병합될때까지 반복함 3. 구현 길이가 1이면 정렬하지말고, 바로 return 길이가 1보다 크다면, 왼쪽과 오른쪽을 나눠준다..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
