내일배움캠프 AI, 15일차 TIL - 2022.09.20

스파르타 코딩클럽 내일배움캠프 AI 웹개발자양성과정 3회차

2022.09.20. 15일차 - TIL

 

 

1. 알고리즘, 자료구조 강의

• 병합정렬(Merge sort) : 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업 반복
  - merge 부분 : 정렬된 array1과 array2의 원소를 하나씩 비교해 작은 것을 새로운 배열에 저장한다. 어느 한 배열의 원소가 없어질 때까지 반복하다 나머지 이어붙인다.

# 정렬된 array1과 array2의 원소를 하나씩 비교해 작은 것을 새로운 배열에 저장 -> 어느 한 배열의 원소가 없을 때까지 반복하다 나머지 이어붙임
def merge(array1, array2):
    array_result = []
    array1_index = 0
    array2_index = 0
    # len(array1) + len(array2)의 길이만큼 반복 => O(n)
    while array1_index < len(array1) and array2_index < len(array2):  
        if array1[array1_index] < array2[array2_index]:  # array1의 값이 더 작은 경우
            array_result.append(array1[array1_index])  # array1의 값을 배열에 추가하고 index 1 증가
            array1_index += 1
        else:  # array2의 값이 더 작거나 같은 경우
            array_result.append(array2[array2_index])  # array2의 값을 배열에 추가하고 index 1 증가
            array2_index += 1

    # array2가 남았을 경우
    if array1_index == len(array1):
        while array2_index < len(array2):
            array_result.append(array2[array2_index])
            array2_index += 1

    #array1이 남았을 경우
    if array2_index == len(array2):
        while array1_index < len(array1):
            array_result.append(array1[array1_index])
            array1_index += 1

    return array_result

     - merge_sort 부분 : 분할 정복을 통한 정렬로 반으로 계속 쪼개 단일 요소만 가진 배열이 되었을 때 정렬된 것으로 보고 병합

# 분할 정복을 통해 정렬 -> 반으로 계속 쪼개 단일 요소만 가진 배열이 되었을 때 정렬된 것으로 보고 병합
def merge_sort(array):
    # 탈출 조건 : 문자열의 길이가 1보다 작거나 같을 때 배열 반환
    if len(array) <= 1:
        return array
    mid = len(array) // 2  # 중간 인덱스 추출
    left_array = array[:mid]  # 좌측 배열
    right_array = array[mid:]  # 우측 배열
    print(array)
    print('left_array', left_array)
    print('right_array', right_array)
    array = merge(merge_sort(left_array), merge_sort(right_array))

    return array
    
# [1, 2, 3, 5] [4, 6, 7, 8] -> [1, 2, 3, 4, 5, 6, 7, 8]  /// n크기 배열 정렬을 위해 n/2인 부분 배열 2개 비교 -> n/2 * 2 번 비교
# [3, 5] [1, 2] -> [1, 2, 3, 5]   /// n/2크기 배열 2개의 정렬을 위해 n/4인 부분 배열 4개 비교 -> n/4 * 4 번 비교
# [6, 8] [4, 7] -> [4, 6, 7, 8]
# [5] [3] -> [3, 5]   /// n/4크기 배열 4개의 정렬을 위해 n/8인 부분 배열 8개 비교 -> n/8 * 8 번 비교
# [2] [1] -> [1, 2]   /// k단계에서 길이가 1이 되었을 때 종료이므로 n/2^k = 1 에서 k(단계)를 구해야 하기 때문에
# [6] [8] -> [6, 8]   /// k = logn and 병합은 n의 시간이 필요하기에
# [7] [4] -> [4, 7]   /// 시간복잡도는 총 O(nlogn)

 

• 스택 : 나중에 들어간 자료가 먼저 나오는 자료구조, LIFO
  - linked list로 구현
  - push(data) : 맨 앞에 데이터 넣기
  - pop() : 맨 앞의 데이터 뽑기
  - peek() : 맨 앞의 데이터 보기
  - isEmpty() : 스택이 비었는지 안 비었는지 여부 반환

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


# 스택 클래스 정의
class Stack:
    def __init__(self):
        self.head = None  # self.head는 현재 스택의 최상위 노드 지표

    # 맨 앞에 데이터를 넣는 메소드
    def push(self, value):
        new_node = Node(value)  # 해당 값으로 새로운 노드 생성
        new_node.next = self.head  # 새로운 노드의 next에 현재 최상위 노드를 연결
        self.head = new_node  # 최상위 노드 지표를 새로운 노드로 업데이트

        return self.head

    # 맨 앞의 데이터를 뽑는 메소드
    # pop 기능 구현
    def pop(self):
        if self.is_empty():
            return "Stack is empty!"
        delete_node = self.head  # 기존 최상위 노드 지표 저장 후
        self.head = self.head.next  # 다음 노드를 최상위 노드로 업데이트

        return delete_node  # 기존 최상위 노드 지표 반환

    # 맨 앞의 데이터를 보는 메소드
    def peek(self):
        if self.is_empty():
            return "Stack is empty!"
        
        return self.head.data

    # 스택이 비었는지 안 비었는지 여부 반환하는 메소드
    # isEmpty 기능 구현
    def is_empty(self):
        return self.head is None  # 비어있으면 True 반환

 

