<알고리즘, 자료구조 3주차> 정렬, 스택, 큐, 해쉬

학습 내용 요약

1. 정렬
2. 스택과 큐
3. 해쉬

1. 정렬

1) 정의
데이터를 순서대로 나열하는 방법. 컴퓨터에서 정렬을 하기 위해서는 그 과정을 명확하게 알려줘야 한다.

2) 버블 정렬
(1) 설명
가장 쉽고 직관적인 정렬. 앞에서 차례대로 두 개씩 비교해서 작으면 앞, 크면 뒤에 놓는 과정을 데이터 끝까지 반복해서 정렬시킨다. 주의할 점은 한 번 반복한 후 정렬된 맨 마지막 수는 제외하고, 그 다음 반복을 시행해야 한다는 것이다. 이 방식은 이중 반복문이 사용되어 N^2만큼의 시간복잡도가 걸린다.

(2) 예시
[4,8,2,1,5] -> [4,2,1,5,8] -> [2,1,4,5,8] -> [1,2,4,5,8]

def bubble_sort(array):
    list_length = len(array)
    for i in range(list_length-1):
        for j in range(list_length-i-1): # 맨 마지막 수 제외하고 비교 반복하기 때문에 i까지 뺌
            if array[j] < array[j+1]:
                pass
            elif array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
            else:
                pass
    return array

3) 선택 정렬
(1) 설명
전체에서 최소값을 선택해서 위치를 변경하고, 처음 수 제외하고 다시 전체에서 최소값을 선택해서 위치를 변경시키는 과정을 반복한다. 이 방식도 이중 반복을 하기 때문에 N^2의 시간복잡도가 걸린다.

(2) 예시
[2,7,4,9,1] -> [1,7,4,9,2] -> [1,2,4,9,7] -> [1,2,4,7,9]

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
        array[i], array[min_index] = array[min_index], array[i]

    return

4) 삽입 정렬
(1) 설명
전체에서 하나씩 올바른 위치에 넣는 방식. 기존 정렬된 배열에 새 데이터가 들어왔을 때, 배열의 마지막 수보다 크면 맨 뒤에 둔다. 배열의 수 중 데이터보다 큰 수가 있다면 차례대로 비교하며 위치를 변경한다. 이때 이미 정렬된 배열은 정렬 상태를 유지한 채 움직인다. 즉, 필요할 때만 위치를 변경해서 정렬한다.

(2) 예시
[2,4] - 6 -> [2,4,6] - 1 -> 차례대로 비교 -> [1,2,4,6] - 9 -> [1,2,4,6,9]

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 # 마지막 수보다 크면 비교 안하고 반복문 빠져나감

5) 병합 정렬
(1) 설명
병합 정렬을 위해서는 분할 정복이라는 개념이 필요하다. 분할 정복이란 문제를 작은 두 개의 문제로 나누고 각 문제를 해결한 뒤, 결과를 모아서 원래 문제를 해결하는 방법이다. 이렇게 원소가 하나만 남을 때까지 나누고, 비교 후 병합 및 정렬을 반복해서 원래 배열 형태로 만든다. 이때 분할 및 병합 과정은 반복해서 발생하기에 재귀함수를 이용하면 좋다.

(2) 예시
[5,3,2,1,6,8,7,4] -> [5,3,2,1],[8,6,7,4] -> [5,3],[2,1],[8,6],[7,4] -> [5],[3],[2],[1],[8],[6],[7],[4]
=> [3,5],[1,2],[6,8],[4,7] -> [1,2,3,5],[4,6,7,8] -> [1,2,3,4,5,6,7,8]

# 병합 정렬 함수
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)

# 병합하는 함수
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

2. 스택과 큐

1) 스택
(1) 설명
한 쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조. LIFO(Last In First Out) 방식이다. 스택은 데이터를 넣고 빼는 즉, 삽입과 삭제가 잦은 자료구조다. 이는 연결리스트와 유사하게 구현 가능하다.

그럼 왜 이런 자료구조를 사용할까? 그것은 순서가 필요한 경우가 있기 때문이다. 즉, 데이터를 넣는 순서를 따지기 위함이다. 예를 들어 ctrl+z 기능으로 설명할 수 있겠다.

(2) 제공 기능

• put(data): 맨 위(세로)/맨 앞(가로)에 데이터 넣기
• pop(): 맨 위(세로)/맨 앞(가로) 데이터 빼기
• peek(): 맨 위(세로)/맨 앞(가로) 데이터 보기
• is_empty(): 비었는지 아닌지 여부 확인

