모두의 알고리즘 문제07. 순차 탐색 연습문제

7-1 찾는 값이 나오는 모든 위치를 리스트로 돌려주는 탐색 알고리즘을 만들어 보세요. 찾는 값이 없다면 빈 리스트를 돌려줍니다.

#연습문제 7-1
def search_list_all(a, x):   # 탐색 대상 리스트a, 찾는값x
    result=[]   # 반환값 저장용 리스트
    n=len(a)
    for i in range(0, n):
        if a[i]==x:
            result.append(i)
    return result

v = [12, 234, 32, 423, 12, 55, 34, 23, 43, 11, 12, 22, 11]

print(search_list_all(v, 12)) # [0, 4, 10]
print(search_list_all(v, 11)) # [9, 12]
print(search_list_all(v, 222)) # []

 

7-2 연습문제 7-1 프로그램의 계산복잡도는?

O(n). 값 찾으려면 리스트 끝까지 찾아봐야함. 리스트 길이와 탐색횟수가 비례한다.

 

 

7-3 학생 번호와 이름이 리스트로 주어졌을 때 학생 번호를 입력하면 학생 번호에 해당하는 이름을 순차탐색으로 찾아 돌려주는 함수를 만들라. 해당하는 학생 번호가 없으면 물음표를 돌려준다.

 

# 연습문제 7-3
def search_stuName(a, stu_no, stu_name): # 찾는 학생번호n, 학생번호 리스트, 학생이름 리스트
    n=len(stu_no)
    for i in range(0, n):
        if stu_no[i]==a:
            return stu_name[i]

    return "?"

stu_no = [39, 14, 68, 106]
stu_name=["justin", "john", "mike", "summer"]

print(search_stuName(39, stu_no, stu_name)) # justin
print(search_stuName(68, stu_no, stu_name)) # mike
print(search_stuName(11, stu_no, stu_name)) # ?