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. 분할 정복(divide and conquer) 분할 = 큰 문제를 여러 개의 작은 문제로 쪼갠 다음 정복 = 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법 충분히 크기가 큰 문제를 쉽게 해결할 수 있는 부분 문제로 분할해 나가고, 분할된 하위 문제를 해결하여 이 결과를 조합하여 윗단계 문제에 대한 답으로 낸다 2. 방법 정답을 쉽게 도출할 수 있을 때까지 재귀적으로 분할된 단위로 자신을 호출하면서 범위를 조금씩 줄여나감(분할단계) 답을 쉽게 도출하는 단계까지 도달한다면 재귀함수는 정답을 return하고 이렇게 return하면서 이를 이용해 재귀 stack에 쌓인 윗단계 재귀함수의 값을 return해나가는 것이 정복단계 def f(x): if (f(x)가 간단함): return f(x) el..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
