AI교육과정 - Python.9

이진 탐색(Binary Search)

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

1. 이진 탐색과 순차 탐색의 비교

   

분할 정복 알고리즘과 이진 탐색

• 분할 정복 알고리즘
  • divide: 문제를 하나 또는 둘 이상으로 나눔
  • conquer: 나누어진 문제가 충분히 작고 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눔
  • divide: 리스트를 두 개의 서브 리스트로 나눔
  • conquer
    • 검색할 숫자 > 중간값: 뒷 부분의 서브 리스트에서 검색할 숫자를 찾음
    • 검색할 숫자 < 중간값: 앞 부분의 서브 리스트에서 검색할 숫자를 찾음

알고리즘 구현

• 이진 탐색은 데이터가 정렬되어 있는 상태에서 진행

  • 예) 데이터가 [2, 3, 7, 12, 20] 일 때
    - binary_search(data_list, find_data) 함수를 만듬
    - data_list의 중간값을 find_data와 비교해서
    - find_data < data_list의 중간값: 맨 앞부터 data_list의 중간까지 find_data를 찾음
    - find_data > data_list의 중간값: data_list의 중간부터 맨 끝까지 data_data를 찾음
    - 그렇지 않다면 data_list 중간값은 find_data로 일치

    def binary_search(data, search):
      print(data)
      if len(data) == 1 and search == data[0]:
        return True
      if len(data) == 1 and search != data[0]:
        return False
      if len(data) == 0:
        return False
      medium = len(data) // 2
      if search == data[medium]:
        return True
      else:
        if search > data[medium]:
          return binary_search(data[medium + 1:], search)
        else:
          return binary_search(data[:medium], search)
    
    binary_search(data_list, 90)
    [14, 33, 38, 40, 54, 63, 70, 89, 92, 97]
    [70, 89, 92, 97]
    [70, 89]
    []
    False

알고리즘 분석

• n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교 연산을 k회 진행
  • n X 12 X 12 X 12 ... = 1
  • n X 12𝑘 = 1
  • n = 2𝑘 = 𝑙𝑜𝑔2𝑛 = 𝑙𝑜𝑔22𝑘
  • 𝑙𝑜𝑔2𝑛 = k

빅 오 표기법으로는 k+1의 결국 최종 시간 복잡도 O(𝑙𝑜𝑔𝑛)

그래프(Graph)

• 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)으로 표현하기 위해 사용

그래프 관련 용어

• 노드(Node): 위치, 정점이라고 함
• 간선(edge): 위치 간의 관계를 표시한 선으로, 노드를 연결한 선(link 또는 Branch라고도 함)
• 인접 정점(adjacent vertex): 간선으로 직접 연결된 정점(또는 노드)

그래프 종류

1. 무방향 그래프
   • 방향이 없는 그래프
   • 간선을 통해서 노드 양방향으로 갈 수 있음
2. 방향 그래프
   • 간선에 방향이 있는 그래프
   • 보통 노드 A, B가 A->B로 가는 간선으로 연결되어 있는 경우 <A,B>로 표기(<A,B>와 <B,A>는 다름)
3. 가중치 그래프
   • 간선에 비용 또는 가중치가 할당된 그래프
4. 연결 그래프와 비연결 그래프
   • 연결 그래프: 그래프에 있는 모든 노드에 대해 항상 경로가 존재하는 경우
   • 비연결 그래프: 무방향 그래프에서 특정 노드에 대해 경로가 존재하지 않는 경우
5. 순환(cycle)과 비순환(acycle) 그래프
   • 순환 그래프: 단순 경로의 시작 노드와 종료 노드가 동일한 경우
   • 비순환 그래프: 사이클이 없는 그래프

그래프와 트리의 차이

1. BFS란?

   • 대표적인 그래프 탐색 알고리즘
   • 정점들과 같은 레벨에 있는 노드(형제 노드)들을 먼저 탐색하는 방식
   • 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회함(S 형식)

2. BFS 알고리즘 구현

   • 큐 자료구조를 활용
   • need_visit 큐, visited 큐 생성 엑셀 정리
     

   data.pop() # 스택 - 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 구조 - 후입선출
   data.pop(0) # 큐 - 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조 - 선입선출

   def bfs(graph, start_node):
     visited, need_visit = list(), list()
     need_visit.append(start_node)
   
     while need_visit:
       node = need_visit.pop(0)
       if node not in visited:
         visited.append(node)
         need_visit.extend(graph[node])
     return visited

깊이 우선 탐색(Depth_First Search)

1. DFS란?
   • 대표적인 그래프 탐색 알고리즘
   • 정점의 자식들을 먼저 탐색하는 방식
   • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회함
2. DFS 알고리즘 구현
   • 스택과 큐의 자료구조를 활용
   • need_visit 스택과 visited 큐를 생성

def dfs(graph, start_node):
  visited, need_visit = list(), list()
  need_visit.append(start_node)

  while need_visit:
    node = need_visit.pop()
    if node not in visited:
      visited.append(node)
      need_visit.extend(graph[node])
  return visited

탐욕 알고리즘(Greddy Algorithm)

