CS/알고리즘

[알고리즘] 탐색알고리즘3 - 해쉬탐색(Hash Search)

해시 탐색법 (Hash Search) 앞에서 살펴본 선형 탐새개이나 이진 탐새개법의 전체 조건은 어떤 데이터가 어떤 요소에 들어 있는지 전혀 모르는 상태에서 검색을 시작한다는 것입니다. 그러나 해시 탐색법은 데이터의 내용과 저장한 곳의 요소를 미리 연계해 둠으로써 극히 짧은 시간 안에 탐색할 수 있도록 고안된 알고리즘입니다. 해시 탐색법은 데이터를 데이터와 같은 첨자의 요소에 넣어 두면 한 번에 찾을 수 있지 않을까?라는 아이디어에서 출발합니다. 예를 들어보면 36인 데이터는 첨자 36의 요소에, 48인 데이터는 첨자 48의 요소에 두는 식입니다. 하지만 이렇게 2개의 데이터만 저장해도 49개의 요소를 가진 배열이 있어야 합니다. 공간적으로 굉장히 낭비가 심해집니다. 좀 더 효율적으로 배열을 사용하기 위..

[알고리즘] 탐색알고리즘2 - 이진탐색(Binary Search)

이진 탐색법 (Binary Search) 이진 탐색법은 탐색의 대상인 데이터가 오름차순으로 정렬되어 있는 경우에 데이터를 이분화하면서 특정 값을 탐색하는 알고리즘이다. 가운데에 있는 요소를 먼저 탐색한다. 조건이 가운데 요소보다 정렬순서가 빠른지 느린지를 보고, 탐색범위를 좁힌다. 탐색범위를 좁혔으면 다시 한번 가운데를 탐색해본다. 계속 찾을때까지 반복하여 원하는 결과를 찾으면 탐색 종료. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다. 종료조건 1. 리스트에서 검색할 값과 같은 요소를 발견한 경우 2. 더 이상 검색할 범위가 없어 검색 실패(검색값이 존재하지 않는 경우) function findInde..

[알고리즘] 탐색 알고리즘1 - 선형 탐색(Linear Search)

선형 탐색(Linear Search) 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘이다. 검색이 종료되는 종료 조건 1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우검색할 값과 같은 요소를 발견한 경우 2. 검색할 값과 같은 요소를 발견한 경우 찾는 대상이 앞쪽에 있으면, 짧은 시간에 탐색할 수 있지만, 뒤쪽에 있거나 결과가 없거나 혹은 탐색대상이 많으면 많은 시간이 걸리고 비효율적일 수 있다. 단순하고 이해하기 쉽고, 구현하기 쉽다는 장점이 있지만, 효율은 좋지않다. #include #include us..

[알고리즘] 알고리즘의 복잡도와 Big-O 표기법

어떤 문제를 해결하는데 있어서 나오는 알고리즘은 다양할 수 있다. 간단한 예로 주어진 정수 n의 절대값을 구하라는 문제가 있을 때, 정수 n을 제곱한 뒤, 그 값에 다시 루트를 씌운다. 정수 n이 음수인지 확인하고, 조건이 참이면 그 값에 -1을 곱한다. 이처럼 간단한 문제에서도 다양한 풀이 방법이 존재한다. 다양한 풀이 방법들 중 어느 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산한다. 즉, 복잡도 계산은 가장 빠르게 실행되는 알고리즘을 찾는 방법이라고 볼 수 있다. 알고리즘 복잡도(Complexity) 표현 방식 알고리즘의 복잡도를 표현하는 방식에는 크게 두 가지가 있다. 시간 복잡도 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 쉽게 말해 알고리즘의 실행 속도(성능)을 ..