탐색 알고리즘 (선형, 이진)

탐색이란 저장된 정보들 중에 원하는 값을 찾는 것이다.

 

1. 선형 탐색 알고리즘 : 순서대로 하나씩 찾기

[1, 7, 3, 9, 5]

라는 배열이 있을 때 3이라는 값을 찾고 싶으면 1 또는 5부터 차례대로 검사를 해서 3인지를 체크하여 찾는 알고리즘이다.

 

선형 탐색 알고리즘은 배열의 원소들의 갯수만큼 전부 탐색을 하여야 본인이 원하는 정보를 찾을 수 있다. 

물론 위 예시에 있는 값 중에 1이라는 값을 1개 찾을 거야 라고 한다면 왼쪽에서 부터 탐색하면 첫 검사에서 끝날 수 있다.

하지만 시간복잡도는 최악의 상황을 기준으로 설정 된다. 그렇다면 왼쪽부터 탐색을 했는데 1이 맨 뒤에 있다라면 전체 탐색을 하기 때문에 시간 복잡도 O(n) 이다.

 

2. 이진 탐색 알고리즘 : 반씩 제외하면서 찾기 (이분 탐색으로도 불린다)

[1,2,3,4,5,6,7,8,9]

라는 배열이 있을 때 4라는 값을 찾고 싶으면 중앙 (5)를 기준으로 내가 찾고자 하는 값과 비교하여 내가 찾고자 하는 값이 더 작을 때 5 보다 큰 수를 모두 제외하여 반을 제외시키고 다시 1,2,3,4,5에서 중앙 (3)을 기준으로 비교하여 탐색하는 알고리즘이다.

 

여기까지 봤을 때 뭔가 배열에서 이상한 부분이 있을 것이다.

맞다!!! 이진 탐색은 정렬이 되어 있는 상태 일 때 가능한 알고리즘이다. 

반씩 제외 하여 탐색 하기 때문에 시간 복잡도는 O(log n) 이다.

 

*이진 탐색이 효율이 좋은 알고리즘이지만 정렬이 되어 있지 않으면 사용할 수 없다.

 

그렇다면 게임 개발에서는 어떻게 사용 할까?

 

예를 들어 정보들이 Add/Remove가 많이 일어나는 개발을 해야한다라면 

Add/Remove가 일어날 때 정렬을 하면서 실행하면 나중에 찾을 때는 이진탐색으로 빠르게 찾을 수 있지만 Add/Remove가 일어날때마다 정렬을 해줘야하기 때문에 시간 적으로 더 많은 비용을 소모하게 된다.

그래서 Add/Remove 가 많이 일어나는 개발을 하게 되면 Add/Remove는 자유롭게 하며 찾을 때 전체 순회하며 찾으면 될 것이다. 

 

만약 정보들을 Get 하는 상황이 많이 일어나게 되면 반대로 Add/Remove를 할 때 정렬을 해주고, 나중에 Get할 때 효율적으로 시간관리를 할 수 있을 것이다.

Get을 많이 이용하는 상황은 예를 들어 축구게임과 같이 선수들이 이미 저장되어 있고, 새로운 선수가 추가 또는 삭제가 많이 안일어나며, Get을 많이 사용하기 때문에 이진탐색과 같은 알고리즘이 효율적으로 사용될 수 있을 것이다.