강몬드의 프로그래밍 이야기

삽입 정렬(Insertion Sort)삽입 정렬은 배열을 정렬된 부분, 정렬되지 않은 부분으로 나눈 후, 정렬 되지 않은 원소를 순차적으로 비교하면서 정렬이 된 부분에 끼워 넣는 방법입니다. 시간 복잡도는 선택 정렬(Selection Sort)와 동일하게 O(N^2)이다. 각 원소에 적당한 위치 찾는 복잡도: 총 원소의 개수 O(N), 순차적으로 삽입 위치를 찾는 복잡도: O(N)이다. 그림여기서는 위 방법을 그림을 통해 설명합니다.삽입 정렬은 정렬 부분(빨간 점선 박스), 정렬 되지 않은 부분(파란 점선 박스)을 나누고 정렬이 된 부분에 순차적으로 원소를 끼워 넣는 방법입니다. 1단계에서는 첫 번째 원소 '19'를 정렬된 부분에 끼워 넣습니다. 2단계에서는 두 번째 원소 '89'를 정렬 부분의 원소와 ..

선택 정렬(Selection Sort)선택 정렬은 매 차례마다 순차적으로 각 인덱스에 해당하는 원소의 값(최소값or 최댓값)을 찾고 해당 인덱스의 원소와 교환해주는 정렬입니다.매 차례마다 남은 원소들을 모두 확인해야 하기 때문에 알고리즘 상 시간 복잡도는 최악의 연산 횟수나 평균 연산 횟수나 O(N^2) 입니다. 그림크기가 5인, 배열을 예로 그림을 통해 설명하겠습니다. 순차적으로 각 인덱스마다(5단계) 해당하는 원소의 값(최소값)을 찾고 해당 인덱스(각 단계)에서 원소를 교환해주는 방법입니다. 1단계에서 첫 번째 인덱스의 값은 '19'를 가리키고, 이후 인덱스에서 최소값 '6'을 찾아서 교환합니다. 2단계에서 두 번째 인덱스는 '89'를 가리키고, 첫 번째 인덱스(이미 정렬이 된)를 제외한 인덱스에서 ..

Network to Classify Digits 이번엔 stochastic gradient descent알고리즘과 MNIST학습 데이터를 사용하여 손글씨 문자를 인식할 수 있는 학습 프로그램을 작성해보자. Python 2.7 version을 사용하여 짧은 프로그램만으로 구현할 수 있다. 코드로만 74줄이다! 먼저 MNIST데이터가 필요하다. 너가 git를 사용한다면 딥러닝 자료들에 대한 코드들을 다음의 명령어로 clone할 수 있다. git clone https://github.com/mnielsen/neural-networks-and-deep-learning. git를 사용하지 않는다면 data와 code를 다음 링크에서 다운 받자. 요오기 이전에 MNIST data에 대해서 설명했을 때, 그것들이 6..

Gradient Descent Learning Algorithm 이제 우리는 신경망을 갖고 어떻게 숫자를 인식하게 학습할 수 있는가? 먼저, 학습을 위한 학습데이터가 필요하다. 우리는 분류 결과값을 갖고 손 글씨로 쓰여진 문자들의 이미지들의 집합인 MNIST 데이터 셋을 이용한다. MNIST의 이름은 NIST(표준 기술 미국 국립 연구소)에 의해 수집 된 데이터 셋 중 일부가 수정됐다하여 MNIST라 붙여졌다. 다음은 MNIST에서 가져온 몇 개의 이미지이다. MNIST 데이터는 두 부분으로 되어 있다. 첫 번째 부분은 60,000개의 이미지 학습 데이터로서 사용되고 이미지는 gray scale이며 28x28크기의 픽셀 값을 갖는다. MNIST 데이터 셋의 두 번째 부분은 10,000개의 이미지 테스트 ..

손 글씨 문자를 분류하는 신경망 문자분류 문제는 두 가지 세부 문제로 나누어서 풀 수 있다. 첫 번째, 우리는 손 글씨들이 작성된 문자들을 각각을 세분화해서 하나의 문자를 포함하는 분리된 이미지를 만들어야한다. 그림 1.5.1은 여러 문자들이 나열된 이미지이다. 그림 1.5.2는 그림 1.5.1의 문자들을 세분화하였다. 인간은 이 세분화 문제를 쉽게 할 수 있지만, 이를 컴퓨터 프로그램이 정확하게 나누기란 어려운 문제다. 세분화 된 이미지를 구했으면 그 다음은 각각의 문자 이미지들을 분류해야 한다. 예를 들어, 위 문자들 중에 첫 번째 문자부터 인식하려고 한다면 프로그램은 ‘5’라고 인지해야 할 것이다. 우리는 두번째 문제, 즉 각각의 숫자를 분류하는 문제를 해결하는 프로그램을 짜는데 집중할 것이다. 왜..