탐색 알고리즘 - 선형, 이진 탐색

해당 글에선 1차 배열에서의 주로 쓰이는 탐색 알고리즘을 다룹니다.

탐색 알고리즘은 컴퓨터 과학에서 가장 기초이기도 하면서 필수적인 알고리즘이다.
여기서 탐색한다는 말은 특정한 데이터가 컴퓨터의 메모리 상 어디에 위치해 있는가를 집어내는 행위이다.

어떠한 일련의 데이터(프로그래밍 언어에선 대부분의 경우 배열이라 칭함)의 집합이 있을 때, 그 집합 중 어떠한 값이 어느 번째에 있느냐 위치를 알아낸다는 의미다.

탐색 알고리즘에는 수없이 많은 종류가 있지만 대표적으로는 아래 알고리즘들이 있다.

1. 선형 탐색
2. 이진 탐색
3. 삼진 탐색
4. 해쉬 탐색
5. 점프 탐색
6. 보간 탐색
7. BFS/DFS
8. 등..

다른 알고리즘들은 복잡하고 설명할 것도 많을 것 같아, 선형과 이진 탐색만 다루고 나머지는 다른 글에서 다룰 예정이다.

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

선형 탐색은 말 그대로 어떠한 데이터 집단을 선형적으로 순서대로 탐색하며 원하는 데이터를 찾아내는 것이다.

선형 알고리즘 시나리오

예를 들어 어느 학교의 한 학급 학생들 성적을 정렬없이(하지만 출력번호 기준으로 정렬 했을 때) 데이터베이스에 저장했다고 가정해보자.

학생 수는 총 10명이고 이들의 성적을 담은 배열은 [78, 57, 66, 45, 96, 70, 89, 56, 88, 30]이다.
이러한 상황에서 교장 선생님께서 성적이 90점대인 학생이 누구냐고 물어봤을 때, 담임 선생님은 학생 한 명 한 명의 성적을 확인하면 되지만 화장실 갈 시간도 없을 정도로 바쁜 나머지 미리 짜두었던 탐색을 대신 해주는 프로그램을 사용하려고 한다.

선형 탐색 알고리즘의 원리

선형 탐색은 원리라고 할 것도 없이 너무나도 간단하다.
그냥 특정한 데이터 묶음을 처음부터 끝까지 하나씩 방문하여 특정 조건을 만족하는지 체크하면 된다.
이를 (시나리오가 조금 가미된)코드로 나타내면 아래와 같다.

선형 탐색 알고리즘 코드 (C++)

// studentGrades: an array having students' grades (non ordered)
// scoreRange: a number which indicates the base number
int getStudentBetweenScoreRange(const vector<int>& studentGrades,
                              const int scoreRange) {
	// returning value, -1 will be returned if no student is found
    int studentIndex = -1;
    
    for (int i = 0; i < studentGrades.size(); ++i) {
    	// when studentGrade is between scoreRange and scoreRange + 9
		// it returns the index of the student
        if (scoreRange <= studentGrades[i] &&
            studentGrades[i] < scoreRange + 10) {
            studentIndex = i;
            break;
        }
    }
    
    return studentIndex;
}

int main() {
    const vector<int> studentGrades = {78, 57, 66, 45, 96, 70, 89, 56, 88, 30};
    int scoreRange = 0;
    
    cout << "Please enter the grade you would like to search: ";
    cin >> scoreRange;
    
    const int studentIndex = getStudentBetweenScoreRange(studentGrades, scoreRange);
    
    if (studentIndex >= 0) {
        cout << "A student with grade between " << 
        scoreRange << " and " << scoreRange + 9 << 
        " has been found on " << studentIndex << "th index" << endl;
    } else {
        cout << "Unfortunately, a student with grade between " <<
         scoreRange << " and " << scoreRange + 9 << 
        " has not been found.." << endl;
    }
    
    return 0;
}

