[알고리즘] 순차 탐색

* <모두의 알고리즘 with 파이썬>의 문제 07를 정리한 내용입니다.

 

1. 순차 탐색이란?

• 임의의 리스트 A가 주어졌다고 가정해보자. 나는 리스트A에 임의의 원소 X가 있는지, 없는지 확인하고 싶다. 이때 리스트에 있는 첫 번째 자료부터 하나씩 비교하면서 같은 값을 찾는 -- '리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색하는' 알고리즘을 순차 탐색이라고 한다. 
• 순차 탐색 알고리즘으로 원하는 값을 찾으려면 몇 번 비교해야할까?
  • 이것은 케바케다. 만약 내가 찾고자하는 원소가 리스트의 맨 앞에 있다면 단 한번의 비교로도 찾을 수 있다. 하지만 맨 뒤에 있다면? 즉, 같은 원소여도 원소가 리스트의 어디에 위치했느냐에 따라 비교 횟수가 달라진다. 
  • 이처럼 경우에 따라 계산 횟수가 다를 때는 보수적인 관점에서 최악의 경우로 시간 복잡도를 계산한다. 순차 탐색의 경우, 비교해보려면 최대 n번의 비교가 필요하고, 따라서 계산 복잡도는 O(n)이 된다. 

 

 

2. 문제 풀이 (1)

• 찾는 값이 나오는 모든 위치를 리스트로 돌려주는 탐색 알고리즘을 만들어보세요. 찾는 값이 리스트에 없다면 빈 리스트인 []를 돌렬줍니다. 이때, 프로그램의 계산 복잡도는 무엇일까요? 

 

v = [12, 13, 14, 14, 15, 61, 45, 12, 15]

def search_number(x, v):
    find = []
    for i in range(len(v)):
        if x == v[i]:
            find.append(i)
    return find 

find_14 = search_number(14, v)
find_44 = search_number(44, v)​

이때 시간 복잡도는 O(n)이다. 모든 위치를 반환하든, 첫 번째 위치만 반환하든, 어쨌거나 리스트의 모든 원소를 훑기 떄문이다. 위 코드의 실행 결과는 다음과 같다.

 

 

3. 문제 풀이 (2)

• 다음과 같이 학생 번호와 이름이 리스트로 주어졌을 때, 학생 번호를 입력하면 학생 번호에 해당하는 이름을 순차 탐색으로 찾아 돌려주는 함수를 만들어 보세요. 해당하는 번호가 없으면 물음표(?)를 돌려줍니다.

  stu_no = [39, 14, 67, 105]
  stu_name = ['Justin', 'John', 'Mike', 'Summer']
  
  def search_stuName(stu_no, stu_name, number):   
      name = '?'
      for i in range(len(stu_no)):
          if number == stu_no[i]:
              name = stu_name[i]
      return name
  
  name_105 = search_stuName(stu_no, stu_name, 105)
  name_77 = search_stuName(stu_no, stu_name, 77)​