반응형 자료구조6 이진 탐색(Binary Search) 이진 탐색(Binary Search) 어떤 decision problem의 답이 단조성(monotonicity)를 띌 때, 정답을 포함하는 구간의 크기를 절반씩 줄여가며 query 횟수를 최대 O(logN)회로 제한할 수 있다. mid보다 찾으려는 수가 작다면 mid의 오른쪽 원소들을 볼 필요가 없을 것이고, mid보다 찾으려는 수가 크다면 mid의 왼쪽 원소들도 볼 필요가 없을 것이다. divide-and-conquer 방식으로 접근해보자. Devide arr[1..N]가 arr[1..mid]와 arr[mid..N]으로 divide. Conquer A[mid] = x : return mid A[mid] < x : select A[mid + 1..N] for the next iteration. A[mid.. 2024. 3. 26. 문자열 압축 문제 문자열 압축 문제 #include #include #include using namespace std; void InsertionSort(char* arr, int n) { int i, key, j; for (i = 1; i = 0 && arr[j] > key) // = 1); cout 2024. 3. 26. 순차 탐색(Sequential Search) 순차 탐색(Sequential Search) 정렬되어 있지 않은 데이터에 대해 count와 index를 찾아보고, 정렬되어 있는 데이터에도 똑같은 기능을 하는 함수를 만들어 보았다. #include using namespace std; void Print(int *arr, int size) { for (int i = 0; i < size; i++) { cout 2024. 3. 12. 삽입 정렬(Insertion Sort) 삽입 정렬 삽입 정렬은 정렬이 안된 key값 오른쪽 부분에서 정렬이 된 key값 왼쪽 부분으로 적절한 위치에 삽입하여 정렬하는 방법이다. #include using namespace std; void Print(int *arr, int size) { for (int i = 0; i < size; i++) { cout 2024. 3. 12. 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 버블 정렬은 모든 값들을 한번씩 비교를 하기 때문에 전체가 이미 정렬이 끝났는지 안끝났는지 미리 확인을 할 수 있다. 그래서 정렬 알고리즘 끼리도 항상 어떤 알고리즘이 좋다 라고 할순 없다. 경우에 따라 다르기 때문이다. #include using namespace std; void Print(int *arr, int size) { for (int i = 0; i < size; i++) { cout 2024. 3. 7. 선택 정렬(Selection Sort) 선택 정렬 선택 정렬은 가장 작은 것부터 선택하여 빼는 방법이다. #include using namespace std; bool CheckSorted(int *arr, int size) { for (int i = 0; i arr[i + 1]) { return false; } } return true; } int main() { for (int k = 0; k < 3; k++) { for (int j = 0; j < 3; j++) { for (int i = 0; i < 3; i++) { int arr[3] = { i, j, k }; int size = sizeof(arr) / sizeof(int); for (int e = 0; e < size; e+.. 2024. 3. 6. 이전 1 다음 반응형
