자료구조 - 이진탐색
순차탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 부터 데이터를 하나씩 차례대로 확인하는 방법 - 최적의 시간복잡도 O(1) : 가장 첫번째에 찾고자 하는 데이터가 있는경우 - 최악의 시간복잡도 O(n) : 가장 마지막에 찾고자 하는 데이터가 있는경우 이진탐색 - 찾으려는 데이터와 정렬 된 리스트의 중간지점을 계속해서 재귀적으로 반복하며 비교해서 찾아내는 방법 - 데이터들이 정렬 되어 있어야 한다. - 탐색하고자 하는 범위의 시작점, 끝점, 중간점의 변수를 사용한다. 34의 인덱스를 찾는다고 해보자 1. low ,middle, high = index : 0, 7, 15 설정, index(middle) < 34 이므로 2. low, middle, high = index : 8, 11, 15 ..
자료구조 - 정렬 [선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬]
정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬(Selection sort) : 여러 데이터들중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것 1. 처음에는 정렬되어 있지 않으므로 가장 작은 1을 선택해서 맨앞의 숫자인 5와 swap 2. 맨앞의 1을 제외하고 나머지 숫자들 중에서 가장 작은 2를 선택해서 맨앞의 숫자인 5와 swap 3. 맨앞의 1, 2를 제외하고 나머지 숫자들 중에서 가장 작은 3을 선택해서 맨앞의 숫자인 3과 swap(이미있다.) 4. 맨앞의 1, 2, 3을 제외하고 나머지 숫자들 중에서 가장 작은 5를 선택해서 맨앞의 숫자인 7과 swap 5. 맨앞의 1, 2, 3,..