(3) 예시 코드

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  # 새 노드 다음을 head로 설정
        self.head = new_head       # 새 노드를 head로 변경

    # pop 기능 구현
    def pop(self):
        if self.is_empty():
            return '스택이 비어 있다.'
        delete_head = self.head    # head를 지울 노드로 저장
        self.head = self.head.next # head 다음을 head로 변경
        return delete_head.data

    def peek(self):
        if self.is_empty():
            return '스택이 비어 있다.'
        return self.head.data

    # is_empty 기능 구현
    def is_empty(self):
        return self.head is None

2) 큐
(1) 설명
한 쪽으로 데이터를 넣고 다른 쪽으로 데이터를 빼는 자료구조. FIFO(First In First Out) 방식이다. 스택과 마찬가지로 연결리스트와 유사하게 구현 가능한데, 시작과 끝을 모두 갖고 있어야 한다는 점이 다르다.

왜 이런 자료구조가 필요할까? 이유는 순서대로 처리할 경우가 필요하기 때문이다.

(2) 제공 기능

• enqueue(data): 맨 위(세로)/맨 뒤(가로)에 데이터 넣기
• dequeue(): 맨 밑(세로)/맨 앞(가로) 데이터 빼기
• peek(): 맨 밑(세로)/맨 앞(가로) 데이터 보기
• is_empty(): 비었는지 아닌지 여부 확인

(3) 예시 코드

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 '큐는 비었네'

        delete_node = self.head
        self.head = self.head.next
        return delete_node.data

    def peek(self):
        if self.is_empty():
            return '큐는 비었네'
        return self.head.data

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

3. 해쉬

1) 설명
해쉬 테이블은 '키', '데이터'를 저장해서 즉각적으로 데이터를 받아오고 업데이트하는 자료구조. 이는 딕셔너리와 유사한 형태이다. 시간복잡도는 효율적일 수 있지만, 공간을 많이 차지하기에 공간복잡도는 비효율적인 편이다.

해쉬 함수는 임의의 길이의 메시지를 입력해 고정된 길이의 해쉬값을 출력하는 함수다. 파이썬에서는 hash(object)로 제공한다.

해쉬 테이블은 '키'를 해쉬 함수를 통해 임의의 값으로 바꾸고, 이를 배열의 인덱스로 변환해 해당하는 값의 데이터를 저장한다.

2) 사용
해쉬 함수의 형태롤 보면 다음과 같다.

hash("fast")
-146084012848775433
hash("slow")
7051061338400740146

물론 이를 그대로 쓸 수 없으니 값을 배열의 길이로 나눈 나머지를 활용한다. 만약, 배열의 길이가 6이면, 나머지는 0~5가 나오고 이는 인덱스 번호로 쓸 수 있다.
※ 딕셔너리는 내부적으로 배열을 사용한다.

딕셔너리에 필요한 함수

• put(key,value): key에 value 저장
• get(key): key에 해당하는 value 가져오기
• index = hash(key) % len(self.items)

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

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

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

3) 충돌
만약, index에 해당하는 숫자가 같은 숫자가 나오면 배열의 같은 인덱스의 값을 덮어버린다. 이를 충돌이라고 한다.

이를 해결하는 방법에는 두 가지 정도가 있다.

• 체이닝: 연결리스트를 이용해 각 값을 키와 함께 노드로 만듦
• 개방주소법: 배열을 순차적으로 돌며 다음 남는 공간에 할당

• 체이닝 구현 코드

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(6):
            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)

기존에 3번째에 키와 값이 있는데 또 3번째가 나온다면, [(키,값) -> (키,값)] 이렇게 둘을 연결지어 주는 것이다.

그리고 같은 인덱스 번호에서 데이터를 찾는다고 하면, 키가 일치하는 값을 반환한다.

즉, 위와 같은 형태가 되는 것이다.

어렵거나 완전히 이해 못한 내용
사실 정렬은 아직 완전히 이해 못했다. 개념을 명확하게 이해 못해서 코드로 구현하는 것도 어렵다. 반복문의 범위가 왜 그렇게 되는지 사실 잘 모르겠다.

해쉬도 반 정도만 이해한 느낌이다. 딕셔너리의 형태이고, 배열과 함께 활용한다는 것까지 알겠는데, 충돌 해결법의 체이닝은 구현하는 연습을 더 해봐야 분명하게 흐름을 이해할 수 있을 것 같다.

참고자료
https://devuna.tistory.com/22(스택, 큐 차이)