[원격 강의] 쉽게 배우는 알고리즘(2)

1주차를 마무리 짓고 2주차를 듣기 시작했다....
이건 뭐지...
ㅜㅠ

1주차

• 공간 복잡도 판단하기
  • 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
  • 저장하는 데이터의 양이 1개의 공간을 사용함
  • 보통 공간 복잡도보다 시간 복잡도로 알고리즘 성능을 판단함
  • 최빈값 찾기 알고리즘의 공간 복잡도를 판단해보자
    • 첫 번째 방법

      alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z"]
      # -> 26 개의 공간을 사용합니다
          max_occurrence = 0 # 1개의 공간을 사용합니다
          max_alphabet = alphabet_array[0]   # 1개의 공간을 사용합니다.
      
          for alphabet in alphabet_array:
              occurrence = 0  # 1개의 공간을 사용합니다

      1. alphabet_array의 길이 = 26

      2. max_occurrence, max_alphabet, occurrence의 변수 = 3

         == 29만큼의 공간이 사용됨.

    • 두 번째 방법

      alphabet_occurrence_list = [0] * 26 # -> 26 개의 공간을 사용합니다
      
          for char in string:
              if not char.isalpha():
                  continue
              arr_index = ord(char) - ord('a')  # 1개의 공간을 사용합니다
              alphabet_occurrence_list[arr_index] += 1
      
          max_occurrence = 0                   # 1개의 공간을 사용합니다
          max_alphabet_index = 0               # 1개의 공간을 사용합니다
          for index in range(26):
              alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용합니다
              if alphabet_occurrence > max_occurrence:
                  max_occurrence = alphabet_occurrence
                  max_alphabet_index = index

      1. alphabet_array의 길이 = 26

      2. max_occurrence, max_alphabet, occurrence의 변수 = 4

         == 30만큼의 공간이 사용됨.

    • 29와 30이 모두 상수라 비교하기 애매함. 이럴 땐 시간 복잡도로 비교해보자!
      • 첫 번째 방법 - 시간 복잡도

        for alphabet in alphabet_array:    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
                occurrence = 0                  # 대입 연산 1번 실행
                for char in string:             # string 의 길이만큼 아래 연산이 실행
                    if char == alphabet:        # 비교 연산 1번 실행
                        occurrence += 1         # 대입 연산 1번 실행 
        
                if occurrence > max_occurrence: # 비교 연산 1번 실행
                    max_alphabet = alphabet     # 대입 연산 1번 실행
                    max_occurrence = number     # 대입 연산 1번 실행

        1. alphabet_array 의 길이 X 대입 연산 1번

        2. alphabet_array 의 길이 X, string의 길이 X (비교 연산 1번 + 대입 연산 1번)

        3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번)

           == 26(1 + 2N + 3) = 52N + 104

      • 두 번째 방법 - 시간 복잡도

        for char in string:        # string 의 길이만큼 아래 연산이 실행
                if not char.isalpha(): # 비교 연산 1번 실행
                    continue
                arr_index = ord(char) - ord('a')         # 대입 연산 1번 실행 
                alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행 
        
            max_occurrence = 0        # 대입 연산 1번 실행 
            max_alphabet_index = 0    # 대입 연산 1번 실행 
            for index in range(len(alphabet_occurrence_list)):    # alphabet_array 의 길이(26)만큼 아래 연산이 실행
                alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행 
                if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행 
                    max_occurrence = alphabet_occurrence # 대입 연산 1번 실행 
                    max_alphabet_index = index           # 대입 연산 1번 실행

        1. string의 길이 X (비교 연산 1번 + 대입 연산 2번)

        2. 대입 연산 2번

        3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)

           == N (1 + 2) + 2 + 26 (1 + 3) = 3N + 106

      • 비교하기 52N + 104 vs 3N+106 vs N^2
        • 알 수 있는 점
          • $52N + 104$ 든 $3N+106$ 이든 $N^2$ 에 비해서 아무것도 아니구나.
          • 공간 복잡도보다는 시간 복잡도를 더 신경 써야 한다!
