코딩고치

삽입 정렬 삽입 정렬 (insertion sort) 2번째 인덱스부터 시작해서 앞의 숫자를 비교. 비교 숫자보다 크면 자리를 바꿈 작은 숫자가 나오면 멈춤 참조 (visualgo.net/en/sorting) 데이터가 2개 일 때 index 1과 index 0 만 비교 데이터가 3개일 때 데이터가 4개일 때 def insertion_sort(data): for trial in range(len(data) - 1): for i in range(trial + 1, 0, -1): if data[i] < data[i - 1]: data[i], data[i - 1] = data[i - 1], data[i] else: break return data import random num = random.sample(ran..

선택 정렬 (selection sort) 선택 정렬이란 데이터에서 최솟값을 찾아 가장 맨 앞에 위치한 값과 교체하는 방법 참조 (visualgo.net/en/sorting) 데이터의 길이가 n일 때 총 n-1번 시행을 한다. 반복문을 돌면서 가장 작은 수가 들어있는 인덱스를 저장할 변수를 만든다. 반복문을 시행한 뒤 자리바꿈을 실행한다. def selection_sort(data): for trial in range(len(data) - 1): first = trial for i in range(trial + 1, len(data)): if data[first] > data[i]: first = i data[first], data[trial] = data[trial], data[first] return ..

버블 정렬 (bubble sort) 버블 정렬: 인접한 두 데이터를 이용하여 대소 관계를 비교하여 순서대로 정렬하는 알고리즘이다. 참조 (visualgo.net/en/sorting) 데이터가 2개일 때 데이터가 3개일 때 이런 식으로 규칙을 찾아 나가면 총데이터가 n개일 때 최악의 경우 데이터를 1번 시행에서 총 n-1번 대소 검사를 하고 n-1번 반복을 한다. 1번 시행을 하면 가장 큰 데이터가 가장 뒤로 이동한다. 이때 굳이 가장 마지막 데이터를 비교할 필요가 없어지므로 데이터의 길이를 시행 횟수만큼 빼준다. 1번 시행했을 때 자리바꿈이 일어나지 않으면 중지를 한다. def bubblesort(data): for trial in range(len(data) - 1): change = False # 자..

힙 힙은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위한 완전 이진트리 (Complete Binary Tree)이다. 힙을 사용하는 이유 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 알고리즘 구현에 사용된다. 이진트리의 경우 한번 연산이 진행되면 데이터가 1/2가 되므로 시간 복잡도가 O($log {n}$)이 걸린다. 따라서 힙도 O($log {n}$)이 걸린다 (배열의 경우 최악의 경우에 O(n)이 걸림). 힙의 구조 최댓값을 구하는 최대 힙 (Max Heap)과 최솟값을 구하는 최소 힙 (Min Heap)으로 구분된다. 최대 힙 : 각 노드의 값은 자식 노드의 값보다 크거나 같다 (가장 위가 가장 큰 값). 최소 힙 : 각 노드의 값은 자식 노드의 값보다 작거나 같다 (가장 위가 가장 ..