Just Do IT

Selection Sort Selection Sort은 가장 기본적인 정렬 알고리즘 중 하나이다. 알고리즘의 진행 순서는 다음과 같다. 주어진 리스트에서 최소값을 찾는다. 그 값을 맨 앞의 값과 교체한다. 맨 처음위치를 뺀 나머지 리스트에 대하여 반복한다. 그림으로 보는게 가장 이해가 잘 될 것같다. 테이블로 보면 다음과 같다. Round Array Min Value 0 [9,1,6,8,4,3,2,0] 0 1 [0,1,6,8,4,3,2,9] 1 2 [0,1,6,8,4,3,2,9] 2 3 [0,1,2,8,4,3,6,9] 3 4 [0,1,2,3,4,8,6,9] 4 5 [0,1,2,3,4,8,6,9] 6 6 [0,1,2,3,4,6,8,9] 8 시간복잡도 위의 테이블 예시를 보면 n = 8인 array에서 in..

Binary Search Binary Search는 가장 기본적인 탐색 알고리즘 중 하나다. Sorting되어있는 배열의 중간값을 기준으로 크기를 비교하는 과정을 반복하여 search를 진행한다. 만약 77을 찾는다고 하면 가장 먼저 1부터 100 사이의 중간인 middle인 50을 찍는다. 50 77이 되면 87 이후로는 볼 필요가 없기 때문에 버릴 수 있다. 따라서 다음 search에서는 75부터 86 사이의 반을 찍으면 된다. 반복적으로 반을 나눠 (n/2) 들어가기 때문에 $ O(logn) $ 시간에 search가 진..