링크드리스트

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        node = self.get_node(index-1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

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



linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)

linked_list.add_node(1, 6)
linked_list.print_all()

print("/")

linked_list.delete_node(0)
linked_list.print_all()

노드들의 생성, 추가, 조회, 삽입, 삭제 하는 함수들을 관리하는 링크드 리스트 클랙스 구현 !

와 진짜.. 어려웠다...
강좌를 아무리 보고 또 봐도 이해가 안됬어서
몇 시간 동안.. 이해해 보려고 머리 뜯으며 공부 중이었는데
어느 순간부터 다시 강좌를 보는데 갑자기 뇌가 트인 것처럼
모든 강사님의 말이 무슨 말인지 이해가 되기 시작하더니..
순식간에 2주 차 공부를 마쳤다

지금 생각해 보면 쉬운 개념인 것 같은데
처음 볼 땐... 지옥 그 자체였다.
c언어에서도 포인터라는 개념이 있는데
그때는 이 정도로 어렵진 않았던 거 같은데... 뭐지?

c언어는 몇 달 동안 천천히 개념을 잡아가면서 공부했어서 그런 걸 수도?
파이썬 문법은 하루 공부한 거 말곤 없었으니 어찌 보면 당연한 것 같다.

버블 정렬

0 ~ range(len(array)-1)까지 돌면서
0 ~ range(len(array)-1)에서 1개씩 줄어들면서
만약 현재 인덱스가 다음 인덱스보다 클경우 뒤집어준다.

input = [4, 6, 2, 9, 1] 
#시간복잡도 = O(N^2)

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

선택 정렬

input = [4, 6, 2, 9, 1]
#시간복잡도 = O(N^2)


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


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

삽입 정렬

0번째 인덱스는 이미 정렬된거로 생각하고
시작하는게 핵심
안쪽 for문에서 range(i)가 핵심이다.
range(i)를 쓰는 이유는
아래 예제에서 보면
4는 이미 정렬되어있고
1번째 인덱스가 6인데
range(1)이면 한번 도는데 if문 충족안해서 break됨.
여기서 이제 4와 6은 정렬되어있음
i가 2로 증가했고
2번째 인덱스인 2를 가지고 놀기시작.
range(2)면 0~1이니까 for문 두번돌꺼임
첫번째 for문에서 6이랑 2랑 비교했는데 if문 충족해서
6,2 에서 위치를 2,6으로 바꾸고
두번째 for문에서 4랑 2랑 비교하는데
if문 충족해서
4,2 에서 2,4로 위치를 바꿈

input = [4, 6, 2, 9, 1]
#O(N^2) 지만 break문이 있어서 시간복잡도가 최선일 경우엔 O(N)이 될 수 있다.


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


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

각종 정렬들에 대해서는 이미 많이 알고있었다.
졸업 시험이 정처기 필기였어서
시험을 통과하기 위해 미친듯이 공부 했었는데...
추억이 새록새록하다.
정렬이 여기서 나오다니...!!

하지만.. 코드로 구현하는건 역시나 어려웠다.
input을 코드에 대입해서 작동하는 원리를 단계별로 글로 써두니까 쉽게 이해가 되긴 한다.. 번거롭지만 ㅠㅠ
더 공부해보자...!!