[알고리즘] 스파르타 코딩 : 알고리즘 - 3주차

정렬 : 데이터를 순서대로 나열하는 방법

 

1, 버블 정렬 :

1번째 원소, 2번째 원소 비교

2번째 원소, 3번째 원소 비교...

...

(N-1)번째 원소, N번째 원소 비교

 

버블 정렬 구현

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

#버블 정렬
# [4, 6, 2, 9, 1]
# 4 < 6 : 그대로 [4, 6, 2, 9, 1]
# 6 > 2 : 교환  [4, 2, 6, 9, 1]
# 6 < 9 : 그대로 [4, 2, 6, 9, 1]
# 9 > 1 : 교환 [4, 2, 6, 1, 9]

# 맨 뒤에 제외 다시 반복
# 4 > 2 : 교환 [2, 4, 6, 1, 9]
# 4 < 6 : 그대로 [2, 4, 6, 1, 9]
# 6 > 1 : 교환 [2, 4, 1, 6, 9]

# 맨 뒤에 제외 다시 반복
# 2 < 4 : 그대로 [2, 4, 1, 6, 9]
# 4 > 1 : 교환 [2, 1, 4, 6, 9]

# 맨 뒤에 제외 다시 반복
# 2 > 1 : 교환 [1, 2, 4, 6, 9]

# 버블 정렬
# O(N제곱)
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 array


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

---

2, 선택 정렬 : 선택해서 정렬

0~N까지 가장 작은 원소 찾아서 앞으로 보내기

1~N까지 가장 작은 원소 찾아서 앞으로 보내기

...

N-1~N까지 가장 작은 원소 찾아서 앞으로 보내기

 

선택 정렬 구현

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

# 선택 정렬
# [4, 6, 2, 9, 1]
# 제일 작은 거 찾아서 앞으로 옮기기
# [1, 6, 2, 9, 4]

# 맨 앞자리 제외 제일 작은 거 찾아서 앞으로 옮기기
# [1, 2, 6, 9, 4]

# 맨 앞자리 제외 제일 작은 거 찾아서 앞으로 옮기기
# [1, 2, 4, 9, 6]

# 맨 앞자리 제외 제일 작은 거 찾아서 앞으로 옮기기
# [1, 2, 4, 6, 9]


# 선택 정렬
# 선택해서 정렬하기
# O(N재곱)
def selection_sort(array):
    n = len(array)

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

    return array



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

---

3, 삽입 정렬 : 하나씩 올바른 위치에 삽입

0번째 원소 삽입

1번째 원소 삽입 및 정렬

2번째 원소 삽입 및 정렬

...

N번째 원소 삽입 및 정렬

 

삽입 정렬 구현

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

# 삽입 정렬
# [4, 6, 2, 9, 1]
# 1번째 원소 6 입장 및 비교
# 4 < 6 : 그대로 [4, 6, / 2, 9, 1] break

# 2번째 원소 2 입장 및 비교
# 6 > 2 : 교환 [4, 2, 6, / 9, 1]
# 4 > 2 : 교환 [2, 4, 6, / 9, 1]

# 3번째 원소 9 입장 및 비교
# 6 < 9 : 그대로 [2, 4, 6, 9, / 1] break

# 마지막 원소 1 입장 및 비교
# 9 > 1 : 교환 [2, 4, 6, 1, 9]
# 6 > 1 : 교환 [2, 4, 1, 6, 9]
# 4 > 1 : 교환 [2, 1, 4, 6, 9]
# 2 > 1 : 교환 [1, 2, 4, 6, 9]


# 삽입 정렬
# O(N제곱)
def insertion_sort(array):
    n = len(array)

    for i in range(1, n):
        for j in range(i):
            if array[i-j] < array[i-j-1]:
                array[i-j], array[i-j-1] = array[i-j-1], array[i-j]
            # 버블 정렬과 선택 정렬엔 break없음
            # 비교 횟수 줄어듦
            else:
                break
    return array


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

---

4, 병합 정렬 : 배열을 앞/뒤로 나눈 뒤 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘(재귀)

ㄴ분할 정복 개념 사용! : 문제를 작은 문제 2개로 분리하고 각각 해결한 다음 결과 모아서 원래 문제 해결하는 전략

 

병합 정렬 구현

array = [5, 3, 2, 1, 6, 8, 7, 4]
# 병합 정렬

