[알고리즘] 이진탐색
이진탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 전체 범위에서 4를 찾고 싶기 때문에 시작점은 [0], 끝점은 [9]로 설정하며 중간값은 [4]로 설정한다. 0과 9의 중간값은 4.5 이지만 소수점 이하를 제거하여 [4]로 중간값을 설정한 것이다. 중간점 [4]를 기준으로 오른쪽에 있는 값들은 볼필요 없기 때문에 끝점을 중간점의 왼쪽으로 옮긴다. 그후 중간점은 인덱스[1], 즉 숫자 2이며 우리가 찾고자하는 값 4가 아니다. 2보다 우리가 찾고자 하는 값인 4가 더 크기 때문에 중간점을 기준으로 왼쪽에 있는 값들은 볼 필요가 없게 된다. 따라서 이번에는 시작점 위치를 중간점 오른쪽으로 옮긴다. 시작점[2],..
대표적인 정렬의 종류 O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가) 선택 정렬(Selection Sort) 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) O(n log n)의 시간 복잡도 병합 정렬(Merge Sort) 퀵 정렬(Quick Sort) 선택 정렬(Selection Sort) 설명 선택정렬 알고리즘은 정렬되어 있지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞부터 순서대로 정렬해 나아가는 알고리즘이다. 선택정렬은 정렬된 값을 배열의 맨 앞에서부터 하나씩 채워나가게 된다. 따라서 뒤 index로 갈수록 비교범위가 1씩 감소한다는 특성을 갖는다. 입력 배열이 이미 정렬되어 있거나 말거나 상관없이 동일한 연산량을 갖기 떄문에 최적화의..