[알고리즘] 탐색 알고리즘 (선형, 이분, 해시, BST)

탐색문제?

저장된 데이터들 중에 원하는 값을 찾는 문제이다.

 

1. 선형 탐색 알고리즘 (Linear Search Algorithm)

• 맨 앞이나, 맨 뒤부터 순서대로 하나하나 찾아보는 알고리즘이다.

• 가장 단순하고 간단한 탐색 알고리즘이다.

1. 맨 끝부터 하나하나 원하는 값을 찾아본다.
2. 원하는 값을 찾으면, 탐색을 종료한다.

예시

5를 찾을 때, 맨 왼쪽에 있는 1부터 시작해서 하나씩 탐색한다.

시간 복잡도

길이 n짜리의 리스트를 탐색할 때,

최선의 경우

• 리스트의 첫 번째 원소가 정답인 경우 : 1번

최악의 경우

• 리스트의 맨 마지막 원소가 정답이거나, 리스트에 정답이 없을 때 : n번

따라서 O(n)의 시간복잡도를 가진다.

2. 이진 탐색 알고리즘 (Binary Search Algorithm)

중간지점을 기준으로 데이터를 반씩 나눠서 탐색하는 알고리즘이다.

1. 중간지점을 선택한 뒤, 중간지점을 기준으로 왼쪽 혹은 오른쪽 부분만 남긴다.
2. 남긴 부분 중에서 다시 중간지점을 선택한 뒤, 왼쪽 혹은 오른쪽만 남긴다.
3. 위 과정을 원하는 값을 찾을 때 까지 반복한다

예시

5를 찾을 때,

시간 복잡도

최선의 경우

• 리스트의 중간부분이 정답일 때 : 1번

최악의 경우

• 리스트에 정답이 없는 경우 : log2(n) 번

따라서 O(logn)의 시간 복잡도를 가진다

선형탐색은 n이 증가함에 따라 시간복잡도가 선형적으로 증가하지만, 이진탐색은 n이 증가해도 시간복잡도가 아주 천천히 증가한다.

보통 정렬된 리스트에는 이진탐색을 사용하고,

정렬되지 않은 리스트에는 선형탐색을 사용한다.

3. 해시 탐색 알고리즘 (Hash Search Algorithm)

선형탐색이나 이진탐색은, 어떤 값이 어떤 index에 들어있는지에 대한 정보가 없는 상태에서 탐색할 때 사용하는 방식이었다.

반면에 해시 탐색은 값과 index를 미리 연결해 둠으로써 짧은 시간에 탐색할 수 있는 알고리즘이다.

함수를 사용하여 데이터를 보관한 후에

보관하는데 사용된 함수를 사용하여 한 번에 데이터를 탐색한다.

아이디어

• 1차 아이디어

  • 처음에는 데이터와 같은 index에 저장했다

    ex) 데이터 24는 24번 index에 저장

    데이터 30은 30번 index에 저장

    • 낭비다 !!
  • 최소한 데이터의 종류 만큼의 index 필요

• 2차 아이디어

  • 데이터에 함수(일정 계산)을 적용하여 나온 값을 index로 하여 보관하는 방법.

    ex) data MOD 10 에 저장하는 방식을 이용하면,

    0~9 까지의 10개의 index를 사용하여 값을 저장할 수 있다.

  • 해시 함수

    • 어떤 값이 주어졌을 때, 그 값을 대표하는 값을 계산하는 함수

  • 해시 값

    • 해시 함수의 계산으로 나온 값

알고리즘

해시 탐색을 위해서는 총 두개의 알고리즘이 필요하다

• 데이터를 저장하는 알고리즘
• 데이터를 검색하는 알고리즘

해시함수로는 나누기 연산, 나머지 연산 등 다양한 연산을 이용할 수 있다.

해시 함수로 데이터를 저장하는 알고리즘

• 배열 2개를 준비한다
  • 주어진 값들을 해시함수를 이용하여 별도의 배열에 다시 저장하기 때문
  • 다른 탐색 알고리즘에서는 배열 크기를 데이터 수 만큼만 준비하면 충분하지만, 해시 탐색법은 데이터 수의 1.5~2배의 크기의 배열을 준비해야 한다.

ex) 데이터가 10개이면, 데이터를 15으로 나눈 나머지를 해시값으로 설정한다.

만약, 같은 해시값을 가진 데이터가 있다면 (충돌이 일어난다면) 비어있는 옆 칸에 보관한다.

해시 함수로 데이터를 검색하는 알고리즘

• 저장할 때 사용한 것과 같은 해시 함수를 사용
• 원하는 데이터가 존재하지 않을 경우에 어떻게 처리할 것인지 정해야 한다

장점

데이터를 저장하거나, 탐색하고자 하는 위치를 즉시! 참조할 수 있기 때문에 빠른 속도로 처리가 가능하다.

4. 이진 탐색 트리 (BST / Binary Search Tree)

트리 자료구조를 이용한 탐색 트리이다.

정의

• 왼쪽 서브트리의 키값들은 root의 키값보다 작다
• 오른쪽 서브트리의 키값들은 root의 키값보다 크다
• 왼쪽, 오른쪽 서브트리들은 각각 모두 BST정의를 만족한다
• BST의 모든 node들의 키값은 unique하다.
• 위의 4가지를 모두 만족해야 한다.

탐색 알고리즘

어떠한 BST에서 원하는 값을 찾고자할 때,

root값을 기준으로

• 원하는 값 > root 키 값 : 오른쪽 서브트리로 이동
• 원하는 값 < root 키 값 : 왼쪽 서브트리로 이동
• 원하는 값 = root 키 값 : 탐색 종료

이 것을 계속 반복해나가면 된다.

삽입 알고리즘

어떠한 값을 삽입하고자 할 때,

1. 위의 탐색알고리즘을 먼저 수행한다.
2. 탐색 실패시에 , 탐색이 종료된 위치에 해당 노드를 삽입한다.
3. 탐색 성공시에, 이미 저장되있는 키값이므로 삽입에 실패한다.

삭제 알고리즘

어떠한 값을 삭제하고자 할 때,

1. 위의 탐색 알고리즘을 먼저 수행한다.

2. 삭제하려는 노드의 차수에 따라

   • 차수 : 0 (leaf node)

     그냥 삭제한다

   • 차수 : 1 (한 개의 자식 존재)

     삭제하고 자식을 삭제한 자리에 붙인다

   • 차수 : 2

     자신을 대체할 노드를 찾아야 한다.

     삭제할 노드의

     ​ 왼쪽 서브트리에서 가장 큰 값

     ​ 오른쪽 서브트리에서 가장 작은 값

     을 자신을 대체할 노드로 정한다.

참고 자료

http://kocw.xcache.kinxcdn.com/KOCW/document/2018/wonkwang/leesangwon0409/11.pdf

http://kocw.xcache.kinxcdn.com/KOCW/document/2018/wonkwang/leesangwon0409/11.pdf

https://m.blog.naver.com/PostView.nhn?blogId=4717010&logNo=60209820587&proxyReferer=https:%2F%2Fwww.google.com%2F

자료구조(Data structure) - 이진 탐색 트리(Binary Search Tree,BST)의 탐색/삽입/삭제연산