전체 글

힙 정렬 (Heap Sort)

힙 (Heap) - 완전 이진 트리 종류 중 한가지 - 우선순위 큐에 사용이 됨 - Max Heap, Min Heap 두가지 종류가 있음 - 완전한 정렬 형태가 아닌 느슨한 정렬 형태 (부모 노드가 두 자식 노드보다 큼) 힙 정렬 (Heap Sort) - 위에서 제시한 Heap 구조를 통해서 정렬을 하는 알고리즘 - 구현이 내림차순일지 오름차순일지에 따라 또, Top-down 인지 Bottom-up 인지에 따라 달라짐 - 여기서는 Top-down 방식의 오름차순을 구현함 정렬 알고리즘 알고리즘을 설명하기 전 주요 알고리즘인 heapify에 대한 설명 - heap 노드를 구성하는 알고리즘 - 부모 노드와 자식 노드 간에 값을 비교해서 큰 값을 찾아 교체 - 만약 교체 했다면 교체된 자식 노드를 부모로 생각..

병합 정렬(Merge Sort)

병합 정렬 - 분할 정복 (divide & conquer) 방법을 이용한 알고리즘 - 퀵 정렬과 유사하나 차이점은 안정 정렬에 속하며 균등분할을 하는 것이 차이가 있음. - 퀵 정렬은 정렬 후 분할한다면, 병합 정렬은 분할 후 합치면서 정렬함. 정렬 방법 1. 배열의 길이가 0 또는 1 일때 까지 분할(divide)함. 2. 더 이상 분할 할 수 없을 때, 병합(merge)을 시작함. 3. 분할한 두개의 배열을 순차적으로 합치는데, 합칠때 두 배열 중에서 작은 값을 찾아서 하나씩 배열에 교체해 나감. (오름차순 기준) 4. 왼쪽 배열 값과 오른쪽 배열의 값을 비교해서 작은 값을 찾아서 원본 배열값에 교체. JAVA Code import java.io.BufferedReader; import java.io..

퀵 정렬(Quick Sort)

퀵 정렬 - 분할 정복(divide and conquer) 방법을 사용함. - 불안정 정렬에 속하며 비교를 통한 정렬인 비교 정렬임. - 매우 빠른 속도를 자랑하지만 최악의 수행속도가 O(n^2)으로 느림. - 합병 정렬과 유사한 방법이기도 하지만 다른 점은 비균등하게 분할하여 conquer 함. (pivot의 인덱스를 기준으로 divide 하기 때문에) 정렬 방법 1. 기준이 될 한 요소를 무작위로 선택, 이를 pivot 이라 함. 2. 왼쪽부터 큰 값을 찾는 커서 1개, 오른쪽부터 작은 값을 찾는 커서 1개 두 개를 생성. (오름차순 기준) 2. pivot 값 보다 큰 값을 왼쪽부터 찾고 pivot 값보다 작은 값을 오른쪽부터 찾음. (오름차순 기준) 3. 만약, 두 위치 모두 값을 찾았다면 두 값을..

Scikit Learn 커스텀 변환기

사이킷 런에는 원하는 기능을 구현하는 변환기를 제작할 수 있다. 이는 BaseEstimator 와 TransformerMixin을 이용하여 제작하게 된다. from sklearn.base import BaseEstimator, TransformerMixin # 열 인덱스 rooms_ix, bedrooms_ix, population_ix, households_ix = 3, 4, 5, 6 class CombinedAttributesAdder(BaseEstimator, TransformerMixin): def __init__(self, add_bedrooms_per_room=True): # *args 또는 **kargs 없음 self.add_bedrooms_per_room = add_bedrooms_per_r..