정렬
정렬이란 데이터를 순서대로 나열하는 방법을 의미한다.
버블 정렬
작은 숫자, 큰 숫자 순서로 있으면 내버려두고
큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경한다.
for i in range(5 - 1):
for j in range(5 - i - 1):
print(j)
실행결과
0123 012 01 0
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):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return array
bubble_sort(input)
print(input)선택 정렬
구하고자하는 값이 최솟값일때 최솟값을 선택해서 정렬한다.
for i in range(5 - 1):
for j in range(5 - i):
print(i + j)실행 결과
01234 1234 234 34
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[i], array[min_index] = array[min_index], array[i]
return
selection_sort(input)
print(input)삽입 정렬
전체에서 하나씩 올바른 위치에 삽입하는 방식이다.
선택정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,
삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이다.
for i in range(1, 5):
for j in range(i):
print(i - j)실행 결과
1 21 321 4321
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
insertion_sort(input)
print(input)병합 정렬(merge)
병합 정렬은 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다.
예를 들어
A 라고 하는 배열이 1, 2, 3, 5 로 정렬되어 있고,
B 라고 하는 배열이 4, 6, 7, 8 로 정렬되어 있다면
이 두 집합을 합쳐가면서 정렬하는 방법이다.
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])
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))mergeSort()
분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
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:]
print(array)
print('left_arary', left_array)
print('right_arary', right_array)
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))[5][3] 을 병합하면 [3, 5] 로
[2][1] 을 병합하면 [1, 2] 로
[6][8] 을 병합하면 [6, 8] 로
[7][4] 을 병합하면 [4, 7] 로
그러면 다시!
[3, 5] 과 [1, 2]을 병합하면 [1, 2, 3, 5] 로
[6, 8] 와 [4, 7]을 병합하면 [4, 6, 7, 8] 로
그러면 다시!
[1, 2, 3, 5] 과 [4, 6, 7, 8] 를 병합하면 [1, 2, 3, 4, 5, 6, 7, 8] 이 됩니다.
스택(stack)
한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조.(Cmd + Z)
push(data) : 맨 앞에 데이터 넣기
pop() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
# head
def push(self, value):
new_head = Node(value)
new_head.next = self.head
self.head = new_head
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
# is_empty 기능 구현
def is_empty(self):
return self.head is None큐(queue)
한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조.
enqueue(data) : 맨 뒤에 데이터 추가하기
dequeue() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, value):
new_node = Node(value)
if self.is_empty():
self.head = new_node
self.tail = new_node
self.tail.next = new_node
self.tail = new_node
return
def dequeue(self):
if self.is_empty():
return "Queue is empty"
delete_head = self.head
self.head = self.head.next
return delete_head.data
def peek(self):
if self.is_empty():
return "Queue is empty"
return self.head.data
return
def is_empty(self):
return self.head is None
해쉬(hash)
컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
키를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다.
put(key, value) : key에 value저장하기
get(key) : key에 해당하는 value가져오기
class Dict:
def __init__(self):
self.items = [None] * 8
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index] = value
return
def get(self, key):
index = hash(key) % len(self.items)
return self.items[index]
my_dict = Dict()
my_dict.put("test", 3)
print(my_dict.get("test"))- 충돌 해결
class LinkedTuple:
def __init__(self):
self.items = list()
def add(self, key, value):
self.items.append((key, value))
def get(self, key):
for k, v in self.items:
if key == k:
return v
class LinkedDict:
def __init__(self):
self.items = []
for i in range(8):
self.items.append(LinkedTuple())
def put(self, key, value):
return
def get(self, key):
index = hash(key) % len(self.items)
self.items[index].add(key, value)
return self.items[index].get(key)
