SCC Algorithm 3주차

nathan·2021년 3월 18일
0

SCC Algorithm

목록 보기
6/7
post-thumbnail

[수업목표]
1. 정렬의 다양한 방법과 구현 방법에 대해 배운다.
2. 스택, 큐의 개념과 활용법에 대해 배운다.
3. 해쉬 개념과 활용법에 대해 배운다.

1. 정렬 (Sort)

정렬 : 데이터를 순서대로 나열하는 방법
이진 탐색을 가능하게 하고, 데이터를 효율적으로 탐색할 수 있게 함

컴퓨터에게 정렬을 명령하기 위해서는 정확한 과정을 설명해줘야 한다.

(1) 버블 정렬 (Bubble sort)

버블 정렬 : 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, ... 이런 식으로 (마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [**4, 6**, 2, 9, 1] 
        46을 비교합니다!
        4 < 6 이면 그대로 둡니다.

2단계 : [4, **6, 2,** 9, 1]
           62를 비교합니다!
           6 > 2 이므로 둘을 변경합니다!
       [4, **2, 6**, 9, 1] 이렇게요!

3단계 : [4, 2, 6, 9, 1]
              69를 비교합니다!
              6 < 9 이면 그대로 둡니다.

4단계 : [4, 2, 6, 9, 1]
                 91를 비교합니다!
                 9 > 1 이므로 둘을 변경합니다!
       [4, 2, 6, **1, 9]** 이렇게요!

자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 가장 큰 숫자인 9가 맨 뒤로 왔습니다.
큰 게 나오면 둘의 자리를 변경했으니 가장 맨 뒤에 갔다는 소리입니다!
그러면, 맨 뒷자리를 제외하고 다시 한 번 돌리면 됩니다!

5단계 : [4, 2, 6, 1, 9]
        42을 비교합니다!
        4 > 2 이므로 둘을 변경합니다.
       [**2, 4**, 6, 1, 9] 이렇게요!

6단계 : [2, 4, 6, 1, 9]
           46을 비교합니다!
           4 < 6 이면 그대로 둡니다.

7단계 : [2, 4, 6, 1, 9]
              61을 비교합니다!
              6 > 1 이므로 둘을 변경합니다!
       [2, 4, **1, 6**, 9] 이렇게요!

그러면 이제 두 번째로 큰 숫자인 6이 맨 뒤에서 두번쨰로 왔습니다!
여기까지만 비교하시면 됩니다. 69을 비교할 필요는 없습니다.
다시 한 번 가볼게요!

8단계 : [2, 4, 1, 6, 9]
        24을 비교합니다!
        2 < 4 이면 그대로 둡니다.

9단계 : [2, 4, 1, 6, 9]
           41을 비교합니다!
           4 > 1 이므로 둘을 변경합니다!
       [2, **1, 4**, 6, 9] 이렇게요!

자, 이제 세 번쨰로 큰 숫자인 4가 맨 뒤에서 세번째로 왔습니다!
마지막 비교만 하면 됩니다!

10단계 : [2, 1, 4, 6, 9]
         21을 비교합니다!
         2 > 1 이므로 둘을 변경합니다!
        [**1, 2**, 4, 6, 9] 이렇게요!

자, 모두 정렬이 되었습니다!

이렇듯 버블 정렬을 통해 가장 큰 값이 맨 뒤에 쌓여 정렬된다.

버블 정렬을 코드로 구현하면 아래와 같다.

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


def bubble_sort(array):
    # 이 부분을 채워보세요!
    for j in range(len(array)-1):   # n의 길이만큼 반복
        for i in range(len(array)-1-j): # 맨 뒤 부터 차곡차곡 1개씩은 최댓값이 정렬되기 때문, n의 길이만큼 반복
            if array[i] > array[i+1]:
                array[i], array[i+1] = array[i+1], array[i]

    return array


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

(2) 선택 정렬 (Selection sort)

선택 정렬 : 말 그대로 선택하여 정렬한다.
처음부터 쭉 보면서 가장 작은 값을 선택하여 인덱스 0의 자리로 옮긴다.
인덱스 1의 자리부터 쭉 보면서 가장 작은 값을 선택하여 인덱스 1의 자리로 옮긴다.
인덱스 2의 자리부터 쭉 보면서 가장 작은 값을 선택하여 인덱스 2의 자리로 옮긴다.
... (앞 과정 반복)

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        46291을 차례차례 비교합니다.
	      그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
       [1, 6, 2, 9, 4] 이렇게요!

자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.

2단계 : [1, 6, 2, 9, 4]
           6294를 차례차례 비교합니다.
           그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다!
       [1, 2, 6, 9, 4] 이렇게요!

3단계 : [1, 2, 6, 9, 4]
              694를 차례차례 비교합니다.
              그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다!
       [1, 2, 4, 9, 6] 이렇게요!

4단계 : [1, 2, 4, 9, 6]
                 96을 비교합니다!
                 그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다!
       [1, 2, 4, 6, 9] 이렇게요!

버블 정렬보다 예시의 설명이 짧지만, 실제로 각 배열을 계속해서 탐색하는 방식이기 때문에 이중 반복문이 사용되어 O(N2)의 시간 복잡도를 갖게 된다.

버블 정렬과 또 다른 점은 선택 정렬은 "최솟값"을 찾아서 변경한다는 점이다.
따라서 min_index라는 변수를 통해 각각의 인덱스들과 비교한 후
내부의 반복문이 끝나면 최소 값의 인덱스와 i의 값들을 비교해주면 된다.
(최솟값이 쌓이는 방식이라고 생각하면 된다.)

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]: # index i 에 j를 추가시켜주는 방법으로 반복문 실행                  
                  min_index = j+i   # min_index 라는 변수에 최저값의 index를 저장
                  
        array[i], array[min_index] = array[min_index], array[i]
    return

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

