[스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 3주차

• 정렬

• 정렬 : 데이터를 순서대로 나열하는 방법
• 버블 정렬: 첫번째 자료와 두번째 자료, 세번째 자료와 네번째 자료,... 이런 식으로 (마지막 - 1) 번째 자료와 마지막 자료를 비교하여 자료를 정렬하는 방식

input = [4, 6, 2, 9, 1]

# 1번째 : [4, 6, 2, 9, 1]
#              → → → →  비교!
# 2번째 : [4, 2, 6, 1, 9]
#              → → → 비교!
# 3번째 : [2, 4, 1, 6, 9]
#              → → 비교!
# 4번째 : [2, 1, 4, 6, 9]
#              →  비교!

def bubble_sort(array):
    n = len(array)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j+1] = array[j+1], array[j]

    return


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

print(sorted(input))

• 선택 정렬 : 선택해서 정렬

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)

    for i in range(n - 1):  # 맨 마지막에 하나 남은 원소 비교 안하니까
        min_index = i
        for j in range(n - i):  # 하나씩 줄어가는 구조
            if array[i + j] < array[min_index]:
                min_index = i + j # i + j = 현재 시도해 보고 있는 인덱스
        array[i], array[min_index] = array[min_index], array[i]
    return


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

• 삽입 정렬 : 전체에서 하나씩 올바른 위치에 "삽입" 하는 방

input = [4, 6, 2, 9, 1]


# 1단계 [4 6 2 9 1]
#       <-
# 2단계 [4 6 2 9 1]
#       <-<-
# 3단계 [2 4 6 9 1]
#       <-<-<-
# 4단계 [2 4 6 9 1]
#       <-<-<-<-

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break

    return


insertion_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

• 병합 정렬 : 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    array_c = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            array_c.append(array1[array1_index])
            array1_index += 1
        else:
            array_c.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            array_c.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            array_c.append(array1[array1_index])
            array1_index += 1
    # 이 부분을 채워보세요!
    return array_c


print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

 

• 병합 정렬 + 분할 정복 : 제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

array = [5, 3, 2, 1, 6, 8, 7, 4]


# [5] [5] -> [3,5]
# [2] [1] -> [1,2]
# [6] [8] -> [6,8]
# [7] [4] -> [4,7]
#
# ->
# [3,5] [1,2] -> [1,2,3,5]
# [6,8] [4,7] -> [4,6,7,8]
#
# ->
# [1,2,3,5] [4,6,7,8] -> [1,2,3,4,5,6,7,8]
#
# [1,2,3,4,5,6,7,8] 길이 N
# 1 단계 : [1,2,3,5] [4,6,7,8] 길이 N/2 2개 비교하면서 합친다. N/2 * 2 = N
# 2 단계 : [3,5] [1,2] -> [1,2,3,5] 길이 N/4 2개 비교
# [6,8] [4,7] -> [4,6,7,8] 길이 N/4 2개 비교 -> 길이 N/4 * 4 = N
# k 단계 : [6] [8]
# N/2^k = 1 -> k = log2N
# 즉, k단계만큼 반복하는데 각각 단계는 0(N) 시간 복잡도를 가진다.
# 즉, log2N * O(N) -> O(NlogN)

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    print(array)
    print('left_array', left_array)
    print('right_array', right_array)
    return merge(left_array, right_array)

    return array


def merge(array1, array2):  # merge O(N)
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge_sort(array))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

• 스택 : 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조, 넣은 순서를 쌓아둔다!

• 빨래통! 가장 먼저 넣은 빨래는 가장 나중에 나온다. 후입선출 Last In First Out LIFO
• 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

    # 맨 위에 데이터 넣기
    def push(self, value):
        new_head = Node(value)
        new_head.next = self.head
        self.head = new_head

    # 맨 위의 데이터 보기 및 삭제
    def pop(self): # 가장 위에서 뽑은 데이터를 반환해줘야함
        if self.is_empty():
            return "Stack is Empty"
        delete_head = self.head # 그래서 해드 값을 다른 변수에 저장
        self.head = self.head.next
        return delete_head  # 출력

    # 가장 꼭대기 있는 데이터 보기
    def peek(self):
        if self.is_empty():
            return "Stack is Empty"
        return self.head.data

    # 스택이 비었는지 안 비었는지 여부
    def is_empty(self):
        return self.head is None # 비었다면 None 이니까 True 반환


stack = Stack()
stack.push(3)
print(stack.peek())
stack.push(4)
print(stack.peek())
print(stack.pop().data)
print(stack.peek())
print(stack.is_empty())
print(stack.pop().data)
print(stack.is_empty())

