혼자 공부 - 22.11.13

자라나는 ㅇㅅㅇ개발자·2022년 11월 13일
0

응애나애기개발자

목록 보기
2/5

스택, 큐

데이터가 들어가고 나오는 곳이 정해져 있는 자료구조


해쉬

알고리즘을 통해 문자열을 고정된 길이의 데이터로 만들어준다.


정렬

데이터를 순서대로 나열하는 방법
데이터를 조금 더 효율적으로 탐색할 수 있게 해준다.

버블 정렬(Bubble Sort)

자료를 차례대로 비교, 교환 하면서 정렬하는 방식.
여러번 반복해야 한다.


예시 :
[4, 6, 2]
-> 0,1번째 인덱스 값 비교 - 그대로
[4, 6, 2]
-> 1,2번째 인덱스 값 비교 - 교환
[4, 2, 6]
-> 다시 처음부터 0,1번째 인덱스 값 비교 - 교환
[2, 4, 6]
-> 1,2번째 인덱스 값 비교 - 그대로
[2, 4, 6]

파이썬에서 자료를 교환하는 방법

a, b = b, a

연습문제 - 버블 정렬을 이용하여 오름차순으로 배열하기

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


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] 가 되어야 합니다!

선택 정렬

이중 반복문을 사용해야 한다.

예시 :
[4, 6, 2]
-> 0,1,2 인덱스 전부 비교, 가장 작은 수를 0번째 인덱스와 교체
[2, 6, 4]
-> 1,2 인덱스 비교, 가장 작은 수를 1번째 인덱스와 교체
[2, 4, 6]


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


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] 가 되어야 합니다!

삽입 정렬

전체에서 하나씩 올바른 위치에 삽입하는 방식
필요할 때만 위치를 변경하므로 더 효율적인 방식


예시 :
[4, 6, 2]
-> 하나씩 가져와서 배열한다.
[4, 6, 2]
-> 6을 가져와서 4와 비교 - 그대로
[4, 6, 2]
-> 2를 가져와서 6과 비교 - 교체, 4와 비교 - 교체
[2, 4, 6]

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


def insertion_sort(array):
    n = len(array)
    for i in range(1, 5):  # 0번 인덱스는 정렬되어있다 생각하기 때문에 1번 인덱스부터 시작
        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] 가 되어야 합니다!

병합 정렬(merge)

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


예시 :
a = [1, 2, 3, 5], b = [4, 6, 7, 8], c = []
-> a와 b의 각 앞 숫자를 비교하여 작은 숫자를 c에 넣는다
a = [1, 2, 3, 5], b = [4, 6, 7, 8], c = [1]
-> 반복
a = [1, 2, 3, 5], b = [4, 6, 7, 8], c = [1, 2]
-> 반복
a = [1, 2, 3, 5], b = [4, 6, 7, 8], c = [1, 2, 3]
-> 반복
a = [1, 2, 3, 5], b = [4, 6, 7, 8], c = [1, 2, 3, 4]
-> 반복
a = [1, 2, 3, 5], b = [4, 6, 7, 8], c = [1, 2, 3, 4, 5]
-> 반복
...
a = [1, 2, 3, 5], b = [4, 6, 7, 8], c = [1, 2, 3, 4, 5, 6, 7, 8]

연습문제

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


def merge(array1, array2):
    array_c = []  # 새로운 값을 받을 어레이
    array1_index = 0  # a에서 비교하기 위해 끄집어낼 인덱스
    array2_index = 0  # b에서 비교하기 위해 끄집어낼 인덱스
    while array1_index < len(array1) and array2_index < len(array2):  # 어레이의 길이보다 짧아질 때 까지
        if array1[array1_index] < array2[array2_index]:  # a에서 가져온 값이 b에서 가져온 값보다 작다면
            array_c.append(array1[array1_index])  # array_c에 그 값을 넣어라
            array1_index += 1  # 그리고 다음 인덱스로 넘어가
        else:
            array_c.append(array2[array2_index])
            array2_index += 1
    if array1_index == len(array1):  # a를 모두 비웠다면 = b가 남았다면
        while array2_index < len(array2):  # b의 길이보다 작을 때까지
            array_c.append(array2[array2_index])
            array2_index += 1
    if array2_index == len(array2):  # b를 모두 비웠다면 = a가 남았다면
        while array1_index < len(array1):  # a의 길이보다 작을 때까지
            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] 가 되어야 합니다!

병합 정렬(mergeSort)

위에 방법은 정렬된 배열을 합치는 방법
분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

mergeSort도 재귀 함수로 활용 가능하다.
MergeSort(시작점, 끝점)이라고 한다면,
MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N)) 라고 할 수 있다.

코드로 정리해본다면

