전체 글

선택, 삽입, 퀵 정렬에 이어서 마지막으로 계수 정렬에 대해 공부해 보자. 계수 정렬(Count Sort) 계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작한다. 계수 정렬은 모든 데이터가 양의 정수일 때 데이터의 개수가 N개, 데이터 중 최댓값이 K일 때, 최악의 경우에도 O(N+K)의 수행 시간을 보장한다. 하지만 한 가지 조건이 붙는데, 바로 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬이 이러한 특징을 가지는 이유는 계수 정렬을 이용할 때 모든 범위를 담을 수 있는 크기의 배열..

퀵 정렬은 삽입 정렬과 선택 정렬에 비해 훨씬 빠른 정렬 알고리즘이고 많이 사용되는 알고리즘이다. 병합 정렬과 함께 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 된다. 퀵 정렬 (Quick Sort) 기본 컨셉은 아래와 같다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식을 반복한다. 원리만 이해해도 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 등 다른 고급 정렬 기법에 비해 쉽게 소스코드를 작성할 수 있다. 퀵 정렬에서는 큰 숫자와 작은 숫자를 교환할 때의 기준을 정하는데 이를 피벗(Pivot)이라고 한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 ..

선택 정렬은 매번 가장 작은 것을 선택해서 정렬했다. 선택 정렬은 알고리즘 문제 풀이에 사용하기에는 시간이 매우 오래 걸리기 때문에 다른 접근법이 필요할 듯하다. 삽입 정렬(Insertion Sort) 삽입 정렬은 데이터를 하나씩 확인하여 각 데이터를 적절한 위치에 삽입하는 식으로 정렬을 진행한다. 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 혹은 완전히 정렬되어있을 때는 매우 효율적이다. 반면에 선택 정렬은 데이터가 완전히 정렬되어있어도 시간 복잡도가 같다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는..

가장 기본적인 정렬 방법 중 하나인 선택 정렬에 대해서 알아보자. 선택 정렬 (Selection sort) 기본적인 컨셉은 전체 데이터에서 가장 작은 값을 맨 왼쪽에 넣고, 그다음엔 두 번째로 작은 값을 왼쪽에서 두 번째에 넣는 방식이다. 이런 식으로 반복해주면 점점 정렬이 될 것이고 마지막 데이터는 가만히 두어도 정렬된 상태일 것이다. 위의 그림에서는 총 7개의 데이터를 7-1번만큼 반복해서 정렬을 하였다. 데이터가 N개이면 반복 횟수는 N-1번일 것이다. ##메인 함수 부분## if __name__ == "__main__": array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i for j in range(i+1, len(arr..

파이썬으로 시험을 보기 전에 기본 문법은 확실히 정리하고 보자. round() IEEE754 표준에서는 실수형을 저장하기 위해 4바이트, 8바이트라는 고정된 크기의 메모리를 할당하기 때문에 현대 컴퓨터 시스템은 대체로 실수 정보를 표현하는 정확도에 한계를 가진다. 파이썬에서도 0.3 + 0.6을 출력해보면 0.89999999999999가 출력된다. round() 함수는 소수점 특정 자릿수에서 반올림을 해준다. 코테에서는 흔히 소수점 다섯 번째 자리에서 반올림한 결과가 같으면 정답으로 인정하는 식이다. round() 함수는 두 번째 인자로 (반올림하고자 하는 위치 - 1)을 넘겨줘야 한다. a = 0.3 + 0.6 print(round(a,4)) 리스트 자료형 리스트 관련 메서드 insert() 함수와 r..

이전 글에서 KMeans 클래스를 이용하여 각 과일들을 클러스터링 했다. 또한 최적의 K를 찾는 법을 클러스터 중심과 클러스터에 속한 샘플 사이의 거리인 이너셔의 변화를 통해 찾아냈다. 그렇게 업로드된 사진을 클러스터로 분류하여 폴더별로 저장했지만, 너무 많은 사진이 등록되어 저장 공간이 부족하다. 사진의 용량을 줄이는 법은 없을까? 차원과 차원 축소 지금까지 데이터가 가진 속성을 특성이라고 했다. 과일 사진에는 가로 100, 세로 100으로 총 10,000개의 픽셀이 있기 때문에 10,000개의 특성이 있다고 할 수 있다. 머신러닝에서는 이런 특성을 차원(dimenstion)이라고도 부른다. 그렇다면 10,000개의 특성은 10,000개의 차원이라고 할 수 있다. 이 차원을 줄일 수 있다면 저장 공간을..

이전 글에서는 사과, 파인애플, 바나나에 있는 각 픽셀의 평균값을 구해서 분류를 했다. 그 사진이 어떤 과일인지 미리 알고 있었기 때문에 각 과일의 평균을 구할 수 있었다. 비지도 학습에서는 사진이 어떤 과일인지 알지 못하는데 이런 경우에는 어떻게 평균값을 구할 수 있을까? K-평균 알고리즘 K-평균 알고리즘의 작동 방식은 다음과 같다. 무작위로 k개의 클러스터 중심을 정한다. 각 샘플에서 가장 가까운 클러스터 중심을 찾아 해당 클러스터의 샘플로 지정한다. 클러스터에 속한 샘플의 평균값으로 클러스터 중심을 변경한다. 클러스터 중심에 변화가 없을 때까지 2번으로 돌아가 반복한다. 이런식으로 거리를 이용해서 중심을 갱신하면서 군집을 형성한다. KMeans 데이터를 불러오자. (샘플 개수, 너비, 높이)로 이..

이전까지 타깃 데이터를 사용하는 지도 학습에 대해 공부했다. 이번 글에서는 타깃이 없는 데이터를 사용하는 비지도 학습과 대표적인 알고리즘을 공부해보자. 과일을 종류별로 분류하는 문제를 생각해보자. 하나하나 사람이 분류할 수도 없고, 생선처럼 미리 과일 분류기를 훈련하기에는 어떤 과일 사진이 들어올지 알 수 없기 때문에 곤란하다. 사진에 대한 정답(타깃)을 모르는데 어떻게 종류대로 분류할 수 있을까? 비지도 학습 (Unsupervised Learning) 비지도 학습은 타깃이 없을 때 사용하는 머신 러닝 알고리즘이다. 우리가 가르쳐주지 않아도 데이터에있는 무언가를 학습하는 것이다. 위에서 예시로 들었던 과일을 종류별로 분류하는 문제를 연습해보자. 이전에는 csv데이터를 불러와서 모델을 만들었지만 이번에는 ..