나의 개발일지 TIL(Today I learned) - 알고리즘 자료구조 특강 및 복습

Today I learned

• 자료구조와 알고리즘 특강
• 연결리스트 복습
• 정렬

 

자료구조와 알고리즘 특강

시간복잡도 최악의 경우를 가정하여 프로그램 성능을 정량화하는 방법

꼭 최악의 경우를 기준으로 계산하도록 해야한다

 

공간복잡도 시간복잡도에 비해서 크게 중요하지 않다 하지만 공간도 최적화하면 당연히 좋다

현업에서 알고리즘의 성능 향상을 위해서 공간을 필수적으로 더 사용해야 한다면 주저하지 말고 공간을 더 사용하자!

 

배열의 주소끼리 연관성

최초 원소의 메모리 주소가 100

두 번째 원소의 메모리 주소 = 최초 원소의 메모리 주소 +( 원소의 데이터 타입에 따른 바이트 크기 )

4바이트의 데이터 타입의 데이터를 저장한다면

100 -> 104 -> 108

이러한 특성 때문에 데이터를 빨리 찾을 수 있다

 

연결리스트 복습

연결리스트로 문제 풀어보기

1406번: 에디터

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

class Linked_list:
    def __init__(self, data):
        self.head = Node(data)

    def append(self, data):
        cur = self.head

        while cur.next is not None:
            cur = cur.next

        cur.next = Node(data)

    def get_node(self, index):
        cur = self.head
        cnt = 0

        while cnt < index:
            cur = cur.next
            cnt += 1

        return cur

    def add_node(self, index, data):
        new_node = Node(data)

        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        pre_node = self.get_node(index - 1)
        new_node.next = pre_node.next
        pre_node.next = new_node

    def del_node(self, index):
        pre_node = self.get_node(index - 1)
        if index == 0:
            self.head = self.head.next
            return

        elif index == self.get_length():
            pre_node.next = None
            return

        pre_node.next = pre_node.next.next

    def get_length(self):
        cur = self.head
        cnt = 0

        while cur is not None:
            cur = cur.next
            cnt += 1

        return cnt

    def print_all(self):
        cur = self.head

        while cur is not None:
            print(cur.data, end="")
            cur = cur.next


N = list(input())
cursor = len(N) - 1
cursor_left_right = 1
linked_list = Linked_list(N[0])
for i in range(1, len(N)):
    linked_list.append(N[i])

M = int(input())
for _ in range(M):
    commend = list(input().split())

    if commend[0] == 'P':
        if (cursor == 0 and cursor_left_right) or (cursor != 0 and cursor == linked_list.get_length() - 1):
            linked_list.append(commend[1])
            cursor += 1
        else:
            linked_list.add_node(cursor, commend[1])
            cursor += 1

    elif commend[0] == 'L':
        if cursor == 0 and cursor_left_right:
            cursor_left_right = 0

        elif cursor != 0:
            cursor -= 1

    elif commend[0] == 'D':
        if cursor == 0 and cursor_left_right == 0:
            cursor_left_right = 1

        elif cursor != linked_list.get_length() - 1:
            cursor += 1

    elif commend[0] == 'B':
        if cursor_left_right:
            linked_list.del_node(cursor)
            if cursor != 0:
                cursor -= 1
            else:
                cursor_left_right = 0

linked_list.print_all()

파이썬을 배운 연결리스트를 이용해서 문제를 풀어보려고 했다 하지만 시간 초과로 문제는 실패이다

그래도 원하는 대로 동작은 한다 3시간을 이 코드만 붙잡고 있었는데 실패라서 너무 아쉽다 하지만 이 문제를 풀어보면서

연결리스트가 더 머리에 잘 들어왔다

 

이 코드의 정답을 보자

import sys

inp = sys.stdin.readline
string = list(inp().rstrip())
stack = []

for _ in range(int(inp())):
    command = inp().split()

    if string and command[0] == "L":
        stack.append(string.pop())
    
    elif stack and command[0] == "D":
        string.append(stack.pop())

    elif string and command[0] == "B":
        string.pop()
    
    elif command[0] == "P":
        string.append(command[1])
    