# 길이 1인 배열부터 mregr해서 정렬 시작
#[5], [3] -> [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]

# 병합 정렬
# O(NlogN)
# [1, 2, 3, 4, 5, 6, 7, 8]          길이 N
#->[1, 2, 3, 5], [4, 6, 7, 8]       길이 N / 2 * 2 = N
#->[3, 5], [1, 2], [6, 8], [4, 7]   길이 N / 4 * 4 = N
#... 길이 1일 때까지
#=> N/2의 k승 = 1
#=> logN
# k단계만큼 반복, 각 단계는 O(N) 시간 복잡도
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:])

    return merge(left_array, right_array)


# O(N)
def merge(array1, array2):
    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] 가 되어야 합니다!

---

스택, 큐 :

---

스택 : 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조(빨래 바구니)

 

스택 구현

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

    # pop 기능 구현
    def pop(self):
        if self.is_empty():
            return "Stack is Empty"

        delete_data = self.head
        self.head = self.head.next

        return delete_data

    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


stack = Stack()
stack.push(3)
stack.push(4)
print(stack.peek())

---

파이썬에서는 스택 이렇게 사용

stack = []            # 빈 스택 초기화
stack.append(4)       # 스택 push(4)
stack.append(3)       # 스택 push(3)
top = stack.pop()     # 스택 pop
print(top)            # 3!

---

스택 문제

Q. 수평 직선에 탑 N대를 세웠습니다. 

모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 

발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 

또한 ,한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

이 때, 맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때

각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 반환하시오.

A.

top_heights = [6, 9, 5, 7, 4]

# <- <- <- <- <-
# 6  9  5  7  4
# 7 > 4, 7은 4번째 탑
# [0, 0, 0, 0, 4]

# <- <- <- <-
# 6  9  5  7
# 9 > 7, 9은 2번째 탑
# [0, 0, 0, 2, 4]

# <- <- <-
# 6  9  5
# 9 > 5, 9은 2번째 탑
# [0, 0, 2, 2, 4]

# <- <-
# 6  9
# [0, 0, 2, 2, 4]

# <-
# 6
# [0, 0, 2, 2, 4]

# [6, 9, 5, 7, 4]가 끝에서부터 하나씩 사라짐 =>  스택 이용

# O(N제곱)
def get_receiver_top_orders(heights):
    result = [0] * len(heights)

    while heights:
        height = heights.pop()

        for index in range(len(heights) - 1, 0, -1):
            if heights[index] > height:
                # 스택에서 하나를 ㄹ뺀 길이 = 배열의 인덱스
                result[len(heights)] = index + 1
                break

    return result


print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

---

큐 : 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형 구조(놀이공원 줄서기)

 

큐 구현

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)

        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.is_empty():
            return "Queue is Empty"

        delete_node = self.head
        self.head = self.head.next

        return delete_node.data

    def peek(self):
        return self.head.data

    def is_empty(self):
        return self.head is None


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

---

해쉬 테이블 : 키를 값에 매핑할 수 있는 구조인 연관 배열 추가에 사용되는 자료 구조. 검색과 저장이 빠름

 

충돌 해결법 1 : 체이닝 = Lineked List 이용

충돌 해결법 2 : 개방 주소법 = 배열의 남는 공간에 값 넣기

 

Lineked List를 이용한 해쉬 테이블 구현

# 데이터 추가 시 충돌 발생 해결 방법 1 : Linked List 이용
class LinkedTuple:
    def __init__(self):
        self.items = list()

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

    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))

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

 

해시 테이블 예시

Q. 오늘 수업에 많은 학생들이 참여했습니다.

단 한 명의 학생을 제외하고는 모든 학생이 출석했습니다.

모든 학생의 이름이 담긴 배열과 출석한 학생들의 배열이 주어질 때,

출석하지 않은 학생의 이름을 반환하시오.

 

A.

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


# O(N)
# 해시 테이블 사용하면 시간은 줄지만 공간은 늘어나는구나
def get_absent_student(all_array, present_array):
    # 모든 학생 딕셔너리 만들기
    student_dict = {}
    for key in all_array:
        student_dict[key] = True    # 공강 복잡도도 O(N)
    # 출석한 학생 삭제하기
    for key in present_array:
        del student_dict[key]

    # 남은 학생 출력
    for key in student_dict.keys():
        return key


print(get_absent_student(all_students, present_students))