Python algorithm 개념 및 실습 - 순차탐색

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

탐색 : 주어진 리스트에 특정한 값이 있는지 찾아 그 위치를 리턴

# 순차 탐색 : 특정한 요소의 위치 리턴(찾은 경우), 못찾으면 -1

def seq_search(list1, key):

    size = len(list1)

    for i in range(size):

        if key == list1[i]:

            return i

    # for문을 다 돌았는데도 못찾으면 -1

    return -1

 

 

# 찾는 숫자가 여러개 있다면 모든 위치를 리스트로 리턴

 

 # 못 찾는 경우 빈 리스트

def seq_search2(list1, key):

    size = len(list1)

    # 비어 있는 리스트

    result = []  # result = list()

    for i in range(size):

        if key == list1[i]:

            result.append(i)

    return result

if __name__ == "__main__":

    list1 = [17, 92, 18, 33, 58, 7, 33, 42]

    print("18 값", seq_search(list1, 18))

    print("33 값", seq_search(list1, 33))

    print("800 값", seq_search(list1, 800))

    print()

    print("18 값", seq_search2(list1, 18))

    print("33 값", seq_search2(list1, 33))

    print("800 값", seq_search2(list1, 800))

 

학생 번호와 이름이 리스트로 주어졌을 때 학생 번호를 입력하면 학생 번호에 해당하는 이름을 순차탐색으로 찾아 돌려주는 함수 작성

 

 

# 찾는 학생의ㅣ 번호가 없다면 ? 리턴

# enumerate 함수를 사용하면 index 값을 쉽게 가지고 올수 있음.

def search_name(stu_no, stu_name, num):

    for idx, no in enumerate(stu_no):

        if no == num:

            return stu_name[idx]

    return "?"

if __name__ == "__main__":

    stu_no = [39, 14, 67, 105]

    stu_name = ["Justin", "John", "Mike", "Summer"]

    print(search_name(stu_no, stu_name, 39))  

    print(search_name(stu_no, stu_name, 67))  

    print(search_name(stu_no, stu_name, 190))  # 해당 학생 없음