알고리즘(Algorithm)/검색 & 탐색(Searching) (5) 썸네일형 리스트형 부르트포스(Brute Force) 일반적으로 SW를 개발하면서 결정 문제(decision problem), 탐색 문제(search problem), 카운팅 문제(couting problem), 최적화 문제(optimization problem), 함수형 문제(function problem) 문제등 다양한 문제해결(Problem Solving)이 필요하다. 문제해결을 위해 단순한 자료구조나 알고리즘을 이용하면 되는 경우도 있지만 한개이상의 알고리즘을 복합적으로 사용하여 풀어야 하는 경우도 많이 있다. 부르트포스(Brute Force) 란 위와 같은 다양한 문제해결을 위해 어떤 방식으로 접근할 것인가? 인데 결론 부터 말하면 문제해결을 위해 모든 가능한 경우의 수를 모두 뒤져서 해를 얻는 한마디로 좀 무식한 방법 이다. 대표적으로 어떤 해커.. 보간탐색(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.. 이전 1 다음