• 점근 표기법
  • 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법
  • 알고리즘의 성능을 수학적으로 표기하고, 알고리즘의 “효율성”을 평가하는 방법
  • 종류
    1. 빅오(Big-O)표기법 : 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 // 주로 사용함
    2. 빅 오메가(Big-Ω)표기법 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지
  • 배열에서 특정 요소 찾기

    input = [3, 5, 6, 1, 2, 4]  # 배열 내 특정 숫자가 존재하면 True, 아니면 False
    
    def is_number_exist(number, array):
        for element in array:
            if number == element:
                return True
    
        return False
    
    result = is_number_exist(3, input)
    print(result)

    • 이 함수의 시간 복잡도는?

      input = [3, 5, 6, 1, 2, 4]
      
      def is_number_exist(number, array):
          for element in array:  # array 의 길이만큼 아래 연산이 실행
              if number == element:  # 비교 연산 1번 실행
                  return True     # N * 1 = N 만큼
      
          return False
      
      result = is_number_exist(3, input)
      print(result)

      input = [4, 5, 6, 1, 2, 3]  # 운이 안 좋으면 input의 길이인 N만큼의 연산을 다 해야됨
      
      def is_number_exist(number, array):
          for element in array:  # array 의 길이만큼 아래 연산이 실행
              if number == element:  # 비교 연산 1번 실행
                  return True     # N * 1 = N 만큼
      
          return False
      
      result = is_number_exist(3, input)
      print(result)

      알고리즘은 성능이 항상 동일한 것이 아니라 입력 값과 입력값의 분포에 따라 성능이 변화할 수 있음

      입력값에 따라 달라지는 연산량

    • 표기법

      • 빅오 표기법 : O(N)
      • 빅 오메가 표기법 : Ω(1)
  • 기억해야 할 것
    • 입력값에 비례해서 얼마나 늘어날 지 파악하자
    • 공간 복잡도보다는 시간 복잡도를 더 줄이기 위해 노력하자
    • 최악의 경우 시간이 얼마나 소요될 지 고민하자 (빅오 표기법)
• 알고리즘 더 풀어보기(1)
  • 곱하기 or 더하기(왼쪽부터 계산했을 때 가장 큰 수를 구하기)

    input = [0, 3, 5, 6, 1, 2, 4]
    
    def find_max_plus_or_multiply(array):
        multiply_sum = 0  # 현재 계산하고 있는 합계
        for number in array:
            if number <= 1 or multiply_sum <= 1:
                multiply_sum += number
            else:
                multiply_sum *= number
        return multiply_sum
    
    result = find_max_plus_or_multiply(input)
    print(result)

    • 시간 복잡도 : O(N)
      • 1차 반복문이 하나, array의 길이만큼 반복 == O(N)
      • 다른 계수 버리기
• 알고리즘 더 풀어보기(2)
  • 반복되지 않는 문자(문자열에서 반복되지 않는 첫 번째 문자를 반환하자. 만약 없다면 _를 반환하자)

    input = "abadabac"
    
    def find_not_repeating_first_character(string):
        alphabet_occurrence_array = [0] * 26
    
        for char in string:
            if not char.isalpha():
                continue
            arr_index = ord(char) - ord("a")
            alphabet_occurrence_array[arr_index] += 1
    
        not_repeating_character_array = []  # 하나만 나오는 캐릭터들
        for index in range(len(alphabet_occurrence_array)):
            alphabet_occurrence = alphabet_occurrence_array[index]
            if alphabet_occurrence == 1:
                not_repeating_character_array.append(chr(index + ord("a")))  # index를 다시 한번 알파벳으로 전환시켜줘야함
    
        print(not_repeating_character_array)
    
        for char in string:
            if char in not_repeating_character_array:
                return  char
        return "_"
    
    result = find_not_repeating_first_character(input)
    print(result)

2주차

• 어레이(Array, 배열) (ex. 캡슐호텔)
  • 크기가 정해진 데이터의 공간(한 번 정해지면 바꿀 수 없음)
  • 각 원소에 즉시 접근할 수 있음(상수 시간 내 접근 가능 : O(1))
  • 원소의 순서는 0부터 시작하고 이를 인덱스라고 부름
  • 원소를 이동할 경우 O(N)의 시간 복잡도를 가짐
  • 원소를 새로 추가하기엔 비효율적인 자료구조
• 링크드리스트(Linked List, 리스트) (ex. 화물 열차)
  • 크기가 정해지지 않은 데이터의 공간
  • 특정 원소에 접근하려면 연결 고리(포인터)를 따라 탐색해야 함(O(N)) (화물칸 : 노드)
  • 원소를 중간에 삽입/삭제하고 싶을 땐 앞, 뒤의 포인터만 변경하면 됨(O(1))