def merge_sort(array):
    if len(array) <= 1:		# 재귀 함수 이므로
        return array		# 반드시 탈출 조건 필요
    mid = (0 + len(array)) // 2
    left_array = merge_sort(array[:mid])  # 왼쪽 부분을 정렬하고
    right_array = merge_sort(array[mid:]) # 오른쪽 부분을 정렬한 다음에
    merge(left_array, right_array)        # 합치면서 정렬하면 됩니다!

재귀함수에서 중요한 탈출 조건을 써줘야 한다.
문자열의 길이가 1보다 작거나 같을 때 -> 무조건 정렬된 상태

스택

Last in First Out -> LIFO 구조 (빨래통)
-> 넣은 순서를 쌓아두는 형태, 되돌리기 기능에 사용

스택의 구현 기능

push(data) : 맨 앞에 데이터 넣기
pop() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기

push(data)

    def push(self, value):
        new_head = Node(value)
        new_head.next = self.head
        self.head = new_head
        return

pop

    def pop(self):
        if self.is_empty():
            return "Stack is Empty"
        delete_head = sefl.head
        self.head = self.head.next
        return delete_head

peek

    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

실제 코드에서는 파이썬의 list를 이용해 스택으로 사용한다.

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

append는 배열의 맨 뒤로 들어간다.

First In First Out -> FIFO 구조(놀이기구)
-> 한쪽 끝에 자료를 넣고, 반대쪽에서 자료를 빼는 선형구조
가게에 주문이 들어왔을 때 처럼 순서대로 들어온 것들을 먼저 처리해야 할 때

enqueue(data) : 맨 뒤에 데이터 추가하기 
dequeue() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기

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

enqueue -> tail 뒤에 붙이기

    def enqueue(self, value):       # 노드 안이 None인지, 아닌지에 따라 예외처리를 우선 해줘야 한다.
        new_node = Node(3)          # new node 생성
        if self.is_empty():         # 비어있다면
            self.head = new_node    # head는 new
            self.tail = new_node    # tail도 new
            return

        self.tail.next = new_node   # [4](head) -> [2](tail) -> [3](new)
        self.tail = new_node        # [4](head) -> [2] -> [3](tail)
        return

dequeue -> head 뽑아내기

    def dequeue(self):              # head와 tail을 바꿔준 후 원래의 head를 반환
        if self.is_empty():
            return "Queue is Empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data     # 임시로 여기에 .data

peek -> head의 데이터를 반환

    def peek(self):
        if self.is_empty():
            return "Queue is Empty"
        return self.head.data       # 임시로 여기에 .data

isEmpty

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

해쉬

해쉬 테이블 : 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.

해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값(나눈 나머지)을 출력하는 함수이다

예제

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

    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]


my_dict = Dict()
my_dict.put("test", 3)
print(my_dict.get("test"))

:
Item 안에 None 이라는 인덱스 8개가 있다고 할 때,

put :
index의 위치는 hash(key)로 무작위 숫자를 생성 후 배열의 길이로 나눠서 나온 나머지 값으로 위치를 정하고 -> key
그 인덱스 위치에 value를 저장한다.

get :
index의 위치는 hash(key)로 무작위 숫자를 생성 후 배열의 길이로 나눠서 나온 나머지 값으로 위치를 정하고 -> key
그 인덱스 위치에 value값을 반환한다.

나중에 value 값을 찾기 쉽게 하기 위해 key를 저장해 두는 것이 좋다.

index의 위치가 중복돼서 충돌이 일어날 수 있다.
-> 원래 값이 사라지게됨
이를 해결하는 방법 중 하나가 링크드 리스트(chaining)

key 중복에 의한 충돌 방지 1 - 체이닝(Chaining)
각 배열에 링크드 리스트를 연결하여 키가 동일하다면 충돌이 일어나지 않도록 그 뒤에(.next)로 연결해주는 기능
get을 사용하면 그 키를 가지고 있는 모든 value들을 반환한다.

key 중복에 의한 충돌 방지 2 - 개방 주소법(Open Addressing)
해당 key에 이미 value가 있다면 그 다음 인덱스로, 거기도 차있다면 그 다음에 값을 넣는 방식

연습문제 - 결석한 학생 찾기

아래 명단에서 출석하지 않은 학생의 이름을 반환하시오

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

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


def get_absent_student(all_array, present_array):
    student_dict = {}               # 학생들을 담는 새로운 딕셔너리
    for key in all_array:           # 전체 학생들을 돌려서
        student_dict[key] = True    # 새로운 딕셔너리 키에 추

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

: 해쉬 테이블은 시간은 빠르지만 공간을 대신 사용하는 자료구조이다.

0개의 댓글