[Algorithm]기본 탐색 알고리즘

이 글은 이전에 운영하던 깃 블로그에서 옮겨온 글입니다.

 

서론

지난 글 [Algorithm] 기본 정렬 알고리즘에 이어, 역시나 코딩 테스트 문제의 단골인 기본 탐색 알고리즘에 대해 다뤄보려 합니다. 정렬은 데이터를 '정리'하는 게 중심이었다면, 탐색은 데이터를 '검색'하는 게 중심이 되겠네요. 단골 문제이다 보니 예시 코드는 좋은 것들이 많이 돌아다녀 이번 글에서 코드는 굳이 포함하지 않겠습니다.(설명이 길어 글 길이가 길어진 이유도 있습니다.)

 

---

선형 탐색

가장 기본적이고 쉬운 탐색 알고리즘이 아닐까 생각합니다. 순서대로 쭉… 찾는 거니까...

• 다른 이름으로 순차 탐색이라고도 함
• 데이터의 집합(배열, 리스트)등의 처음부터 끝까지 순서대로 비교하며 탐색하는 방식
• 데이터의 양이 늘어나면 수행 시간이 기하급수적으로 늘어남
• 구현이 가장 간단하지만 가장 비효율적
• 시간 복잡도 : O(n)

---

이진 탐색

• 이분 검색이라고도 함, 반씩 나누어 검색하는 방식
• 중간값부터 탐색을 하며 트리 구조에서 자주 쓰이는 방식
• 반드시 정렬되어 있어야 한다는 전제조건이 있음
• 시간 복잡도 : O(logN)

---

너비 우선 탐색(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으로 초기화
  • 현재 노드에서 연결된 노드들을 우선순위 큐에 넣음
  • 우선순위 큐이므로 최단거리순으로 정렬
  • 현재 노드와 연결된 노드들 사이의 최단거리를 찾아서 거리 배열과 경로 배열을 채움
  • 모든 노드를 방문할 때까지 반복(우선순위 큐 부분)