감자튀김 공장🍟

힙(Heap) 히프는 완전이진트리 기반 자료구조이다. 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 뜻한다. key(부모노드) ≥ key(자식노드) 조건을 항상 성립한다. 노드의 인덱스 배열로 구현 시 0번째 인덱스가 아니라 1번째 인덱스에서부터 시작된다. 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1 부모의 인덱스 = (자식의 인덱스) / 2 힙 트리 힙 트리는 중복된 값을 허용한다. 힙 트리가 이닌 예 완전 이진 트리가 아니기 때문에 힙 트리는 아니다. 힙 종류 최대 힙(max heap) 부모 노드의 키값이 자식 노드의 키값보다 ..

합병 정렬 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는다. 분할 정복(divide and conquer) 기법에 바탕을 두고 있는 정렬이다. 즉 하나의 리스트를 2개의 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결한다. 분리된 문제가 해결되지 않는다면 분할 정복 문제를 반복하여 적용한다. (순환 호출) 합병 정렬 단계 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다. 결합(Combine): 정렬된 부분 배..

퀵 정렬 분할-정복법(divide and conquer)에 근거한다. 퀵정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬하는 전형적인 분할-정복법을 사용한다. 합병 정렬과의 다른 점은 리스트를 비균등하게 분할한다는 점이다. 리스트 안의 한 요소를 피벗(pivot)으로 선택하면 피벗보다 작은 요소들은 피벗의 왼쪽으로, 피벗보다 큰 요소들은 피벗의 오른쪽으로 옮겨진다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다. 합병 정렬과 마찬가지로 부분 리스트에 대해 순환 호출된다. 퀵 정렬의 과정 피벗을 5로 설정한 후, 5보다 작은 값은 왼쪽 리스트에, 큰 값은 오른쪽 리스트로 보내는 탐색과 교환 과정..

내용 정리 ➡ https://good-potato.tistory.com/40 [C++] 쉘 정렬 (Shell Sort) 쉘 정렬 쉘 정렬은 삽입 정렬의 O(n^2)보다 빠르다. 셀 정렬은 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬 good-potato.tistory.com 코드 정리 # 쉘 정렬 def shell(arr): n = len(arr) h = n // 2 while h > 0: for i in range(h, n): j = i - h tmp = arr[i] while j >= 0 and arr[j] > tmp: arr[j + h] = arr[j] j -= h arr[j + h] = tmp h //= 2

내용 정리 ➡ https://good-potato.tistory.com/38 [C++] 삽입 정렬(Insertion Sort) 삽입 정렬 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. 정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판 good-potato.tistory.com 코드 정리 #삽입 정렬 def insertion(arr): n = len(arr) for i in range(1, n): j = i temp = arr[i] while j > 0 and arr[j-1] > temp: arr[j] = arr[j - 1] j -= 1 arr[j] = temp

내용 설명 ➡ https://good-potato.tistory.com/37 [C++] 선택 정렬(Selection Sort) 선택 정렬 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교 good-potato.tistory.com 코드 # 선택 정렬 def selection(arr): n = len(arr) for i in range(n-1): min = i for j in range(i + 1, n): if arr[j] < arr[min]: min = j arr[i], arr[min] = arr[min], arr[i]

설명은 여기로 ➡ https://good-potato.tistory.com/39 [C++] 버블 정렬(Bubble Sort) 버블 정렬 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 리스트의 비교-교환 과 good-potato.tistory.com python 코드 #버블 정렬 def bubble_sort(arr): n = len(arr) for i in range(n-1): # range(시작 숫자, 종류 숫자, step) for j in range(n-1, i, -1): if arr[j - 1] > arr[j]: arr[j-1], arr[j] = arr[j], arr[j-1] # 최적화1 - 이..

쉘 정렬 쉘 정렬은 삽입 정렬의 O(n^2)보다 빠르다. 셀 정렬은 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 쉘 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이 한다. 위 과정을 부분 리스트의 개수가 1일 때까지 반복한다. 부분 리스트 구성 방법 주어진 리스트의 각 k번째 요소를 추출하여 만든다. 이 k를 간격(gap)이라고 한다. 각 스텝마다 간격 k를 줄여가므로 수행과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가된다. 쉘 정렬의 과정 1단계 간격(gap)을 5로 잡고 {10, 3, 16}, {8, 22},..

버블 정렬 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 리스트의 비교-교환 과정(스캔)이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 버블 정렬의 과정 5와 3을 비교하면 5가 더 크므로 서로 교환하고, 다음으로 5와 8을 비교하게 되면 8이 더 크므로 교환 없이 다음 단계로 진행된다. 한 번의 스캔에 의해 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동하게 된다. 스캔의 실행 횟수는 원칙적으로는 (데이터 개수 - 1)번 만큼 실행되지만 중간에 정렬이 끝났다면 계속 실행하지 않는다. 구현 코드 #include using namespace std; void bubbleSort(i..

삽입 정렬 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. 정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단한 후 해당 위치에 이 숫자를 삽입한다. 삽입 정렬의 과정 카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드를 기존의 카드 사이의 올바른 자리를 찾아 삽입 하는데 그 경우와 똑같다고 생각하면 된다. 구현 코드 #include using namespace std; void insertionSort(int arr[], int len) { int i, j, temp; for (i = 1; i = 0; j--) { if (arr[j] < ..