• 큐 : 가장 먼저 들어간 자료가 가장 먼저 나오는 자료구조, FIFO
  - 끝과 시작 노드를 가리키는 head와 tail 필요 
  - enqueue(data) : 맨 뒤에 데이터 추가하기
  - dequeue() : 맨 앞의 데이터 뽑기
  - peek() : 맨 앞의 데이터 보기
  - isEmpty(): 큐가 비었는지 안 비었는지 여부 반환

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 큐 클래스 선언
class Queue:
    def __init__(self):  # head와 tail 초기화
        self.head = None
        self.tail = None

    # 큐에 값을 넣는 메소드
    def enqueue(self, value): 
        new_node = Node(value)  # 전달받은 값으로 새로운 노드 생성
        if self.isEmpty():  # 비어있는 큐인지 확인 -> 비어있다면 head와 tail이 모두 None이기 때문에
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node  # 기존 tail의 다음이 새로운 노드를 가리키도록 지정
        self.tail = new_node  # tail을 새로운 노드로 업데이트

    # 큐에서 값을 뺴는 메소드
    def dequeue(self):
        if self.isEmpty():
            return "Queue is empty!"

        delete_node = self.head  # 삭제하려는 기존 head가 가리키는 노드 저장
        self.head = self.head.next  # head값을 기존 head 다음 노드를 가리키도록 업데이트

        return delete_node.data

    # 큐에서 최상위값을 보는 메소드
    def peek(self):
        if self.isEmpty():
            return "Queue is empty!"

        return self.head.data

    # 큐가 비어있는지 확인하는 메소드
    def isEmpty(self):
        return self.head is None

 

• 해쉬 테이블 : 키를 값에 매핑하는 구조인, 연관 배열 추가에 사용되는 자료구조 -> 해시 함수를 사용해 index와 bucket(또는 slot)의 배열로 계산, 데이터의 검색과 저장이 아주 빠름(why? 모든 값을 조회하지 않고 key로 바로 찾기 때문에)
  - 딕셔너리도 내부적으로 배열 사용
  - 딕셔너리의 put(key, value) : key에 value 저장하기
  - 딕셔너리의 get(key) : key에 해당하는  value 가져오기
  - 해시 함수 : 임의의 길이를 갖는 메시지를 입력해 고정된 길이의 해쉬값을 출력하는 함수 -> 파이썬에서 hash(object) 함수 제공
  - 해시함수 결과값을 배열의 길이로 나눈 나머지 값으로 배열 내부의 인덱스로 연결시킨다.

class Dict:
    def __init__(self):
        # items = [None, None, None, None, None, None, None, None]
        self.items = [None] * 8

    # 해당 key에 value를 저장하는 메소드
    def put(self, key, value):
        index = hash(key) % len(self.items)  # 키에 대해 해시함수로 임의의 수를 만들고 배열의 길이로 나눈 나머지를 인덱스로 사용
        self.items[index] = value  # 해당 인덱스에 값 추가

    # 해당 인덱스를 가진 items의 원소 반환
    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index]


my_dict = Dict()
my_dict.put("test", 3)
print(my_dict.get("test"))  # 3이 반환되어야 합니다!

• 충돌(collision) : 같은 array의 index로 매핑이 되어서 데이터를 덮어 써버리는 결과가 발생하는 경우
  - 해결 방법 1) 링크드 리스트를 이용해 체이닝 구현(Chaining)
  - 해결 방법 2) 배열의 다음 남는 공간에 넣는 개방 주소법(Open Addressing)

# 체이닝 방법
# 동일한 인덱스로 나올 때 각 튜플(key, value)을 서로 이어줌
class LinkedTuple:
    def __init__(self):
        self.items = []

    def add(self, key, value):
        self.items.append((key, value)) # 하나의 인덱스에 튜플을 추가 [1, 2, 3, (fast, '빠름')]

    def get(self, key):
        for k, v in self.items:
            if k == key:
                return v


class LinkedDict:
    def __init__(self):
        self.items = []
        # 각 인덱스 별 LinkedTuple 생성
        for i in range(8):
            self.items.append(LinkedTuple())

    # 해당하는 index의 LinkedTuple에 새로운 값을 추가
    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)
    # 만약, 입력된 key가 "fast" 인데 index 값이 2가 나왔다.
    # 현재 self.items[2] 가 [("slow", "느린")] 이었다!
    # 그렇다면 새로 넣는 key, value 값을 뒤에 붙여주자!
    # self.items[2] == [("slow", "느린") -> ("fast", "빠른")] 이렇게! 

    # index의 LinkedTuple 에 값을 가져옴
    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index].get(key)
    # 만약, 입력된 key가 "fast" 인데 index 값이 2가 나왔다.
    # 현재 self.items[2] 가 [("slow", "느린") -> ("fast", "빠른")] 이었다!
    # 그렇다면 그 리스트를 돌면서 key 가 일치하는 튜플을 찾아준다.
    # ("fast", "빠른") 이 일치하므로 "빠른" 이란 값을 돌려주자!