2023.04.13 TIL

오늘의 나는 무엇을 잘했을까?

시간분배를 잘 해서 진도 및 학습이 원활했던 것 같다.

오늘의 나는 무엇을 배웠을까?

• 알고리즘 패러다임

  하나의 문제에 대해 각기 다른 접근법이 존재한다. 이렇게 문제에 접근하는 방식들을 카테고리화 하여 나눈 것을 알고리즘 패러다임이라고 부른다. 알고리즘 패러다임을 공부하면 문제를 푸는 요령이나 해결책에 대한 실마리들을 학습할 수 있다.
  

• Brute Force 알고리즘

  가능한 모든 경우의 수를 전부 시도하는 가장 순진한 알고리즘 접근법이다.

  문제를 보며 brute force 접근법을 시도해보자.

  [문제]
  카드 3장씩을 왼쪽, 오른쪽에서 각각 가지고 있다. 왼쪽 한 장, 오른쪽 한 장을 뽑아 카드에 적힌 두 수를 곱한 값을 생성한다고 할 때, 가능한 가장 큰 값을 찾아라.

  def max_product(left_cards, right_cards):
      max = left_cards[0] * right_cards[0]
      for l_card in left_cards:
          for r_card in right_cards:
              if max < l_card * r_card:
                  max = l_card * r_card
      return max    
  # 테스트 코드
  print(max_product([1, 6, 5], [4, 2, 3]))
  print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
  print(max_product([-1, -7, 3], [-4, 3, 6]))

  위 코드와 같이 모든 경우의 수를 전부 대입해보며 가장 큰 수를 찾는 방법이 brute force 접근법을 사용한 방식이다.

  • 장점

    • 직관적이고 명확하다
    • 확실한 답을 찾을 수 있다.

  • 단점
    - 무식한 방법이라 효율이 가장 낮다.

    brute force 알고리즘은 좋은 알고리즘 축에는 속하지 않지만, 어떤 문제든 먼저 생각해야 하는 알고리즘이다. 효율적인 알고리즘을 찾는 과정에 있어서 항상 출발점이 되는 접근방식임을 기억하자.

• Divide and conquer 알고리즘

  분할 정복 알고리즘이라고도 부르며, 해결하기 복잡한 하나의 큰 문제를 작은 부분 문제들로 나누어 풀고, 부분 문제들에 대한 해답을 기존 큰 문제에 대한 해결의 조각으로 사용하는 방법이다.

  Divide and Conquer는 다음 세 단계로 이루어진다.

  1. Divide
     

  2. Conquer
     

  3. Combine
     

     Divide and Conquer 방식은 어렵다. 하나의 큰 문제를 바로 어떻게 부분문제로 쪼갤지 감이 안오는 경우가 많다. 이럴 때는 부분 문제로 나누었다 해도 부분 문제 또한 Divide and conquer방식으로 다시 쪼개야 하는 경우가 많을 것이다. 하지만 충분히 연습하고 익숙해지다 보면 어떻게 문제를 나누어야 좋을지 감이 잡힐 것이다.

  • Divide and Conquer의 대표적 문제, Merge sort

    대표적으로 Divide and Conquer를 사용하는 알고리즘중에 merge sort(병합 정렬)이 있다. 다음 그림을 보며 어떻게 분할 정복하는지 알아보자.
    

    def merge(list1, list2):
        ret = []
        len1 = len(list1)
        len2 = len(list2)
        i = 0
        j = 0
        while i < len1 and j < len2:
            if list1[i] <= list2[j]:
                ret.append(list1[i])
                i += 1
            else:
                ret.append(list2[j])
                j += 1
        if i == len1:
            ret += list2[j:]
        else:
            ret += list1[i:]
        return ret
    
    # 합병 정렬
    def merge_sort(my_list):
        list_len = len(my_list)
        if list_len == 1:
            return my_list
        
        first_half = merge_sort(my_list[:(list_len // 2)])
        second_half = merge_sort(my_list[(list_len // 2):])
        return merge(first_half, second_half)

  • 또 다른 분할 정복의 대표주자, quick sort

    퀵 정렬또한 분할 정복 알고리즘을 사용하는 대표 알고리즘이라 할 수 있다. 병합 정렬에서는 combine하는 부분이 어려웠지만, 퀵 정렬에서는 divide 파트가 까다롭고 어렵다. 반면 combine하는 파트는 크게 어렵지 않다.

  1. Divide

     피벗을 정해 파티션을 나눈다. pivot의 왼쪽에는 pivot보다 작은 값들이 들어가고, 오른쪽에는 큰 값들이 들어간다.

     

  2. Conquer

     각 파티션을 퀵 정렬한다. 결과적으로 전체 정렬이 되어있다.

     

  3. Combine

     Divide와 Conquer단계만 거치면 자동으로 정렬이 되어있기 때문에 딱히 해줄일이 없다.

     # 두 요소의 위치를 바꿔주는 helper function
     def swap_elements(my_list, index1, index2):
         # 여기에 코드를 작성하세요
         my_list[index1], my_list[index2] = my_list[index2], my_list[index1]
     
     # 퀵 정렬에서 사용되는 partition 함수
     def partition(my_list, start, end):
         # 여기에 코드를 작성하세요
         b = start
         i = start
         p = end
         while i < p:
             if my_list[p] > my_list[i]:
                 swap_elements(my_list, b, i)
                 b += 1
             i += 1
         swap_elements(my_list, b, p)
         return b 
     
         
     # 퀵 정렬
     def quicksort(my_list, start, end):
         # 여기에 코드를 작성하세요
         if start > end:
             return
         pivot = partition(my_list, start, end)
         quicksort(my_list, start, pivot - 1)
         quicksort(my_list, pivot + 1, end)

오늘의 나는 어떤 어려움이 있었을까?

딱히 어려움이 없었다.

내일의 나는 무엇을 해야할까?

• 위클리미션 끝내기