알고리즘(Algorithm) (45) 썸네일형 리스트형 보간탐색(Interpolation Search) 선형탐색(Linear Search)는 데이터의 원소를 처음부터 끝까지 순차적으로 탐색하면서 검색하는 부르트포트(Brute Force)의 종류이고 이진탐색(Binary Search)은 정렬된 데이터 원소들을 절반씩 나누면서 분할 정복(Divide Conquer)하는 방식이라고 설명했었다. 그럼 보간탐색(Interpolation Search)은 무엇인가? 보간탐색은 이진탐색을 개선한 것인데 이진탐색처럼 비교 대상을 무조건 mid = (high-low)/2 로 하지 않고 우리가 찾는 원소는 전체 데이터 값을 보니 대충 이정도에 있겠구나 추측하여 탐색하는 방식이다. 예를들어 data = [2, 4, 6, 8, 10, 12, 14] 가 있고 이중 12를 찾는다면 이진탐색은 mid = (6 - 0)/2 = 3이 되.. 이진탐색-상/하한선((lower bound,upper bound) 주어진 자료에서 중복되지 않은 값이 주어질 때 그 데이터내에 특정 값이 존재하는지 검색하는 방법 중 이진탐색(Binary Search)은 자료를 정렬한후 분할정복방식으로 데이터를 2/1씩 나누면서 값이 존재하는지 확인하는 알고리즘을 사용했었다. 이진탐색이 데이터내 특정 값을 정확히 찾는 것이라면 lower bound와 upper bound 는 이진탐색 알고리즘에서 약간 변형된 것으로 중복된 자료가 있을때 유용하게 탐색할 수 있는 알고리즘으로 lower bound는 데이터내 특정 K값보다 같거나 큰값이 처음 나오는 위치를 리턴해주고 upper bound 는 K값보다 처음으로 큰 값이 나오는 위치를 리턴해주는 알고리즘이다. △ [출처] http://bajamircea.github.io/coding/cpp/2.. 이진탐색(Binary Search) 선형(순차) 탐색(Linear Search) 은 부르트포스(brute force)의 일종으로 무식하게 처음부터 끝가지 모든 자료를 비교해가면서 원하는 값을 찾는 무식한 방법이라고 하였다. 그래서 찾는것이 앞부분에 있으면 다행히 빨리 찾을수 있지만 뒤에 있다면 worst case 로 탐색하는데 O(N)이 걸린다. 이진탐색(Binary Search) 알고리즘은 선형탐색이 가지고 있는 단점을 보완할 수 있는 알고리즘인데 아무리 자료가 많아도 탐색하는데 O(log N) 이 걸린다. 선형탐색에 비해 성능면에서 엄청 좋은것이다. 그래서 실무에서는 선형탐색보다 이진탐색을 더 많이 사용한다. 대신 조건이 있는데 선형탐색은 자료가 정렬될 필요가 없지만 이진탐색은 내부 알고리즘 로직에 의해 반드시 자료가 정렬되어 있어야만.. 선형(순차) 탐색(Linear Search) 선형(순차) 탐색(Linear Search)은 자료를 탐색하는데 가장 무식하면서 이해하기 쉬운 알고리즘(algoritm) 이다. 선형(순차)탐색은 일종의 부르트포스(Brute Force)의 한 예이기도 한데 왜 무식하냐 하면 특정 자료를 찾기위해서 모든 자료를 뒤져봐야 알기 때문이다. 찾는 것이 일찍나오면 그나마 다행인데 모든 자료 끝까지 뒤질때까지 안나오는 worst case 인경우 성능이 O(N)이다. 위 그림을 보면 더 이해하기 쉬운데 리스트 = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 } 에서 33을 찾기위해 처음부터 마지막 까지 같은 값이 있는지 하나씩 비교해가면서 찾는 것이다. 코드 구현도 매우 간단한데 함수의 확장성을 고려해서 점진적으로 발전시켜 나가겠다. 1.. 선택정렬(Selection Sort) 선택정렬(Selection Sort)은 심플한 정렬 알고리즘이다. 알고리즘이 어떤 식으로 동작하는지 살펴보자. 위와 같이 정렬되지 않은 데이터들이 있고 오름차순(ascending)으로 정렬하는 것을 가정하고 설명하겠다. 모든 데이터들을 순차적으로 비교하여 가장 최소값을 찾는다. (여기는 10이 가장 작은 값이다.) 위에서 찾은 가장 작은 값은 10이다. 10을 첫번째 위치에 있는 (index = 0) 인 14와 교체한다. 맨 왼쪽의 10은 이미 데이터의 모든 원소들 중 가장 작은값이 선택(selection)되어 이동하였으므로 그 다음에는 10을 뺀 나머지 원소들 중 가장 작은 값을 찾는다. 10을 뺀 나머지 원소들 중에서 가장 작은 값은 14이므로 14를 두번째 위치에 있는(index = 1) 인 33과.. 이전 1 ··· 3 4 5 6 다음
