감자튀김 공장🍟

그래프의 탐색 그래프 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. Ex) 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 연결되어 있지 않은지 너비 우선 탐색(BFS: Breath First Search) 너비 우선 탐색이란? 너비 우선 탐색(BFS)은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 기법이다. 이러한 그래프가 있을 경우 BFS로 어떤 순서가 나오는지 확인해보자. 그래프의 시작 정점인 1에서 시작하여 v(1)을 방문한 후 v(1)에 인접한 정점 v(2)와 v(3)을 방문한 후 v(1)에 더 이상 인접한 간선이 없으므로 해당 단계는 종료된다. 다음에 정점 v(2)와 v(3)..

내용 설명 ➡ 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]

쉘 정렬 쉘 정렬은 삽입 정렬의 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) 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이..