(3) 삽입 정렬 (Insertion sort)

선택 정렬이 전체에서 최솟값을 "선택"하는 것이었다면,
삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입"하는 방식이다.

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,
삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적이라고 볼 수 있다.

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [**4**, 6, 2, 9, 1] 
        4는 현재 정렬되어 있는 부대원입니다. 
			  그럼 이제 새로운 신병인 6을 받습니다.
        4, **6** 이 되는데 4 < 6 이므로 그대로 냅둡니다.
       [**4, 6,** 2, 9, 1] 이렇게요!

자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!

2단계 : [**4, 6,** 2, 9, 1]
        4, 6 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 2를 받습니다.
        4, 6, **2** 가 되는데 6 > 2 이므로 둘을 변경합니다!
        4, **2**, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
       [**2, 4, 6**, 9, 1] 이렇게요!

3단계 : [**2, 4, 6**, 9, 1]
        2, 4, 6 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 9를 받습니다.
        2, 4, 6, **9** 가 되는데 6 < 9 이므로 그대로 냅둡니다.
       [**2, 4, 6, 9**, 1] 이렇게요!

4단계 : [**2, 4, 6, 9**, 1]
        2, 4, 6, 9 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 1을 받습니다.
        2, 4, 6, 9, **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]** 이렇게요!

자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?

1만큼 비교했다가 1개씩 늘어나면서 반복을 하게 된다.

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

def insertion_sort(array):
    # 이 부분을 채워보세요!
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            # print(i-j)
            if array[i - j] < array[i - j - 1]:
                array[i - j], array[i - j - 1] = array[i - j - 1], array[i - j]
            else:
                break   # 이전의 숫자들은 비교할 필요가 없어짐 (선택정렬과 다른점 - 최선의 경우 O(N)의 시간이 걸림)
    return

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

버블 정렬, 선택 정렬, 삽입 정렬은 모두 최악의 상황에서 O(N2)의 시간 복잡도가 걸리지만, 최선의 경우에 "삽입 정렬"은 Ω(N)의 시간이 걸린다.
이유 : 이전의 숫자들은 현재 숫자보다 작을 때 더이상 비교할 필요가 없어진다.(다음 인덱스로 이동)

(4) 병합 정렬 (Merge sort)

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

예를 들어서
A 라고 하는 배열이 1, 2, 3, 5 로 정렬되어 있고,
B 라고 하는 배열이 4, 6, 7, 8 로 정렬되어 있다면
이 두 집합을 합쳐가면서 정렬하는 방법입니다.

