감자튀김 공장🍟

쉘 정렬 쉘 정렬은 삽입 정렬의 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] < ..

선택 정렬 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 이 절차를 (개수 - 1)만큼 되풀이한다. 선택 정렬의 과정 구현 코드 #include using namespace std; void swap(int& a, int& b) { int tmp; tmp = a; a = b; b = tmp; } void SelectionSort(int* arr, int len) { int min_idx; for (int i = 0; i < len - 1; i++) { min_idx = i; for (int j = i + 1; j < len; j++) { if (arr[min_idx] ..

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

연결 리스트 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(Linked List)라고 한다. 연결 리스트는 배열의 단점을 보완하고자 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 연결 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 3가지 종류의 연결 리스트가 있다 단순 연결 리스트 원형 연결 리스트 이중 연결 리스트 단순 연결 리스트 구현 구조 typedef struct ListNode { int data; struct ListNode* next; } ListNode; ​ 구조체 내부에 데이터를 저장하는 dat..

순회 이진 트리에서 데이터를 탐색하는 방법은 크게 세 가지 방법이 있다. 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal) 전위 순회 전위 순회는 Root를 제일 먼저 처리합니다. 순서 Root (자기 자신) 왼쪽 자식 오른쪽 자식 위의 트리에서 전위 순회로 순회를 한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서입니다. 중위 순회 중위 순회는 Root를 가운데 순번에서 처리합니다. 순서 왼쪽 자식 Root (자기 자신) 오른쪽 자식 위의 트리에서 중위 순회로 순회를 한다면 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7 순서입니다. 후위 순회 후위 순회는 Root를 가장 마지막에서 ..

큐의 구조 큐의 특징 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. FIFO(First-In First-Out): 먼저 들어온 데이터가 먼저 나가는 구조이다 A -> B -> C -> D의 순서로 큐에 삽입되었을 때 삭제 순서는 A -> B -> C -> D 이다. 큐에서 삽입이 일어나는 곳을 후단(Rear)라고 하며 삭제가 일어나는 곳을 전단(Front)라 한다. 스택과 다른 점은 삽입과 삭제가 다른 쪽에서 일어난다는 점이다. 큐의 연산 push(): 큐에 원소를 추가(rear) pop(): 큐에 있는 원소를 삭제(front) front(): 큐 제일 앞에 있는 원소를 반환 back(): 큐 제일 뒤에 있는 원소를 반환 empty(): 큐가 비어 있으면 tr..

스택의 구조 스택의 특징 스택의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. LIFO (Last-In-Fisrt-Out)의 형태를 가지고 있다. A -> B -> C -> D의 순서로 스택에 삽입되었을 경우 삭제 순서는 D -> C -> B -> A가 된다. 스택의 가장 위를 top이라고 하며 top 에서 삽입과 삭제가 이루어진다. 스택에 요소가 하나도 없을 때 그러한 스택을 공백 스택(empty stack)이라고 한다. 스택의 연산 push: 스택에 새로운 원소를 삽입 pop: 스택의 top 원소를 제거하고 반환 empty: 스택이 비어있는지 검사 size: 스택의 크기 swap: 두 스택의 내용을 바꿈 top: top에 있는 원소를 반환 스택 구현 코드 #include ..