본문 바로가기

Today I Learned

 (65)
선택 정렬 (Selection Sort) 선택 정렬(selection sort)이란, 다음과 같은 순서를 반복하며 정렬하는 알고리즘이다. 주어진 데이터 중, 최솟값을 찾음 해당 최솟값을 데이터 맨 앞에 위치한 값과 교체함 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting 즉, '최솟값을 선택한다'고 해서 선택 정렬이라고 이해하면 된다. 코드로 구현해보기 전에, 데이터가 두 개일 때, 세 개일 때, 네 개일 때 어떤 순서로 진행되는지 알아보겠다. 데이터가 두 개일 때 ex) data_list = [9, 1] data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_list[1] 값을 교환 데이터가 세 개일 때..
삽입 정렬 (Insertion Sort) 삽입 정렬(insertion sort)은 어떤 데이터를 특정 위치에 삽입하는 방식으로 정렬이 이뤄진다. 특징은 다음과 같다. 삽입 정렬은 두 번째 데이터부터 시작 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B 값을 뒤 인덱스로 복사 이를 key 값이 더 큰 데이터를 만날 때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting 데이터가 4개일 때를 예시로 들어 로직을 이해해보겠다. (데이터 개수에 따라 복잡도가 떨어지는 것은 아니므로) ex) data_list = [9, 3, 2, 5] 처음 한 번 실행하면, key 값은 9, 인덱스(0) - 1은 0보다..
버블 정렬 (Bubble Sort) 버블 정렬(bubble sort)이란 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘이다. 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting 데이터가 네 개일 때를 예시로 이해해보겠다. 데이터 갯수에 따라 복잡도가 바뀌는 것은 아니므로, 네 개로 로직을 이해할 수 있다. ex) data_list = [1, 9, 3, 2] 1차 로직 적용 1과 9 비교, 자리 바꿈 없음 [1, 9, 3, 2] 9와 3 비교, 자리 바꿈 [1, 3, 9, 2] 9와 2 비교, 자리 바꿈 [1, 3, 2, 9] 2차 로직 적용 1과 3 비교, 자리 바꿈 없음 [1, 3, 2, 9] 3과 2 비교, 자리 바꿈 [1, 2, 3, ..
힙 (Heap) (3) 힙에 데이터 삭제 구현 (Max Heap 예) 힙 클래스 구현 4 - delete 1 보통 삭제는 최상단 노드 (root node)를 삭제하는 것이 일반적이다. 왜냐하면 힙의 용도는 최대값 또는 최소값을 root node에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것이기 때문이다. class Heap: def __init__(self, data): self.heap_array = list() self.heap_array.append(None) self.heap_array.append(data) def pop(self): if len(self.heap_array) = len(self.heap_array):# array의 길이는 항상 전체 length에서 1을 더하게 되어 있다. len(ar..
힙 (Heap) (2) 4. 힙 구현 힙과 배열 일반적으로 힙 구현 시 배열 자료구조를 활용한다. 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root node 인덱스 번호를 1로 지정하면, 구현이 조금 더 수월하다. 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1 위 그림을 보면, 가령 10 노드의 인덱스 번호가 2인데..
힙 (Heap) 1. 힙 (Heap) 이란? 힙(Heap)이란 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다. 완전 이진 트리란 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다. 힙을 사용하는 이유는 다음과 같다. 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸리는 반면, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(log n)이 걸린다. 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다. 즉, 최대값과 최소값을 찾는 기능이 필요할 때, 힙(Heap) 자료구조를 사용하면 매우 효율성을 높일 수 있는 것이다. 힙이란 자료구조는 트리를 기반으로 하는 변형된 형태의 정책을..
트리 (Tree) (3) 6.4. 이진 탐색 트리 삭제 이진 탐색 트리에서 특정 노드를 삭제하는 것은 굉장히 복잡하다. 경우의 수를 나눠서 이해하는 것이 좋다. Leaf Node 삭제하는 경우 (Branch가 없을 때) Child Node가 하나인 Node 삭제하는 경우 (Branch가 한 개일 때) Child Node가 두 개인 Node 삭제하는 경우 (Branch가 두 개일 때) 일단, 이전까지 만들었던 이진 탐색 트리에 데이터 넣는 메서드, 탐색하는 메서드가 정리된 NodeMgmt는 다음과 같다. class NodeMgmt: def __init__(self, head): self.head = head def insert(self, value): self.current_node = self.head while True: if..
트리 (Tree) (2) 6. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기 이진 탐색 트리의 구조 안에서 구현을 하려면, 노드가 있고, 각 노드마다 왼쪽 Branch, 오른쪽 Branch를 지칭하는 주솟값을 가지고 있다. 이러한 구조는 내부 구현은 링크드 리스트로 하면 편리하다. 6.1. 노드 클래스 만들기 class Node: def __init__(self, value): self.value = value self.left = None self.right = None 클래스로 해서 노드라는 구조를 만드는데, 하나의 노드는 사실 더블 링크드 리스트와 비슷하다. 두 개의 주소를 가지고 있는 것이다. 왼쪽, 오른쪽의 주소를 하나씩 가지고 있는 것이다. 주소를 넣을 때부터 Branch를 가지고 있는 노드를 넣을 필요는 없으..

티스토리툴바