[1, 2, 3, 5]  # 정렬된 배열 A
[4, 6, 7, 8]  # 정렬된 배열 B
[] # 두 집합을 합칠 빈 배열 C1단계 : [**1**, 2, 3, 5][**4**, 6, 7, 8] 
        14를 비교합니다!
        1 < 4 이므로 1을 C 에 넣습니다.
     C:[1]2단계 : [1, **2**, 3, 5][**4**, 6, 7, 8] 
        24를 비교합니다!
        2 < 4 이므로 2를 C 에 넣습니다.
     C:[1, 2]3단계 : [1, 2, **3**, 5][**4**, 6, 7, 8] 
        34를 비교합니다!
        3 < 4 이므로 3을 C 에 넣습니다.
     C:[1, 2, 3]3단계 : [1, 2, 3, **5**][**4**, 6, 7, 8] 
        54를 비교합니다!
        5 > 4 이므로 4을 C 에 넣습니다.
     C:[1, 2, 3, 4]3단계 : [1, 2, 3, **5**][4, **6**, 7, 8] 
        56을 비교합니다!
        5 < 6 이므로 5을 C 에 넣습니다.
     C:[1, 2, 3, 4, 5], 이렇게 되면 A 의 모든 원소는 끝났습니다!

그러면 B에서 안 들어간 원소인
       [6, 7, 8] 은 어떡할까요?
하나씩 C 에 추가해주면 됩니다.
     C:[1, 2, 3, 4, 5, 6, 7, 8] 이렇게요!

그러면 A 와 B를 합치면서 정렬할 수 있었습니다.

위의 병합 방법을 어떻게 정렬에 사용할 수 있을까?

답은 바로 분할과 정복(Divide & Conquer)이다.

분할과 정복이란, 문제를 2개의 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결하는 전략이다.

예를 들어, [5, 3, 2, 1, 6, 8, 7, 4]라는 배열이 있고 하자.
반으로 쪼개면 [5, 3, 2, 1][6, 8, 7, 4]로 나눌 수 있다.
또 반으로 쪼개면 [5, 3], [2, 1], [6, 8], [7, 4]로 나눌 수 있고,
다시 또 반으로 쪼개면 [5], [3], [2], [1], [6], [8], [7], [4]로 나눌 수 있다.

여기서 두 개씩 병합 정렬을 한다면,
[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, 4, 5, 6, 7, 8]을 도출해 낼 수 있다.

여기의 예시에서도 알 수 있듯, 두 개를 병합하는 과정이 반복된다.
따라서 우리는 재귀(Recursion)를 사용하면 더욱 효율적인 코드를 만들 수 있다.

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)        # 합치면서 정렬하면 됩니다!

재귀함수를 이용할 때는 꼭 탈출조건을 잊지말자.

2. 스택 & 큐 (Stack & Queue)

(1) 스택(Stack)

스택이란, 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조이다.

Last In First Out(후입 선출)

스택 자료구조에서 제공하는 기능

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

(2) 큐(Queue)

큐란, 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조이다.

First In First Out(선입 선출)

큐 자료구조에서 제공하는 기능

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

3. 해쉬(Hash)

해쉬 테이블

해쉬 테이블이란, 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조이다.

해쉬 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.

데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
(키에 대해 검색하면 값을 바로 조회할 수 있는 유용한 자료구조!)

python에서는 딕셔너리 자료형이 해쉬 테이블이라고 불리기도 한다.
(같다고 생각하면 될 듯)


해쉬 함수란, 임의의 길이를 갖는 메시지를 입력하여, 고정된 길이의 해쉬 값을 출력하는 함수이다.

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

다음과 같은 방법으로 인덱스를 구할 수 있다.
hash(key) % len(self.items)

But,

만약 해쉬의 값이 같으면 어떻게 될까?
같은 어레이의 인덱스로 매핑이 되어 데이터를 덮어 써버리게 될 것이다.
이를 충돌(Collision)이 발생했다고 말한다.

✌️충돌을 해결하는 방법!

  1. 체이닝(Chaining) : 링크드 리스트를 사용

  2. 개방주소법(Open Addressing) : 배열의 다음 남는 공간에 넣기

ex.
fast 의 해쉬 값이 3이 나와서 items[3] 에 들어갔습니다.
그런데 slow 의 해쉬 값이 동일하게 3이 나왔습니다.
그러면, items[4] 를 봅니다., 이미 차 있네요.
그러면 그 다음 칸인 items[5] 를 봅니다. 
비어 있으니까 items[5] 에 slow 의 value 값을 넣는 방식입니다.
profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글