파이썬 알고리즘 정의와 종류 (정렬, 탐색)
알고리즘 종류
정렬(Sorting)
정렬은 특정한 기준에 따라 데이터를 늘어놓는 알고리즘입니다.
버블 정렬(Bubble Sort)
버블 정렬은 바로 옆에 있는 것과 비교해서 정렬하는 것입니다. 구현은 쉽지만 효율성이 매우 낮다고 알려져 있습니다.
선택 정렬(Selection Sort)
데이터를 선택 정렬은 배열에서 작은 데이터를 선별하여서 데이터를 앞으로 보내는 정렬의 일종입니다. 이 정렬도 효율은 낮습니다.
삽입 정렬(Insertion Sort)
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.
퀵 정렬(Quick Sort)
퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행합니다.
병합 정렬(Merge Sort)
합병 정렬 또는 병합 정렬은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나 입니다.
힙 정렬(Heap Sort)
힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 됩니다.
기수 정렬(Radix Sort)
기수 정렬은 기수 별로 비교 없이 수행하는 정렬 알고리즘이다. 기수로는 정수, 낱말, 천공카드 등 다양한 자료를 사용할 수 있으나 크기가 유한하고 사전순으로 정렬할 수 있어야 한다. 버킷 정렬의 일종으로 취급되기도 합니다.
계수 정렬(Count Sort)
계수 정렬 또는 카운팅 소트는 컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것, 즉 정수 정렬 알고리즘의 하나 입니다.
파이썬 코드
import random
class Sort :
def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr) - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
def selection_sort(arr):
for i in range(len(arr)):
min_index = i
for j in range(i+1, len(arr)):
if arr[min_index] > arr[j]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left, right, equal = [], [], []
for i in arr:
if i < pivot:
left.append(i)
elif i > pivot:
right.append(i)
else:
equal.append(i)
return quick_sort(left) + equal + quick_sort(right)
def merge_sort(arr):
if len(arr) < 2:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
merged_arr = []
l = r = 0
while l < len(left) and r < len(right):
if left[l] < right[r]:
merged_arr.append(left[l])
l += 1
else:
merged_arr.append(right[r])
r += 1
merged_arr += left[l:]
merged_arr += right[r:]
return merged_arr
def heap_sort(arr):
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
n = len(arr)
for i in range(n, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
def radix_sort(arr):
RADIX = 10
placement = 1
max_digit = max(arr)
while placement < max_digit:
buckets = [list() for _ in range(RADIX)]
for i in arr:
tmp = int((i / placement) % RADIX)
buckets[tmp].append(i)
a = 0
for b in range(RADIX):
buck = buckets[b]
for i in buck:
arr[a] = i
a += 1
placement *= RADIX
return arr
def counting_sort(arr):
max_value = max(arr)
m = max_value + 1
count = [0] * m
for a in arr:
count[a] += 1
i = 0
for a in range(m):
for c in range(count[a]):
arr[i] = a
i += 1
return arr
arr = [i for i in random.sample(range(10), 10)]
print("Original array: ", arr)
print("Bubble sort: ", Sort.bubble_sort(arr))
print("Selection sort: ", Sort.selection_sort(arr))
print("Quick sort: ", Sort.quick_sort(arr))
print("Merge sort: ", Sort.merge_sort(arr))
print("Heap sort: ", Sort.heap_sort(arr))
print("Radix sort: ", Sort.radix_sort(arr))
print("Counting sort: ", Sort.counting_sort(arr))
알고리즘 탐색(Search)
탐색이란, 원하는 값을 찾는 것입니다.
선형 탐색(Linear Search)
순서대로 하나씩 찾는 방법 입니다.
이분(이진) 탐색(Binary Search)
반씩 제외하면서 찾는 방법 입니다.
해시 탐색(Hash Search)
선형탐색이나 이진탐색은, 어떤 값이 어떤 index에 들어있는지에 대한 정보가 없는 상태에서 탐색할 때 사용하는 방식이 었습니다.반면에 해시 탐색은 값과 index를 미리 연결해 둠으로써 짧은 시간에 탐색할 수 있는 알고리즘입니다.
완전 탐색
브루트 포스(Brute Force)
brute: 무식한, force: 힘 무식한 힘으로 해석할 수 있다. 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져옵니다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다는 점입니다.
백트래킹
해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.
재귀함수
함수는 자기 자신을 내부에서 호출할 수 있다. 이러한 함수를 재귀 함수라고 한다. 재귀 알고리즘(recursive algorithm)이란 재귀 함수를 이용하여 문제를 해결하는 알고리즘을 말합니다.
def linear_search(list, target):
for i in range(0, len(list)):
if list[i] == target:
return i
return None
def binary_search(list, target):
first = 0
last = len(list) - 1
while first <= last:
midpoint = (first + last) // 2
if list[midpoint] == target:
return midpoint
elif list[midpoint] < target:
first = midpoint + 1
else:
last = midpoint - 1
return None
def hash_search(list, target):
hash_table = {}
for i in range(0, len(list)):
hash_table[list[i]] = i
if target in hash_table:
return hash_table[target]
return None
def brute_force_search(list, target):
for i in range(0, len(list)):
for j in range(i + 1, len(list)):
if list[i] + list[j] == target:
return [i, j]
return None
def recursive_binary_search(list, target):
if len(list) == 0:
return False
else:
midpoint = len(list) // 2
if list[midpoint] == target:
return True
else:
if list[midpoint] < target:
return recursive_binary_search(list[midpoint + 1:], target)
else:
return recursive_binary_search(list[:midpoint], target)
print(linear_search([1,2,3,4,5], 5))
print(binary_search([1,2,3,4,5], 5))
print(hash_search([1,2,3,4,5], 5))
print(brute_force_search([1,2,3,4,5], 5))
print(recursive_binary_search([1,2,3,4,5], 5))
BFS(너비 우선 탐색) & DFS(깊이 우선 탐색)
from collections import deque
graph_list = { 1: set([2, 3]),
2: set([1, 3, 4]),
3: set([1, 5]),
4: set([1]),
5: set([2,6]),
6: set([3,4])}
root_node = 1
def bfs(graph, root):
visited = []
queue = deque([root])
while queue:
node = queue.popleft()
if node not in visited:
visited.append(node)
queue += graph[node] - set(visited)
return visited
print(bfs(graph_list, root_node))
def dfs(graph, root):
visited = []
stack = [root]
while stack:
node = stack.pop()
if node not in visited:
visited.append(node)
stack += graph[node] - set(visited)
return visited
print(dfs(graph_list, root_node))
알고리즘 공부하기 좋은 사이트
- 백준 (Baekjoon)
- 프로그래머스 (Programmers)
- 코드업 (CodeUp)
- 리트코드 (LeetCode)
- 코드포스 (Codeforces)
- 해커랭크 (Hackerrank)
알고리즘 관련 학습 자료 추천
Flutter 배우는데 Dart 언어 찍먹해서 되겠어요?
모두의연구소 오름캠프 [Flutter 모바일 앱 과정] 수강생의 인터뷰입니다.다른 프레임워크에 비해 꾸준하게 개발되서 플러터를 선택했는데,가장 근간인 Dart를 제대로 배울 수 있어서 좋았다고 하는데,자세한 내용은 영상에서 만나요!모두의연구소 오름캠프 [Flutter 모바일 앱 과…