string += stack[::-1]
print("".join(string))

스택을 이용해서 풀면 쉽다 아직 스택을 제대로 공부하지 않았지만 코드는 이해했다

연결리스트 복습이 끝나면 스택 큐 덱을 활용한 알고리즘을 공부해야 한다

이 코드는 커서를 중심으로 왼쪽 스택 오른쪽 스택으로 나눠 문자를 옮기면 된다

마지막에는 오른쪽 스택은 순차적으로 쌓이다 보니 문자가 역순이다 역순을 정방향으로 바꾼 후 최종 문자열로 합치면

쉽게 풀 수 있다

 

정렬

정렬이란 데이터를 순서대로 나열하는 방법을 의미한다

알고리즘의 굉장히 중요한 주제이다

이진 탐색을 가능하게 하고, 데이터를 효율적으로 탐색할 수 있게 만든다

 

1. 버블 정렬

가장 쉽고 직관적인 버블 정렬

첫 번째 자료와 두 번째 자료를 두 번째 자료와 세 번째 자료를 하나하나 비교하면서 교환하는 정렬 방식이다

코드를 보면서 공부해보자

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


def bubble_sort(array):
    len_arr = len(array)
    for i in range(len_arr - 1):
        for j in range(len_arr - i - 1):
            if array[j] > array[j + 1]:
                array[j + 1], array[j] = array[j], array[j + 1]

    return array


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

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

자신과 자신의 바로 옆 요소를 비교하고 바꾸고를 반복하는 정렬이다 이 함수의 시간 복잡도는 O(N^2)이다

 

2. 선택 정렬

하나의 요소를 골라서 모든 수와 비교하고 바꾸고를 반복해 정렬하는 방법이다

코드를 보면서 공부하자

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]:
                min_index = i + j
        array[min_index], array[i] = array[i], array[min_index]
    return


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

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

선택 정렬과 버블 정렬의 차이점은 선택 정렬은 최솟값을 찾아서 변경한다

그래서 최솟값을 담고 있을 그릇이 필요하다 최솟값이 나오면 담고 모든 수와 비교하며 자리를 바꾼다

시간 복잡도는 O(N^2)이다

 

3. 삽입 정렬

선택 정렬은 최솟값을 선택해 그릇에 담아두고 비교했지만 삽입 정렬은 하나씩 자기 위치에 삽입하는 방식

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위를 바꾸지만 삽입 정렬은 필요할 때만 위치를 변경한다

그래서 더 효율적인 방법이다

 

코드를 보고 공부해보자

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


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
    return array


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

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

6부터 시작해서 4와 한 번 비교하고 2로 6과 4를 비교해서 첫 번째로 옮긴다 이런 식으로 자기 자리를 찾아 삽입한다

이 방법도 시간 복잡도는 O(N^2)이다

 

4. 병합 알고리즘

배열을 반으로 나누어 쪼개는 걸 반복해 쪼개질 수 없을 때까지 쪼갠 후 병합을 하며 정렬을 시키는 방법이다

코드를 보자

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


def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = array[:mid]
    right_array = array[mid:]
    return merge(merge_sort(left_array), merge_sort(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


print(merge_sort(array))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

재귀를 이용해서 다 쪼갠 배열을 다시 병합해서 정렬시킨다  O(NlogN)의 시간 복잡도를 가진다

재귀도 힘들고 병합 정렬도 힘든데 두 개가 한 번에 들어가 있다 사실 아직 병합 정렬은 이해 못 했다

시간 복잡도도 왜 저렇게 나오는지 이해 못 했다 ㅠㅠ

다시 천천히 복습하면서 알고리즘 문제도 풀고.... 하다 보면 이해하겠지?

다음 TIL에서 제대로 이해한 모습을 봤으면 좋겠다!

 

오늘의 느낀 점

알고리즘은 하면 할수록 더욱 버겁다 그래도 암기의 영역도 있고 익숙해진다면 충분히 가능하다고 한다

계속 복습을 하고 문제를 푼다면 자연스럽게 내 것이 될 거라고 믿으면서 오늘의 TIL을 마친다