해당 프로그램의 코드의 생김새는 위와 비슷할 것이다.
매개변수로 받은 ‘학생들의 성적이 들어있는 배열’을 처음부터 끝까지 차례차례 반복을 돌아주며 조건을 만족하는 성적을 발견하면 해당 성적의 인덱스를 리턴하는 원리이다.

이 전에 예를 들었던 상황에서 교장선생님은 성적이 90점대인 학생을 알고싶어 하셨다. 그래서 담임 선생님은 프로그램을 돌려 90을 입력해 해당 학생이 4번째 학생이구나(출석번호가 5번)라는 것을 알게된다.

그냥 단순하게 선형 탐색 코드를 설명할 수 있었지만 이렇게 하는게 더욱 기억에 잘 남을 것 같아서 해보았다.

선형 탐색의 특징

선형 탐색은 탐색 알고리즘 중에 아주 기본 중에 기본이다. 그래서 효율적이지 못하다. 하지만 선형 탐색이 가지는 몇가지 특성 덕에 유용하게 쓰인다.

1. 데이터가 정렬되어 있지 않을 때 사실상 유일하게 쓸 수 있는 간단하고 효과적인 알고리즘.
2. 데이터의 양이 상대적으로 많이 않을 때 사용하기 유용한 알고리즘.

데이터가 정렬되지 않았을 때

선형 탐색을 제외한 나머지 탐색 알고리즘은 특정한 자료구조를 바탕으로 이미 완벽히 정렬돼 있거나 어느정도 정렬됐다고 판단될 때 사용할 수 있는 방법들이다.

그래서 대부분의 데이터는 애초에 저장할 때 부터 보통 각자가 사용하는 자료구조에 따라 알맞게 자동으로 정렬되는 형식이다. 이렇게 이미 정렬돼있는 상황에선 탐색 시간을 줄이기 위해서 선형 탐색보다 더 복잡한 알고리즘을 사용한다.

하지만 모든 상황에서 데이터가 정렬돼있기를 기대할 순 없다.

데이터가 정렬되기를 기대할 수 없는 상황들

아래 예시들은 예시일 뿐 반드시 그렇다고 할 수 없음

• 게임에서 아이템 데이터 탐색
  • 퀘스트를 완료했을 때 인벤토리에서 제거돼야할 아이템의 ID를 탐색할 때 선형 탐색 사용. (보통 게임 내의 인벤토리는 정렬이 돼있지 않기 때문)
• 서버 로그에서 특정 에러 메세지 탐색
  • 로그는 시간순으로 기록되지만, 에러 발생 위치는 랜덤이기 때문에 선형 탐색 사용.
• 채팅방에서 등장한 특정 단어 탐색
  • 서버 로그와 마찬가지로 채팅은 시간순으로 기록될 수 있지만, 등장하는 단어들은 완전히 랜덤이기 때문에 선형 탐색 사용. 이처럼 정렬돼있지 않은 데이터를 다루는 경우는 생각보다 굉장히 많다.

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

이진 탐색은 어떠한 데이터 그룹을 매번 2배만큼 나누어 탐색하는 방식을 사용한다.
예를 들어 데이터를 20개 가진 배열에서 어떠한 값을 탐색한다고 했을 때, 20개를 처음부터 끝까지 선형적으로 탐색하는 대신 데이터가 있을 법한 범위를 지정하여 탐색한다.
처음엔 20 / 2(10개 범위), 두번째로는 10 / 2(5개 범위), 세번째로는 5 / 2(2개 범위), 그리고 마지막으로 2 / 2(1개 == 결과) 범위만큼 탐색하여 결과를 찾아낸다.

어떻게하면 이렇게 매번 탐색해야하는 범위를 절반으로 줄여가며 시간 복잡도를 줄일까?

이진 탐색 알고리즘의 원리

이진 탐색 알고리즘의 핵심은 바로 범위를 지정하는 것이다.
그런데 컴퓨터가 어떻게 알고 딱 유저가 찾는 데이터의 위치가 특정 범위에 있다는 것을 알 수 있을까? 바로 데이터가 정렬돼있기 때문이다.