• 최적의 해에 가까운 값을 구하기 위해 사용
• 근사치 추정에 활용
• 반드시 최적의 해를 구할 수 있는 것은 아님
• 여러 경우 중 하나를 결정해야 할 때마다, 매 순간이 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식

탐욕 알고리즘 예

• 지불해야 하는 값이 4720원일 때 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하는 방법
  • 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현
  • 탐욕 알고리즘으로 매 순간 최적이라고 생각되는 경우를 선택하면 됨

def min_coin_count(value, coin_list):
  coin_list.sort(reverse=True)
  total_coin_count = 0
  details = list()
  for coin in coin_list:
    coin_num = value // coin
    total_coin_count += coin_num
    value -= coin_num * coin
    details.append([coin, coin_num])
  return total_coin_count, details

• 수학, 과학 계산용 패키지
• 성능: ndarray가 파이썬의 list보다 빠름
• 메모리 사이즈 ndarray가 파이썬의 list보다 적은 메모리를 사용

1. array(배열)

   • 여러값들의 그룹
   • 타입: <class 'numpy.ndarray'>

2. array의 data 타입

   • ndarray는 list와 다르게 단일 데이터 타입만 허용
     • 리스트는 [1, 3.14, 'Python', '🥳', True] 와 같이 여러 타입 저장이 가능하나, np.array([1,2,3.14,True]) 는 전부 실수로 나옴 = array([1. , 2. , 3.14, 1. ])
       
   • dtype

     np.array([1,2,3.14,True], dtype=int)
     #array([1, 2, 3, 1])
     np.array([1,2,3.14,True,'1234'], dtype=int)
     #array([   1,    2,    3,    1, 1234])

3. 인덱싱과 슬라이싱

   • 배열의 부분 선택

   arr2d = np.array([[1,2,3,4],[5,6,7,8],[9,10,11,12]])
   arr2d.shape # (3, 4) - 3열 4행

   1. 0행 가져오기

      #[1 2 3 4]
      print(arr2d[0])
      print(arr2d[0])
      print(arr2d[0,:])

   2. 0열 가져오기

      #[1 5 9]
      print(arr2d[:,0])

4. Fancy 인덱싱

   • 범위가 아닌 index의 집합의 값을 선택하여 추출하고 싶을 때 활용

   np.array([[1,2,3,4], 5,6,7,8], [9,10,11,12]])
   #array([[1, 2, 3, 4], [5, 6, 7, 8]])
   arr2d[[0,1]]
   arr2d[[0,1],:]

5. Boolean 인덱싱

   • 조건 필터링을 통하여 boolean 값을 이용한 색인
   • ndarray와 boolean 리스트 크기가 동일해야함

   arr1 = np.array(['🤯','🥹','🍗','🥲','😇'])
   selValue = [True, True, False, False, True]
   arr1[selValue] # array(['🤯', '🥹', '😇'], dtype='<U1')

   • ndarray에 연산자 적용 시 결과값이 boolean으로 반환됨

   arr2d = np.array([[1,2,3,4], 5,6,7,8], [9,10,11,12]])
   arr2d > 7
   # array([[False, False, False, False],
   #       [False, False, False,  True],
   #       [ True,  True,  True,  True]])

1. 연산자

   • shape 길이가 같아야 하며, 같은 position끼리 연산함

   1. 덧셈 연산

      a = np.array([[1,2,3], [2,3,4]])
      b = np.array([[3,4,5], [1,2,3]])
      a + b # array([[4, 6, 8], [3, 5, 7]])

   2. 뺄셈 연산

      a - b
      # array([[-2, -2, -2], [ 1,  1,  1]])

   3. 곱셉 연산

      a * b
      # array([[ 3,  8, 15], [ 2,  6, 12]])

   4. 나눗셈 연산

      a / b
      # array([[0.33333333, 0.5       , 0.6       ],
      #       [2.        , 1.5       , 1.33333333]])

   5. 내적(dot product) = dot

      • 맞닿는 shape가 같아야 함
      • 결과 행렬은 떨어져있는 shape의 형태와 같아야함

      np.dot(a,b)
      #array([[22, 28], [22, 28], [31, 40]])

2. arange

   • 순차적인 값을 생성할 때 사용

   np.arange(1, 11)
   # array([ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10])

3. sort

   • 기본값은 오름차순
   • sort 시 값이 저장되지 않아서 정렬된 값이 필요하다면 따로 저장이 필요함

   np.sort(arr1)[::-1] # 내림차순

   1. 행 정렬

      np.sort(arr2d, axis = 0) # axis=0: 행

   2. 열 정렬

      np.sort(arr2d, axis = 1) # axsis=1: 열

   3. 축의 마지막 방향

      np.sort(arr2d, axis = -1) # axis=-1: 축이 많을 경우 마지막 축의 값을 설정

4. 숫자의 단일 연산

   a = np.array([[1,2,3], [4,5,6]])
   a + 3 # array([[4, 5, 6], [7, 8, 9]])
   a - 3 # array([[-2, -1,  0], [ 1,  2,  3]])
   a / 3 # array([[ 3,  6,  9], [12, 15, 18]])
   a * 3 # array([[0.33333333, 0.66666667, 1.        ], [1.33333333, 1.66666667, 2.        ]])