[TIL] 2022-11-11(10day)

알고리즘(Algorithm -3)

---

👉 정렬

- 데이터를 순서대로 나열하는 방법을 의미

 

-1) 버블 정렬

 - 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식

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


def bubble_sort(array):
    n = len(array)
    for i in range(n):	##배열의 크기만큼 반복했다가,
        for j in range(n - i - 1):	 #1개씩 줄어들면서 반복
            if array[j] > array[j + 1]:	#만약 array[j]가 더 크다면 
                array[j], array[j + 1] = array[j + 1], array[j]	#두 값을 변경
    return array

bubble_sort(input)
print(input)

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))

✍️ 시간 복잡도 : 2차 반복문이 나왔고, array 의 길이 만큼 반복한다면 O(N^2)

 

 

-2) 선택 정렬

 - 전체에서 최솟값을 선택하는 방법

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


def selection_sort(array):
    n = len(array)
    for i in range(n - 1):	#배열의 크기만큼 반복 (맨 마지막 비교는 하지 않아도 되기 때문에 -1)
        min_index = i	#min_index 라는 변수를 통해 각각의 인덱스들과 비교
        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]	#내부의 반복문이 끝나면, 최소 값의 인덱스와 i의 값들을 교체
    return array


selection_sort(input)
print(input)

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))

✍️ 시간 복잡도 : 2차 반복문이 나왔고, array 의 길이 만큼 반복한다면 O(N^2)

 

 

-3) 삽입 정렬

 - 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식

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


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):	#0 번째 인덱스는 정렬된 상태라고 판단되어 1번째 인덱스부터 비교
        for j in range(i):
            if array[i - j - 1] > array[i - j]:	#만약 array[i - j - 1]가 더 크다면
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]	#두 값을 변경
            else:
                break
    return array

insertion_sort(input)
print(input)

print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))

✍️ 시간 복잡도 : 2차 반복문이 나왔고, array 의 길이 만큼 반복한다면 O(N^2)

 

 

-4) 병합 정렬 (merge)

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

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


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])	#작은 값을 새로운 result라는 배열에 하나씩 추가
            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(array_a, array_b))

print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge([-7, -1, 9, 40], [5, 6, 10, 11]))
print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge([-1,2,3,5,40], [10,78,100]))
print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge([-1,-1,0], [1, 6, 9, 10]))

 

-5) 병합 정렬 (mergeSort)

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


def merge_sort(array):
    if len(array) <= 1:	#문자열의 길이가 1보다 작거나 같을 탈출
        return array
    mid = len(array) // 2
    left_array = array[:mid]
    right_array = array[mid:]
    print(array)
    print('left_arary', left_array)
    print('right_arary', right_array)
    return merge(merge_sort(left_array), merge_sort(right_array))

# 출력된 값을 보면 다음과 같다.
# [5, 3, 2, 1, 6, 8, 7, 4]     맨 처음 array 이고,
# left_arary [5, 3, 2, 1]      이를 반으로 자른 left_array
# right_arary [6, 8, 7, 4]     반으로 자른 나머지가 right_array 입니다!

# [5, 3, 2, 1]                 그 다음 merge_sort 함수에는 left_array 가 array 가 되고
# left_arary [5, 3]            그 array를 반으로 자르고,
# right_arary [2, 1]           나머지를 또 right_array 에 넣은 뒤 반복.

# [5, 3]
# left_arary [5]
# right_arary [3]

# [2, 1]
# left_arary [2]
# right_arary [1]

# [6, 8, 7, 4]
# left_arary [6, 8]
# right_arary [7, 4]

# [6, 8]
# left_arary [6]
# right_arary [8]

# [7, 4]
# left_arary [7]
# right_arary [4]

---

👉 스택 (Stack)

- 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조 ( Last In First Out  / LIFO 구조)

- 데이터 넣고 뽑는 걸 자주하는 자료 구조 (링크드 리스트와 유사)

 

-1) 스택의 구현 (제공하는 기능)

 - push(data) : 맨 앞에 데이터 넣기

		def push(self, value):                 # 현재 [4] 밖에 없다면
        new_head = Node(value)             # [3] 을 만들고!
        new_head.next = self.head          # [3] -> [4] 로 만든다음에
        self.head = new_head               # 현재 head의 값을 [3] 으로 바꿔준다.

 

 - pop() : 맨 앞의 데이터 뽑기

		def pop(self):
        if self.is_empty():                  # 만약 비어있다면 에러!
            return "Stack is empty!"
        delete_head = self.head              # 제거할 node 를 변수에 잡습니다.
        self.head = self.head.next           # 그리고 head 를 현재 head 의 다음 걸로 잡으면 된다.
        return delete_head                   # 그리고 제거할 node 반환

 - 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

---

👉 큐 (Queue)

- 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조.  (First In First Out / FIFO)

- 순서대로 처리되어야 하는 일에 필요 or 먼저 해야 하는 일들을 저장하고 싶을 때

 

-1) 큐의 구현 (제공하는 기능)

 - enqueue(data) : 맨 뒤에 데이터 추가하기

		def enqueue(self, value):              
        new_node = Node(value)             
				if self.is_empty():                # 만약 비어있다면,
            self.head = new_node           # head 에 new_node를
            self.tail = new_node           # tail 에 new_node를 넣어준다.
            return

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

 

- dequeue() : 맨 앞의 데이터 뽑기

		def dequeue(self):
        if self.is_empty():
            return "Queue is empty!"        # 만약 비어있다면 에러!

        delete_head = self.head             # 제거할 node 를 변수에 잡습니다.
        self.head = self.head.next          # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.

        return delete_head.data             # 그리고 제거할 node 반환

 

- peek() : 맨 앞의 데이터 보기

		def peek(self):
        if self.is_empty():
            return "Queue is empty!"
    
        return self.head.data

 

 - isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기

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

---

🙋‍♂️ 소감 : 

알고리즘 강의 영상을 몇 번씩 돌려보는데 알듯 말듯 ㅠㅠ
구조 자체는 눈에 익은 것도 같은데 원리가 정확히 이해가 가질 않아
우선 무지성 진도 나가기는 멈추고, 보았던 강의들을 주말 동안 계속 반복해야겠다 ㅠㅠ
오늘 첫 CS 특강도 있었는데, 백엔드에게는 정말 필요한 기본 지식들로서
기술면접 때도 많이 나오는 내용이라고 하니 차근차근 정리를 잘 해나가야겠다.

😈 아는 내용이라고 그냥 넘어가는건 금물! 😈