알고리즘과 자동화

• 수동적인 계산을 어떻게 컴퓨터에서 자동화 할지?

알고리즘의 다양성

• 정렬에 대해서 배우는 이유
  • 정렬이란 무엇인가? - 숫자 두 개의 크기를 비교하고 바꿔주는 작업을 반복하여 조건에 맞게 순서를 맞춰주는 작업
  • 모든 알고리즘의 기반이 된다 (중요)
• 자료구조와 알고리즘의 연관성 - 구구단을 외우는 것과 유사하다 (숫자와 곱셉의 개념처럼)
  • 자료구조(기반) 는 숫자, 알고리즘은 곱셉 (방법)
• 탐색조건이 적음 → 쉽지만 데이터 양이 많은 경우에는 반복이 많으므로 시간과 메모리를 많이 소비

알고리즘의 활용

• 주로 수학과 연관되어 활용

  • 팩토리얼 (n!)

  # 팩토리얼 예시코드
  
  n = int(input("숫자 입력하세요 : "))
  def factorial(n) :
    if n > 0 :
      return n * factorial(n - 1)
    else :
        return 1
  
  print('팩토리얼 결과 : ', factorial(n))
  

  데코레이터를 통한 속도 측정

  # case - 1
  @check_time # 데코레이터 생성하여 활용
  def sum_n(n):
      s = 0
      for i in range(1, n+1):
          s += i
      return s
  
  if __name__ == "__main__":
  	sum_n(100000)
  

  교환 (SWAP)

  # 첫번째 방법
  a = 3
  b = 1
  
  temp = a
  a = b
  b = temp
  
  print(a,b)
  

Search Algorithm Basic (탐색 알고리즘 기본)

선형 및 이진검색

• Linear Search (선형)

  • 한 번에 하나씩 모두 검색
  • 반복문을 활용해 배열의 변수 (반복자 i) 만큼 검색을 진행한다

  def linear_search(linear_arr, search_number):
      for i in range(len(linear_arr)):
        if linear_arr[i] == search_number:
          return i
  
  linear_arr = [5,22,87,1,3]
  search_number = 1
  print("search index : ",linear_search(linear_arr, search_number))
  

• Binary Search (이진)

  • 반복을 통해 숫자를 반으로 줄이면서 검색

  • 선형보다 속도가 더 빠름

  • 이미 정렬된 경우에만 작동

    • 정렬된 선형의 숫자들 중 특정 숫자를 효율적으로 검색하기위해 나온 방법

    #찾고자 하는 수의 인덱스를 반환한다 
    
    def test_binary_search(test_list, test_search_item):
    
         low = 0  # 인덱스가 0(리스트의 첫번째 항목)으로 주어진다.
         high = len(test_list) - 1  # 인덱스의 마지막 항목(리스트길이 - 1)
    
         while low <= high:
             middle = (low + high) // 2   # middle 변수를 생성해서 이진검색속도를 빠르게 한다.
             search_value = test_list[middle]
    
             if search_value == test_search_item:
                 return middle   # 이진검색을 통해 값을 찾는 경우, 검색값의 인덱스를 반환한다.
             if search_value > test_search_item:
                 high = middle - 1
             else:
                 low = middle + 1
         return '인덱스를 찾지 못함'   # 이진검색을 통해 값을 찾지 못하는 경우, 별도의 인덱스를 반환하지 않는다.
    
    test_list = [6,12,17,23,38,45,77,84]   # 이진검색의 조건에 적합하도록 이미 정렬된 리스트를 활용한다.
    print('이진검색을 통해 검색된 리스트 인덱스 : ', test_binary_search(test_list, 12))
    

Iterative Sorting (반복 정렬)

Selection Sort (선택정렬)

• 왼쪽부터 가장 작은 노드와 비교하면서 교환을 시작
  • 기준 노드는 가장 앞부터
• 최소노드 선택 → 왼쪽부터 비교 → 교환
• 시간 복잡도 - O(n^2)

Iteration Sort (삽입정렬)

• 아직 정렬되지 않은 특정 노드와 정렬된 노드들의 값을 비교하고 값이 더 큰 것의 인덱스보다 작은 인덱스에 삽입하여 정렬하는 알고리즘