[SW 정글 11일차] 검색 알고리즘

오늘은 2주차 시작으로 검색 알고리즘에 대해 공부를 시작했다.

검색 알고리즘에 대해 거의 모르다시피 살고 코딩테스트에서는 in 을 써서 값이 배열 안에 있는지 없는지 확인만 하는 수준이였다.

오늘부로 검색 알고리즘 개념을 잡고자 한다.

 

 

1. 선형 검색 (linear search)

선형 검색은 배열에서 원소를 검색하는 방법 중 가장 기본적인 알고리즘이다.

원하는 값을 찾기 위해 배열의 맨 앞부터 순서대로 확인하며 검색하는 것이다.

어떠한 방식으로 검색이 이루어지는지 아래의 그림을 보며 이해해보자.

배열의 맨 앞부터 순서대로 3인지를 확인하고 아니면 다음 원소로 넘어가면서 3인 원소를 찾았을 때 검색을 멈추게 된다.

선형 검색의 종료 조건은 2가지가 존재한다.

- 찾고자하는 값을 찾지 못하고 배열의 맨 끝을 지난 경우

- 검색할 값과 같은 원소를 찾은 경우

 

그러면 선형 검색 알고리즘을 직접 구현해보자.

# while문을 사용한 경우
def seq_search(arr, key):
    i = 0
    
    while True:
        if i == len(arr):
            return -1
        if a[i] == key:
            return i
        
        i += 1


#for문을 사용한 경우
def seq_search(arr, key):
    for i in range(len(arr)):
        if a[i] == key:
            return i
    return -1

코드를 보면 for문과 while문으로 반복문을 통해 선형 검색이 가능하다.

맨 앞부터 순서대로 검색을 하면서 원하는 key에 해당하는 원소를 찾으면 해당 인덱스를 반환한다.

만약, 원하는 key가 배열에 없다면 -1을 반환해준다.

 

선형 탐색은 위에서 언급했듯이 반복할 때 마다 2가지의 종료조건을 고려해야하므로 과정을 계속 반복하다보면 종료 조건을 검사하는 비용을 무시할 수 없게된다.

이러한 문제점을 해결하기 위해 기존의 선형 검색에 보초(sentinel)을 추가하여 비용을 반으로 줄일 수 있다.

원리는 간단하다.

그냥 기존의 배열의 맨 뒤에 찾고자 하는 key값을 추가해주는 것이다.

먼저 구현 코드를 보고 설명을 해보려고 한다.

import copy

def seq_search(seq, key):
    arr = copy.deepcopy(seq)
    arr.append(key)
    
    i = 0
    while True:
        if a[i] == key:
            break
        i += 1
   
   return -1 if i == len(seq) else i

기존의 선형 검색은 while문이나 for문이나 배열을 끝까지 돌았는지에 대한 체크를 반복적으로 해줬다.

하지만, 보초법을 사용한 선형 검색은 일단은 계속해서 반복문을 돌 것이고 배열의 맨 뒤에 key와 똑같은 값을 가진 보초를 세워뒀기 때문에 언젠가는 멈출 것이다.

멈춘 후에는 해당 인덱스 값이 추가한 보초를 가리키면 -1을 반환해주고 아니면 해당 인덱스를 반환해주는 것이다.

종료조건 하나를 빼준 방법이기 때문에 기존의 선형 검색보다 비용은 반으로 절감되는 효과를 볼 수 있다.

 

 

 

2. 이진 검색 (binary search)

이진 검색은 선형 검색보다 빠르게 검색할 수 있는 장점을 가지고 있는데 배열이 정렬된 상태에서 검색이 시작되야 효율적이다.

그림을 보면서 어떻게 이진 검색이 이루어지는지 알아보자.

먼저 처음에는 배열의 범위를 왼쪽은 맨 앞, 오른쪽은 맨 뒤로 잡는다.

그리고 범위의 왼쪽 인덱스와 오른쪽 인덱스의 절반에 위치한 값과 찾고자 하는 값을 비교한다.

