스파르타 코딩클럽
내일배움캠프 AI 웹개발자양성과정 2회차
알고리즘 강의 3주차 개발일지
1. Sort
1) bubble sort
: 인접한 두 칸을 비교해가며 정렬
: 시간복잡도
input = [4, 6, 2, 9, 1]
def bubble_sort(array):
while True:
end_bool = True
for i in range(len(array)-1):
if array[i] > array[i+1]:
array[i], array[i+1] = array[i+1], array[i]
end_bool = False
if end_bool:
break
return
bubble_sort(input)
print(input) # [1, 2, 4, 6, 9]2) selection sort
: 아직 정렬되지 않은 모든 원소를 탐색하여 특정 원소를 선택하는 정렬
: 시간복잡도
input = [4, 6, 2, 9, 1]
def selection_sort(array):
for i in range(len(array)):
min_index = i
for j in range(len(array)-i):
index = i + j
if array[min_index] > array[index]:
min_index = index
array[i], array[min_index] = array[min_index], array[i]
return
selection_sort(input)
print(input) # [1, 2, 4, 6, 9]3) insertion sort
: 아직 정렬되지 않은 원소를 하나씩 옳바른 위치에 삽입하는 정렬
: 시간복잡도
input = [4, 6, 2, 9, 1]
def insertion_sort(array):
for i in range(len(array)):
new_index = i
for j in range(i):
index = i - j - 1
if array[index] > array[new_index]:
array[new_index], array[index] = array[index], array[new_index]
new_index = index
else:
break
return
insertion_sort(input)
print(input) # [1, 2, 4, 6, 9]
4) merge sort
: 정렬된 서로다른 배열 두개를 옳바르게 정렬하는 방법(merge)을 정렬할 배열를 임위의 두개 배열로 나눠서 재귀적으로 정렬(merge sort)하는 방법
: 시간복잡도
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 = merge_sort(array[:mid])
right_array = merge_sort(array[mid:])
return merge(left_array, 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] 2. Stack
: 한쪽 끝으로만 데이터를 넣고 뺄 수 있는 자료 구조. 가장 최근에 저장한 데이터를 가장 먼저 꺼낼 수 있다. (LIFO - last in, first out)
In computer science, a stack is an abstract data type that serves as a collection of elements, with two main principal operations:
- Push, which adds an element to the collection, and
- Pop, which removes the most recently added element that was not yet removed.
The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out).
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
1) stack 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def push(self, value):
if self.is_empty():
self.head = Node(value)
else:
new_head = Node(value)
new_head.next = self.head
self.head = new_head
return
# 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 None2) stack example
Q. 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한 ,한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.
예를 들어 높이가 6, 9, 5, 7, 4 인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다.
그러면, 탑은 다음과 같이 신호를 주고 받습니다.
높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑에서 수신하고,
높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이,
높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다.
높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는
어떤 탑에서도 수신할 수 없습니다.
이 때, 맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 반환하시오.
top_heights = [6, 9, 5, 7, 4]
def get_receiver_top_orders(heights):
m = len(heights)
orders = [0] * m
for j in range(m):
serve_tower = heights.pop()
n = len(heights)
for i in range(n):
if heights[n-i-1] > serve_tower:
orders[m-j-1] = n-i
break
return orders
print(get_receiver_top_orders(top_heights)) # [0, 0, 2, 2, 4] 3. Queue
: 한쪽 끝으로 데이터를 넣고, 반대쪽에서는 데이터를 뺄 수 있는 선형구조. 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있다. (FIFO - first in, first out)
In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.
...
The operations of a queue make it a first-in-first-out (FIFO) data structure.
https://en.wikipedia.org/wiki/Queue_(abstract_data_type)
1) queue 구현
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
else:
self.tail.next = new_node
self.tail = new_node
return
def dequeue(self):
if self.is_empty():
return "Queue is empty"
if self.head == self.tail:
self.head = None
self.tail = None
else:
delete_node = self.head
self.head = self.head.next
return delete_node
def peek(self):
if self.is_empty():
return "Queue is empty"
return self.head.data
def is_empty(self):
return (self.head is None) and (self.tail is None)4. Hash
1) hash table
: 데이터를 hash function을 이용하여 key, value로 맵핑하여 저장하는 자료구조
In computing, a hash table, also known as hash map or dictionary, is a data structure that implements a set abstract data type, a structure that can map keys to values.
https://en.wikipedia.org/wiki/Hash_table
2) hash function
: 임의의 데이터를 고정된 크기의 값으로 반환해주는 함수
A hash function is any function that can be used to map data of arbitrary size to fixed-size values.
https://en.wikipedia.org/wiki/Hash_function
3) hash 구현
class LinkedTuple:
def __init__(self):
self.items = list()
def add(self, key, value):
self.items.append((key, value))
def get(self, key, default=None):
for k, v in self.items:
if key == k:
return v
return default
class LinkedDict:
def __init__(self):
self.items = []
for i in range(8):
self.items.append(LinkedTuple())
def put(self, key, value):
idx = hash(key) % len(self.items)
self.items[idx].add(key, value)
def get(self, key):
idx = hash(key) % len(self.items)
return self.items[idx].get(key)Github
