정렬array

특성

정렬은 이진 탐색*을 가능하게 하고, 데이터를 조금 더 효율적으로 탐색할 수 있게 만든다.

• 이진 탐색: 범위의 절반씩을 나누어 탐색을 실시

종류

• 버블 정렬: N번째 자료와 N+1 자료를 비교하여 교환하면서 자료를 정리한다.
  시간복잡도: O(N^2)
• 선택 정렬: 전체를 탐색하면서 가장 작은 값을 찾고 그 값을 맨 앞 값과 교체한다
  시간복잡도: O(N^2)
• 삽입 정렬: 전체에서 하나씩 올바른 위치에 삽입한다.
  이미 정렬된 정렬에서 다음 원소가 하나씩 비집고 들어간다.
  최선의 경우 N의 시간 복잡도를 가질 수 있다.

병합정렬 merge

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

두 배열을 병합정렬 merge 해보자

# 병합정렬할 배열은 각각 이미 정렬됐다고 가정
array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]

def merge(array1, array2):
    array_c = [] # 두 배열을 정렬하면서 새롭게 담을 배열
    array1_index = 0
    array2_index = 0
    # 두 배열의 전체 요소를 전부 담을 때까지
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            array_c.append(array1[array1_index])
            array1_index += 1
        else:
            array_c.append(array2[array2_index])
            array2_index += 1
	# 만약 한 배열에서 모든 요소를 새로운 배열에 다 담았다면
    # 비교를 하지 않고, 나머지 배열의 모든 요소를 새로운 배열에 담는다.
    if array1_index == len(array1):
        while array2_index < len(array2):
            array_c.append(array2[array2_index])
            array2_index += 1
    if array2_index == len(array2):
        while array1_index < len(array1):
            array_c.append(array1[array1_index])
            array1_index += 1
    return array_c
print(merge(array_a, array_b))

병합정렬 mergesort

• 분할 정복 divide and conquer: 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
  MergeSort(시작점, 끝점)
  MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))

병합정렬 mergesort 해보자

# 이번에는 정렬되지 않은 전체 코드
array = [5, 3, 2, 1, 6, 8, 7, 4]

# 재귀 함수 형태로 문제를 분리한다.
def merge_sort(array):
	# 탈출 조건: mergeSort하는 요소가 1개가 될 때까지
    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)


# 앞의 병합정렬 merge와 동일
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))

각각의 시간복잡도

• merge: O(N)
• mergeSort:모든 단계에서 O(N)의 시간 복잡도
  총 log2N의 단계
  log2N*O(N) = O(NlogN)만큼의 시간 복잡도

merge와 mergeSort의 경우 면접에서 직접 구현해보라는 경우도 있다.

백준 문제

https://www.acmicpc.net/problem/24060
https://www.acmicpc.net/problem/24061
https://www.acmicpc.net/problem/24062

스택stack

특성

한쪽 끝으로만 자료를 넣고 뺼 수 있는 자료 구조
Last In First Out LIFO 늦게 들어간 애가 빨리 나온다
ex. Ctrl+Z

list로 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    def push(self, value):
        """
        node = self.head
        while node.next is None:
            node = node.next
        node.next = 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_head = self.head
        self.head = self.head.next
        return delete_head

    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) # 3
print(stack.peek()) # >> 3
stack.push(4) # 4 - 3
print(stack.peek()) # >> 4
print(stack.pop().data) # >> 4
print(stack.peek()) # >> 3
print(stack.is_empty()) # >> False

queue로 구현

import queue
data_queue = queue.LifoQueue()
# push()와 동일
data_queue.put(1) # 1
data_queue.put(2) # 2 - 1
data_queue.put(3) # 3 - 2 - 1
# pop()과 동일
data_queue.get() # >> 3
data_queue.get() # >> 2

백준 문제

https://www.acmicpc.net/problem/1874
https://www.acmicpc.net/problem/10828