아래 예시 이미지를 보면 이해에 도움이 될 거라고 생각한다.
시나리오는 위와 같은 데이터와 상황을 이용하는 것으로 가정했지만 이번엔 이해하기 편하게 하기 위해 찾는 데이터가 90 ~ 99처럼 특정 범위에 있는 것이 아니라 점수가 45점인 학생이 있는지 없는지 판별하는 상황이라고 가정해보자.

이진 탐색은 이미 정렬된 데이터에서만 작동하기 때문에 우선 정렬을 먼저 해줘야 한다. [78, 57, 66, 45, 96, 70, 89, 56, 88, 30]을 정렬하여 다음 배열을 얻을 수 있다.
[30, 45, 56, 57, 66, 70, 78, 88, 89, 96]

정렬된 데이터를 기준으로 이진 탐색을 진행하는 과정을 담은 이미지이다.

1. 데이터의 가운데에 있는 원소의 값과 찾고자 하는 값을 비교한다.
   • 만약 찾고자 하는 값이 더 작다면 범위를 가운데 원소를 기준으로 두고 왼쪽으로 설정한다.
   • 만약 찾고자 하는 값이 더 크다면 범위를 가운데 원소를 기준으로 두고 오른쪽으로 설정한다.
2. 새로 설정한 범위에서 또 가운데 값을 찾고 1번으로 돌아간다.
3. 원하는 원소를 찾을 때까지 1과 2번을 반복한다.
   

이진 탐색은 이러한 과정으로 동작하기 때문에 위의 이미지의 형태를 띈다.

1. 우리의 목표는 45점을 가진 학생이 한 학급에 있는지 없는지 판단하는 것이다. 그렇기 때문에 찾고자 하는 값은 45이다.
2. 데이터의 가운데에 있는 값이 66이니까 45와 66을 비교한다.
   • 45가 66보다 작으니 범위를 절반의 왼쪽으로(첫번째 원소부터 66 원소까지) 축소한다.
3. 새로 정한 범위에서 가운데 값과(56) 찾고자하는 값을(45) 비교한다.
   • 45가 56보다 작기 때문에 또 범위를 절반의 왼쪽으로(첫번째 원소부터 56까지) 축소한다.
4. 새로 정한 범위에서 가운데 값과(45) 찾고자하는 값을(45) 비교한다.
   • 값이 서로 같으니 해당 데이터에는 45점을 가진 학생이 존재한다는 의미가 된다.

이런 방식으로 매번 탐색하는 범위를 절반으로 줄여나가면서 진행하기 때문에 선형 탐색의 시간 복잡도인 O(N)을 거뜬히 뛰어넘는(훨씬 더 적은 연산을 한다는 의미에서) O(log N) 복잡도를 가진다.

이진 탐색 알고리즘 코드 (C++)

bool getStudentBetweenScoreRange(const vector<int>& studentGrades,
                              const int score) {
    bool doesStudentExist = false;
    int left = 0, right = studentGrades.size() - 1;
    
    while (left <= right) {
        const int mid = (left + right) / 2;
        
        if (studentGrades[mid] < score) { left = mid + 1; }
        else if (studentGrades[mid] > score) { right = mid - 1; }
        else { doesStudentExist = true; break; }
    }
    
    return doesStudentExist;
}

위 방식을 코드로 작성하면 이러하다.
이번엔 main() 함수가 좀 이해에 방해가 될 것 같아 완전히 이진 탐색 코드에 집중을 쏟아보자.

여기서 가장 중요한 변수는 left, right, 그리고 mid이다.

• left: 항상 right보다 왼쪽에 위치하는 인덱스용 변수
• right: 항상 left보다 오른쪽에 위치하는 인덱스용 변수
• mid: left와 right의 범위에서 가운데 인덱스 left와 right은 탐색할 ‘범위’를 나타내는 변수이기 때문에 가장 처음에는 각각 0과 데이터의 마지막 원소 위치로 초기화한다.
  