• 큐 : 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조, 순서대로 처리되어야하는 일에 필요

• 놀이공원! 가장 처음에 줄 선 사람이 가장 빨리 나오고 가장 마지막에 선 사람이 가장 늦게 나온다. 
  선입선출 First In First Out FIFO
• enqueue(data) : 맨 뒤에 데이터 추가
• dequeue() : 맨 위의 데이터 뽑기
• peek() : 맨 위의 데이터 보기
• isEmpty() : 큐가 비었는지 안 비었는지 여부 반환

※ 스택과는 다르게 큐는 끝과 시작의 노드를 전부 가지고 있어야 하므로, self.head 와 self.tail 을 가지고 시작!

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


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    # 맨 뒤에 데이터 추가
    def enqueue(self, value):
        new_node = Node(value)  # [3] 새로운 노드 생성
        if self.is_empty():  # head, tail 이 None 인지 아닌지에 따른 예외 처리
            self.head = new_node  # 새로운 노드가 들어오면 head 이자
            self.tail = new_node  # tail 이다. 딱 하나만 있으면 head 이자 tail 이다.
            return

        self.tail.next = new_node  # 현재 tail 의 다음 노드가 new_node 로
        self.tail = new_node  # 현재 tail 을 new_node 로 변경

    # 맨 위의 데이터 뽑기
    def dequeue(self):
        if self.is_empty():
            return "Queue is Empty"
        delete_head = self.head  # 반환할 사라질 head 값을 다른 변수에 넣어넣고
        self.head = self.head.next  # head 값에 head 의 다음 값을 대입하고
        return delete_head.data  # 기존 head 값 반환

    # 맨 위의 데이터 보기
    def peek(self):
        if self.is_empty():
            return "Queue is Empty"
        return self.head.data

    # 큐가 비었는지 안 비었는지 여부 반환
    def is_empty(self):
        return self.head is None

queue = Queue()
queue.enqueue(3)
print(queue.peek())
queue.enqueue(4)
print(queue.peek())
queue.enqueue(5)
print(queue.peek())
print(queue.dequeue())
print(queue.peek())
print(queue.is_empty())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print(queue.is_empty())

• 해쉬

• 해쉬 테이블 : 컴퓨터에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조...
  해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다...
  데이터를 다루는 기법 중에 하나로 "데이터의 검색과 저장이 아주 빠르게 진행" 된다.                                                  (파이썬 딕셔너리와 같다고 보면 된다.)
• 해쉬 함수 : 임의의 길이를 갖는 메세지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수

-  딕셔너리 구

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

    # 딕셔너리에 새로운 key 와 value 를 추가
    def put(self, key, value):
        index = hash(key) % len(self.items) # key 를 해싱해서 임의의 문자열로 만들고 그 값을 현재 배열의 최대 길이로 % 연산

        self.items[index] = value
        return

    # key 값에 따른 value 값을 얻기 월하는 메소드
    def get(self, key):
        index = hash(key) % len(self.items)  # key 를 해싱해서 임의의 문자열로 만들고 그 값을 현재 배열의 최대 길이로 % 연산
        return self.items[index] # key 로 이용해서 반환


my_dict = Dict()
my_dict.put("test", 3) # test 를 key 값으로 3 을 value 에 저장하고
print(my_dict.get("test")) # test 라는 key 값으로 value 가져와 출력

- 충돌

class LinkedTuple:
    def __init__(self):
        self.items = list()

    def add(self, key, value):
        self.items.append((key, value))

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


class LinkedDict:
    def __init__(self):
        self.items = []
        for i in range(8):
            self.items.append(LinkedTuple())

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)
        return

    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index].get(key)

- 출석체크

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]


def get_absent_student(all_array, present_array):
    dict = {}
    for key in all_array:
        dict[key] = True  # 아무 값이나 넣어도 상관 없습니다! 여기서는 키가 중요한거니까요

    for key in present_array:  # dict에서 key 를 하나씩 없앱니다
        del dict[key]

    for key in dict.keys():  # key 중에 하나를 바로 반환합니다! 한 명 밖에 없으니 이렇게 해도 괜찮습니다.
        return key


print(get_absent_student(all_students, present_students))

print("정답 = 예지 / 현재 풀이 값 = ",get_absent_student(["류진","예지","채령","리아","유나"],["리아","류진","채령","유나"]))
print("정답 = RM / 현재 풀이 값 = ",get_absent_student(["정국","진","뷔","슈가","지민","RM"],["뷔","정국","지민","진","슈가"]))

============================================================================================

출처 : [스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 3주차

============================================================================================