![]()
배경 예를 들어 배열 x의 원소 수가 13이고, 그 안에 오름차순으로 정렬된 10개의 데이터가 저장되어 있다고 가정해보겠습니다. [5, 6, 14, 20, 29, 34, 37, 51, 69, 75] 이 배열에서 35를 추가한다면 과정은 다음과 같습니다. ① x[5], x[6] 사이에 값이 추가되도록 이진 검색법으로 검사 ② x[6] 이후의 모든 원소를 한 칸씩 뒤로 이동 ③ x[6]에 35 대입 원소가 이동하는데 필요한 복잡도는 O(n)이고, 비효율적입니다. 해시법 해시법은 해시값을 통해 추가·삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행하는 알고리즘입니다. 해시값은 배열의 원소들을 총 원소 개수로 나눈 나머지입니다. 이 해시값은 데이터에 접근할 때 기준이 됩니다. 위 예시라면 배열 x의 ..
이진 검색 배열의 데이터가 정렬 되었을 때 배열의 첫번째 원소부터 하나씩 스캔하는 선형 검색보다 빠르게 검색할 수 있는 알고리즘입니다. 즉, 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있습니다. n개의 원소가 오름차순으로 정렬된 배열 seq에서 이진 검색하는 알고리즘은 검색 범위의 맨 앞(pl), 맨 끝(pr), 중앙의 인덱스(pc)를 활용하여 검색합니다. 검색할 키 값이 정렬된 배열의 중앙 값을 기준으로 앞 혹은 뒤인지를 반복문 안에서 인덱스 변수 값을 갱신해나가며 키 값을 찾을 때까지 검색해나가는 것입니다. 예를 들어 seq = [5, 7, 10, 12, 14, 16, 20] 배열에서 이진 검색 알고리즘을 토대로 키 값 16을 검색하겠습니다. 이때 pl = 0, pr..
검색 알고리즘 검색은 어떤 조건을 만족하는 데이터를 찾아내는 과정입니다. 알고리즘에는 배열 검색, 연결 리스트 검색, 이진 검색 트리 검색 등 다양한 검색 알고리즘이 있습니다. 선택할 수 있는 알고리즘은 다양하지만, 단순히 계산 시간이 빠르다고 해서 좋은 알고리즘은 아닙니다. 검색 처리 시간뿐만 아니라 데이터의 추가·삭제 등 이외 작업들에 대한 비용을 종합 평가하여 적절한 알고리즘을 선택해야합니다. 하여 이번 포스팅에서는 구체적으로 다음 세 가지 배열 검색 알고리즘 중 선형 검색 알고리즘에 대해 공부하고자 합니다. ① 선형 검색: 무작위로 늘어놓은(원소의 값이 정렬되지 않은) 데이터 집합에서 검색을 수행 ② 이진 검색: 일정한 규칙으로 늘어놓은(원소의 값이 정렬된) 데이터 집합에서 아주 빠른 검색 수행 ..