그리고 left가 right보다 작거나 같을 때까지 while문 내부의 코드를 반복한다.

• mid를 (left + right) / 2로 설정하여 항상 특정한 범위의 가운데 원소를 가리키도록 한다.
• if문을 통해 left, right을 적절히 옮겨준다.
  • 찾고 있는 원소보다 mid가 더 작다면 찾고있는 원소는 가운데 값보다 오른쪽에 위치한다는 의미이기 때문에 left를 mid + 1로 설정한다.
  • 찾고 있는 원소보다 mid가 더 크다면 찾고있는 원소는 가운데 값보다 왼쪽에 위치한다는 의미이기 때문에 right을 mid - 1로 설정한다.
  • 찾고 있는 원소와 mid에 있는 원소가 서로 같다면 해당 원소를 찾았다는 의미이므로 탐색을 끝낸다.

mid 값을 구하는 다른 방법

위 코드에선 mid = (left + right) / 2로 하고 있지만 이 방법은 overflow 에러를 발생시킬 수 있는 위험이 있다.
그래서 일반적으로 쓰이는 방법은 mid = left + (right - left) / 2이다. 왜 이 두 수식이 같은지 직관적으로 이해가 가지 않을 거지만 아래 시각적 설명을 보면 도움이 될 것이다.

$$\text{left}+\frac{(\text{right}-\text{left})}{2}=\frac{\text{left}+\text{right}}{2}$$

(left + right) / 2과 left + (right - left) / 2를 수학적으로 적어보았다. 여기서 우선 좌변에만 집중해보자.

$$\text{left}+\frac{\text{right}}{2}-\frac{\text{left}}{2}$$

좌변에 있는 나누기 2를 펼쳐보면 위 수식과 같아진다.

$$(\text{left}-\frac{\text{left}}{2})+\frac{\text{right}}{2}$$

left끼리 붙여보고 이를 계산해보면 다음을 얻는다.

$$\frac{\text{left}}{2}+\frac{\text{right}}{2}$$

이 수식을 다시 합쳐보면 아래와 같은 모양이 된다.

$$\frac{\text{left}+\text{right}}{2}$$

최종적으로 우리는 두 수식이 정확하게 같은 수식이라는 것을 알 수 있게 된다.

왜 굳이 이렇게 해야할까?
위에도 언급했지만 overflow 발생 위험 때문이다.
만약 데이터의 크기가 int로 나타낼 수 있는 값과 아주 가까울 경우 (right + left)을 시행할 때 int가 나타낼 수 있는 범위를 초과할 수 있는 가능성이 높다는 것이다.
물론 left, right을 int가 아닌 long long으로 표현하고 웬만한 크기에는 신경을 끄는 것도 방법이겠지만 프로그래밍에선 최대한 발생할 수 있는 에러, 버그들은 사전에 방지하는게 강력하게 권장되기 때문에 이 방법이 많이 쓰인다.

이진 탐색의 특징

예시로 보았듯 이진 탐색은 매번 탐색을 할 때마다 탐색할 범위를 절반씩 줄여나가기 때문에 상당히 커다란 데이터에도 빠르게 탐색을 수행할 수 있다는 특징이 있다.
만일 데이터가 100만개라고 할 때 선형 탐색은 최악의 상황에서 100만번의 연산을 하지만 이진 탐색으로는 약 20번의 연산으로 탐색을 끝낼 수 있다. 실로 어마어마한 차이라고 볼 수 있다.

하지만 이미 언급됐듯이, 데이터가 정렬돼있는 상황에서만 사용할 수 있다.
컴퓨터 입장에선 탐색보다는 정렬이 훨씬 복잡하다. 탐색은 아주 빠른 시간내에 성취할 수 있는 반면 탐색하기 전에 정렬을 해주거나 데이터를 넣을 때마다 자동으로 정렬되는 알고리즘을 넣어줘야 하기 때문에 선형 탐색과 이진 탐색의 장단점이 분명히 존재한다.