UNIT 06 (탐색)

순차 탐색

문제) 주어진 리스트에 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘을 만들어라. 리스트에 찾는 값이 없다면 -1을 돌려준다.

# 리스트에서 특정 숫자의 위치 찾기
# 입력 ; 리스트 a, 찾는 값 x
# 출력 : 찾으면 그 값의 위치, 찾지 못하면 -1

def search_list(a, x):
    n = len(a)
    for i in range(0, n):
        if x == a[i]:
            return i

    return -1

v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_list(v, 18))
print(search_list(v, 33))
print(search_list(v, 900))

연습문제

6-1) 프로그램 601은 리스트에 찾는 값이 여러 개 있더라도 첫 번째 위치만 결과로 돌려준다. 찾는 값이 나오는 모든 위치를 리스트로 돌려주는 탐색 알고리즘을 만들어라. 찾는 값이 리스트에 없다면 빈 리스트인 [ ]를 돌려준다.

def search_list(a, x):
    list = []
    n = len(a)
    for i in range(0, n):
        if x == a[i]:
            list.append(i)

    return list

v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_list(v, 18))
print(search_list(v, 33))
print(search_list(v, 900))

6-2) 연습 문제 6-1 프로그램의 계산 복잡도는 무엇인가? O(n)

6-3) 다음과 같이 학생 번화와 이름이 리스트로 주어졌을 때 학생 번호를 입력하면 학생 번호에 해당하는 이름을 순차 탐색으로 찾아 돌려주는 함수를 만들어라. 해당하는 학생 번호가 없으면 물음표(?)를 돌려준다. 참고로 학생 번호가 39번이면 "Justin", 14번이면 "John"을 돌려준다.
stu_no = [39, 14, 67, 105]
stu_name = ["Justin", "John", "Mike", "Summer"]

def search_list(a, b, x):
    n = len(a)
    for i in range(0, n):
        if x == a[i]:
            return stu_name[i]

    return "?"

stu_no = [39, 14, 67, 105]
stu_name = ["Justin", "John", "Mike", "Summer"]

print(search_list(stu_no, stu_name, 39))
print(search_list(stu_no, stu_name, 67))
print(search_list(stu_no, stu_name, 100))

출처

모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10