검색 알고리즘 - (선형 알고리즘)

이제 정말 알고리즘에 대해 시작하는 느낌이다. 선형 알고리즘이 가장 기초가 되는 방법인 것 만큼 크게 어렵지 않아 쉽게 공부할 수 있었다. 

 

이해가 안되는 코드도 단원을 마치고 다시 생각해보니 크게 어려웠던 내용이 아니고 내가 이해를 못했었던 것 같다.

 

앞으로도 초심을 잃지말고 지금처럼만 공부를 하면 좋은 코드를 만들 수 있는 사람이 될 수 있을거라고 생각을 하며 공부해야겠다.

---

선형 알고리즘

 

선형 알고리즘이란 검색값(key)을 배열의 0번 인덱스부터 마지막까지 찾아보는 알고리즘이다.

 

배열의 모든 인덱스를 하나하나 찾아보기 때문에 알고리즘 자체의 효율성은 좋지 않을 수 있지만 간단하고 확실하기 때문에 많이 사용되기도 한다.

 

다음은 선형 알고리즘의 코드이다. 

# while 을 이용한 선형 알고리즘

def seq_search(a,key):
    i = 0

    while(True):
        if i == len(a):
            return -1
        if a[i] == key:
            return i
        i += 1

if __name__ == '__main__':
    num = int(input('원소 수 입력: '))
    x = [[None] * num]

    for i in range(num):
        x[i] = int(input('검색할 값 입력: '))

        idx = seq_search(x,ky)

        if idx == -1:
            print('검색값을 갖는 원소가 존재하지 않습니다.')

        else:
            print(f'검색값은 x[{idx}]에 있습니다.')

 코드의 내용을 보면 배열에서 키값을 찾을 때 2개의 조건이 있다는 것을 볼 수 있다. 먼저 첫번쨰로는 키값과 원소의 값이 같은가? 이다. 

 

이 질문은 해당 값을 찾기 위해 무조건 적으로 필요하기 때문에 반드시 필요하다.

 

하지만 2번째는 i가 배열의 끝번호를 지났는가? 이다. 이 질문은 원하는 키값이 배열에 없을 때 배열에 없다는 내용을 알기위한 내용인데 이로 인해 낭비비용이 생길 수 있다.

인덱스 0번인 5부터 인덱스값을 하나씩 늘려가며 7을 찾는 것이다. 선형알고리즘은 이렇게 원하는 키값이 뒤에 있거나 없을 때에는 큰 리스크가 있다.

 

보초법

 

앞서 언급했던 것처럼 선형 알고리즘에는 2가지의 질문이 있다. 첫번째는 '키값과 원소값이 같은지' (검색)이고, 다른 하나는 '리스트 안에 존재하는가' 이다.

 

여기서 키값이 항상 리스트 안에 존재한다면 이 질문은 하지 않아도 된다. 그래서 만들어진게 보초법이다.

 

보초법은 사용자가 검색하려는 값 (key값)을 배열의 맨 뒤에 추가하여 항상 그 값이 있도록 유지하는 방법이다. 이렇게 했을 때 이점은 리스트안에 해당 값이 있는지에 대한 if 문을 제거할 수 있으므로 알고리즘 면에서 이득이다.

 

다음은 보초법의 코드이다.

import copy

def seq_search(seq,key):
    a = copy.deepcopy(seq)
    a.append(key)

    i = 0
    while True:
        if a[i] == key:
            break
        i += 1

    return -1 if i == len(seq) else i

if __name__ == '__main__':
    num = int(input('원소수 입력 :'))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'x[{i}]:'))

    ky = int(input('검색할 값 입력: '))

    idx = seq_search(x,ky)

    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')

    else:
    print(f'검색값은 x[{idx}]에 있습니다.')

먼저 seq 를 복사하여 a 리스트에 key값과 함께 넣는다. 이 때 키값은 a리스트의 맨 마지막에 위치한다.

 

그런 후에 배열의 원소를 스캔하여 검색하는 과정을 반복하고,

 

16행에 나타나는 return은 해당 값을 찾았을 때 그 값이 보초값인지 기존에 있던 데이터인지 판별해 주는 역할을 한다. 

 

따라서 보초법을 사용하더라도 데이터의 무결성을 유지하고 알고리즘면의 이점만 있는 선형 알고리즘을 보완한 코드를 만들 수 있다.