탐색 알고리즘
지난번에 정렬 알고리즘을 포스팅했었는데, 이번에는 탐색 알고리즘에 대해 포스팅을 해보려 한다.
선형탐색
가장 기본적이고 쉬운 탐색 알고리즘이 아닐까 생각한다. 순서대로 쭉… 찾는거니까
- 다른 이름으로 순차 탐색이라고도 함
- 데이터의 집합(배열, 리스트)등의 처음부터 끝까지 순서대로 비교하며 탐색하는 방식
- 데이터의 양이 늘어나면 수행시간이 기하 급수적으로 늘어남
- 구현이 가장 간단하지만 가장 비효율적임
- 시간 복잡도 : O(n)
이진탐색
- 이분 검색이라고도 함, 반씩 나누어 검색하는 방식
- 중간값부터 탐색을 하며 트리 구조에서 자주 쓰이는 방식
- 반드시 정렬되어 있어야 한다는 전제조건이 있다
- 시간 복잡도 : O(logN)
- 코드 예시
template < typename T > long BinarySearch(const vector
& vec, long start, long end, const T& key) { if(start > end) return -1; long mid = start + (end-start)/2; if(vec[mid] == key) return mid; if(vec[mid] > key) return BinarySearch(vec, start, mid-1, key); return BinarySearch(vec, mid+1, end, key); }
너비우선 탐색(BFS)
- 인접한 노드들을 차례로 방문하는 방식의 탐색
- 그래피 기반의 탐색, 시작부터 height가 작은 노드부터 차례로 방문하여 전체 탐색
- 일반적으로 queue를 이용하여 구현
- 구현 방식
- queue에 시작점을 push
- queue의 가장 앞에 있는 노드 pop
- 현재 노드에 인접한 모든 노드들 중 아직 방문하지 않은 노드들을 queue에 push
- queue가 텅빈 상태일때 까지 반복
- 코드예시(슈도코드)
깊이우선 탐색(DFS)
- 더 이상 나아갈 깊이가 없을때까지 들어가서 탐색하며 더 이상 깊어질 깊이가 없다면 이전의 위치로 돌아와 다른 루트로 탐색을 진행한다
- 주로 트리와 그래프 탐색에 이용됨
- 주로 stack을 이용하여 구현
- 구현 방식
- 시작 정점을 결정하여 방문
- 정점에 인접한 정점중에서 방문하지 않은 정점을 스택에 push하고 방문
- 방문하지 않은 정점이 없으면 탐색방향을 바꾸기 위해 스택을 pop
- 스택의 가장 위쪽 정점을 새로운 기준으로 push, pop 반복
- 스택이 공백이 될때까지 반복한다
- 코드예시(슈도코드)
해시테이블
이전에 map 컨테이너와 같이 이야기한적이 있는거 같다. 다시한번 좀더 자세히 정리해본다.
- 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것
- 탐색, 삽입, 삭제 성능 : 최악 O(n) ~ 평균 O(1)
- 해시 함수
- 문자열을 받아서 숫자를 반환하는 함수
- 문자열에 대해 숫자를 맵핑(할당) 한다
- 일관성을 유지해야함
- 다른 단어가 들어간다면 꼭 다른 숫자가 나와야 한다
- 해시 테이블의 장점
- 어떤 것과 다른 것 사이의 관계를 모형화할 수 있다
- 중복을 막을 수 있다
- 서버에게 작업을 시키지 않고 자료를 캐싱할 수 있다
- 서로 다른 입력값에 대하여 동일한 해시 값을 반환하는 충돌현상이 있을 수 있다
- 해시 함수의 충돌
- 사용률이 낮을때는 해시테이블이 가장 느린 경우도 있다
- 사용률 = 해시 테이블에 있는 항목 수 / 해시 테이블에 있는 공간의 수
- 값들이 뭉쳐져 있을경우에는 충돌이 일어날 확률이 높다(클러스터)
- 좋은 해시 함수는 값들을 골고루 분산시키는 해시 함수이다
- 예시 코드
A* 알고리즘
- 휴리스틱 추정값을 사용하여 최소가 되는 지점을 우선 탐색 (우선 순위 큐)
- 휴리스틱 추정값 : f(x) = h(x) + g(x)
- h(x) : 출발 노드 n으로부터 도착 노드 n까지의 경로 가중치
- G(x) : 노드 n으로부터 목표 노드까지의 추정 경로 가중치(도착 노드까지의 예상 이동비용)
- Open / Closed 리스트
- Open : 검색 가능성이 있는 노드의 집합, 아직 조사하지 않은 노드
- Closed : 이미 검색이 끝난 지점들의 집합
- 탐색 우선 순위는 Open 리스트 내의 f(x) 가중치 값이 가장 작은 노드부터 탐색
- 작동 원리
- 시작 노드의 주변 노드를 Open리스트에 집어 넣는다
- 반복 과정
- Open리스트에서 f값이 가장 낮은 노드를 현재 노드로 지정
- 현재 노드는 Open리스트에서 제거하고 Closed리스트에 넣는다
- 현재 노드의 주변 노드에 대하여 판단
- 주변 노드중 갈수 없거나 이미 Closed리스트에 있다면 무시
- 위 경우가 아니고 Open리스트에 없다면 Open리스트에 추가
- 이 노드의 부모노드는 주변노드의 중심 노드(현재 노드)이다
- 만약 이 노드가 이미 Open리스트에 있다면 G비용을 이용하여 가장 작은지 판단
- G비용이 더 작다면 부모노드는 이 노드이다
- 위 과정을 목표노드를 찾을때까지(목표 노드를 Open리스트에 넣은 순간)나 Open리스트가 텅빌때까지 실행
- 목표 노드로부터 부모노드를 거슬러 올라가면 최단 경로가 된다
다익스트라
- 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
- 최단거리는 최단거리로 이루어져 있다(그리디 알고리즘)
- 간선들은 모두 양의 간선들을 가져야 한다
- 첫 정점을 기준으로 연결되어있는 정점들을 추가해가면서 최단 거리를 갱신하는 것
- 정점을 잇기 전까지는 시작점을 제외한 정점들은 모두 무한대 값을 가짐
- 우선순위 큐 사용
- 최소거리 값 갱신 횟수의 증가 때문에 사용
- 속도에 이점이 있다
- 우선순위 큐 사용
- 작동 구조 * 거리 배열을 음의 값으로 초기화, 시작점만 0으로 초기화(음의 값인 경우 아직 계산 안한 노드)
- 경로 배열을 음의 값으로 치기화, 시작점만 0으로 초기화
- 현재 노드에서 연결된 노드들을 우선순위 큐에 넣는다
- 우선순위 큐이므로 최단거리순으로 정렬 된다
- 현재 노드와 연결된 노드들 사이의 최단거리를 찾아서 거리배열과 경로배열을 채운다
- 모든 노드를 방문할 때 까지 반복(우선순위 큐 부분)