만약, 비교하였을 때 같다면 그냥 반환을 해주면 되는 것이고 찾고자 하는 값보다 큰 경우에는 오른쪽 범위를 가운데 앞으로 당겨주어 다음 검색 범위를 반으로 줄여준다.

찾고자 하는 값보다 작은 경우에는 왼쪽 범위를 가운데 뒤까지 당겨주어 검색 범위를 반으로 줄여준다.

이렇게 검색의 범위를 반으로 줄이면서 가운데 값과 찾고자 하는 값을 비교하면서 찾고자 하는 값이 존재하는지 검색하면 된다.

 

이진 탐색의 종료조건은 아래의 2가지와 같다.

- a[pc]와 key가 일치하는 경우(pc는 검색 범위의 절반위치)

- 검색 범위가 더 이상 없는 경우

 

그러면 이진 검색 알고리즘을 구현한 코드를 봐보자.

def bin_search(arr, key):
    left_pointer = 0
    right_pointer = len(arr) - 1
    
    while left_pointer <= right_pointer:
        middle_pointer = (left_pointer + right_pointer) // 2
        if a[middle_pointer] == key:
            return middle_pointer
        elif a[middle_pointer] < key:
            left_pointer = middle_pointer + 1
        else:
            right_pointer = middle_pointer - 1
    
    return -1

찾고자하는 key값과 정해진 범위에서 가운데 값을 비교하며 left_pointer를 옮겨 범위를 반으로 줄이거나 right_pointer를 옮겨 범위를 반으로 줄이는 과정을 반복하면서 원하는 값을 찾는 것을 알 수 있다.

 

 

 

---

[오늘의 나는 어땠을까?]

오늘은 많은 일들이 있었다.

일단 처음으로 코딩 테스트 모의고사가 진행됐다.

정글에 들어오기 전에 코딩 테스트를 응시한 경험이 6~7번 정도 있어서 내가 풀 수 있는 문제를 빠르게 파악해서 버릴 건 버리고 풀 수 있는 건 확실히 풀 수 있도록 하는 선택이 중요한 것같다.

오늘은 3문제에 1시간 30분이 주어졌고 결과는 2문제 풀어서 2문제 맞췄다.

마지막 문제는 3문제 중 가장 어려운 문제였는데 남은 시간 40여분을 투자해도 어떻게 풀어야할지 감이 오지를 않았다.

모의고사를 보기 이전에 팀원들이 몇 개 푸는게 목표인지 물어봤다.

솔직히 마음 속으로는 3문제 모두 푸는 것이였지만 그냥 2문제만 풀어도 만족한다고 했다.

3문제를 꼭 풀어야하는 건아니지만 3문제를 다 푼 것에 뭔가 내가 성장했다는 것을 느낄 수 있다고 생각했다.

아쉽지만 2주차 모의고사로 올솔 성공 목표를 이루는 것을 미뤄야겠다...

 

다음으로 17시에 소규모 면담을 참여했다.

6개의 질문을 했는데 운영진님들 중 한 분이 해준 말이 가장 기억에 남는다.

 

이상적인 모습으로 되는 것이 당연히 좋은 것이지만 현재 자신의 상태를 파악하고
주어진 시간을 효율적으로 활용하는 것이 중요하다.
이상적인 것을 추종하려하지 말고 어제의 나보다 발전하려고 노력해라.

 

너무 와닿는 말이였다.

나는 너무 이상적인 것, 나의 위치를 생각하지 않고 너무나 높은 곳을 바라보며 올라가려고 한 것같다.

어제의 나보다 발전, 어제는 몰랐지만 오늘은 알게된 지식..

나는 나의 발전에 집중하면서 시간을 효율적으로 활용하며 지속적으로 성장할 것이다.

느려도 꾸준하게. 비교 대상은 어제의 나.

 

---

<참고 자료>

자료구조와 함께 배우는 알고리즘 입문 파이썬 편 (저자 Bohyoh Shibata, 옮김 강민)