• 클래스
  • 분류, 집합과 같이 속성과 기능을 가진 객체를 총칭하는 개념
    • 객체 : 세상에 존재하는 유일무이한 사물
  • 코드

    class Person:
        def __init__(self, param_name):  # self는 항상 존재해야 함
            print("i am created!", self)
            self.name = param_name
    
        def talk(self):
            print("안녕하세요, 제 이름은", self.name, "입니다.")
    
    person_1 = Person("유재석")  # () : 생성자(객체를 생성할 때 쓰는 함수)
    print(person_1.name)
    print(person_1)
    person_1.talk()
    person_2 = Person("박명수")
    print(person_2.name)
    print(person_2)
    person_2.talk()

• 링크드 리스트 구현

  • 노드에게 필요한 것

    • 칸에 있는 데이터
    • 다음 칸이 무엇인지 → 두가지 데이터를 가지고 있어야 하니까 클래스(LinkedList)로 묶으면 됨
      • LinkedList : head node, 맨 처음 데이터만 가지고 있으면 됨.(그러면 다음 거 타고 타고 가면 됨)
        • self.head에 시작하는 노드를 저장함
        • 다음 노드를 보기 위해서는 각 노드의 next를 조회해서 찾아야 함.

  • 코드

    # [3] -> [4]  // 노드 안에 들어가야 할 것 : 각 노드가 데이터랑 다음 칸에 있는 포인터가 있어야 함
    # data, next  // 다음 칸을 나타내는 것들
    class Node:  # 데이터와 넥스트를 주입 받아야 함
        def __init__(self, data):  # data를 입력받아서 self.data에 저장을 할 것임
            self.data = data  # self.data에 data를 주입함
            self.next = None  # self.next에는 None을 넣어줌 < 처음 생성할 때에는 아무것도 다음을 가리키지 않기 때문
    
    node = Node(3)  # 테스트
    print(node)  # 실행값 = <__main__.Node object at 0x00000269950E5BE0>
    ----------
    print(node.data)  # 실행값 = 3
    ----------
    node = Node(3)  # 테스트
    first_node = Node(4)
    node.next = first_node
    print(node.next.data)  # 실행값 = 4
    
    print(node.data)  # 실행값 = 3

    • 링크드리스트 구현

      class LinkedList:  # LinkedList는 head node만 가지고 있으면 됨
          def __init__(self, data):  # self, data를 받고
              self.head = Node(data)  # self.head에 해당 data를 들고 있는 노드를 생성해서 넣어주면 됨
                                      # 방금 생성한 이 노드가 head 노드로 저장이 됨 >> LinkedList 생성 끝!!
      
      linked_list = LinkedList(3)  # linked_list 정의해보자
      print(linked_list)  # 실행값 = <__main__.LinkedList object at 0x000002002D3FE970>
      ----------
      print(linked_list.head)  # 실행값 = <__main__.Node object at 0x00000201C321ED00>
      ----------
      print(linked_list.head.data)  # 실행값 = 3
      ----------
      print(linked_list.head.next)  # 실행값 = None

    • append라는 함수 구현

      class Node:
      		def __init__(self, data):
      				self.data = data
      		self.next = None
      
      			node = Node(3)
      			first_node = Node(4)
      			node.next = first_node
      
      			class LinkedList:
      		def __init__(self, data):
      		self.head = Node(data)
      
      		def append(self, data):
      				if self.head is None:
          		self.head = Node(data)
          		return
      
      		cur = self.head
      		while cur.next is not None:
          		cur = cur.next
          		print("cur is", cur.data)
      		cur.next = Node(data)
      
      		# 노드들의 값들을 전부 다 출력해보자
      		def print_all(self):
      		print("hihihi")
      		cur = self.head
      		while cur is not None:
          		print(cur.data)  # cur을 계속 옮기면서 값을 출력해주면 됨
          		cur = cur.next
      
      			linked_list = LinkedList(3)
      			linked_list.append(4)
      			linked_list.append(5)
      			linked_list.print_all()

• 느낀점

  • 오늘 3주차까지 들어야한다는데... 왜 난 아직도 2주차에서 못 벗어났죠ㅜ
    튜터님이 직접 쳐보진 않더라도 우선 몇 번 들어서 익숙해지는게 낫다고 하시니까 산책갔다와서 강의 들어야겠다,, 오늘도 할 일이 많네ㅔ에