보호되어 있는 글입니다.
2023 2학기/알고리즘
힙정렬 힙정렬은 힙 자료구조를 이용하는 정렬 알고리즘. 힙 : 힙 조건을 만족하는 완전 이진트리. (힙 조건 -최대힙- 각 노드의 값이 자식 노드의 값보다 커야 한다는 것) n개의 노드를 가진 힙의 높이 = log2 n 힙의 루트에는 가장 큰 수가 저장되므로, 루트의 숫자를 힙의 가장 마지막 노드에 있는 숫자와 바꿈. 즉, 가장 큰 수를 배열의 가장 끝으로 이동시킨 것. 그리고 힙의 크기를 1 줄인후, 루트에 새로 저장된 숫자로 인해 위배된 힙 조건을 해결하여 새로운 루트의 숫자를 힙의 마지막 노드에 있는 숫자와 바꿈. 이를 반복. 수도코드 및 시간복잡도 힙 정렬 입력:입력이 A[1]부터 A[n]까지 저장된 배열A 출력:정렬된 배열 A 배열 A의 숫자에 대해서 힙 자료 구조를 만든다 heapSize = ..
쉘 정렬 버블 정렬의 경우, 작은 숫자가 배열의 앞부분으로 매우 느리게 이동. 삽입 정렬의 경우, 배열의 마지막원소가 입력에서 가장 작은 숫자라면, 그 숫자가 배열의 맨 앞으로 이동해야하므로, 모든 다른 숫자들이 1칸씩 오른쪽으로 이동해야함. 쉘 정렬 = 그룹의 크기를 줄여가며, 삽입정렬을 각 그룹마다 진행 수도코드 및 시간복잡도 입력:크기가 n인 배열A 출력:정렬된 배열A for each gap h = [h0 > h1 > ... hk = 1] //큰 gap부터 차례로 for i = h to n-1{ currentElem = A[i]; j = i; while(j >= h and (A[j-h] > currentElem)) { A[j] = A[j-h]; j = j-h; } A[j] = currentElem;..
선택 문제 (selection) n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제. 효율적으로 찾기 위해 분할 정복 개념 씀. 수도코드 및 시간복잡도 selection(A, left, right, k) 입력 : A[left]~A[right]와 k (단, 1
퀵 정렬 퀵 정렬은 분할 정복 알고리즘으로 분류되나, 알고리즘이 수행되는 과정을 보면 정복 후 분할하는 알고리즘. 피봇이라는 배열의 원소를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할후, 피봇을 그 사이에 놓는 것. 분할된 부분문제들에 대해서도 동일한 과정을 순환적으로 수행한다. 수도코드 및 시간복잡도 Quicksort(A, left, right) 입력 : 배열 A[left] ~ A[right] 출력 : 정렬된 배열 A[left] ~ A[right] if (left < right) //만약 그렇지 않으면, left == right으로 더이상 분할할 수 없는 크기 { 피봇을 A[left] ~ A[right] 중에 선택하고, 피봇을 A[left]와 자리를 바꾼 후..
삽입정렬 삽입정렬은 배열을 정렬된 부분(앞부분) 과 정렬이 안 된 부분(뒷부분) 으로 나누고, 정렬이 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복. 정렬된 부분의 원소 수가 1개 늘어나고, 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어듬. 수도코드 및 시간복잡도 입력 : 크기가 n인 배열 A 출력 : 정렬된 배열 A for i = 1 to n-1{ currentElement = A[i] //정렬이 안 된 부분의 가장 왼쪽 원소 j = 0) and (A[j] > currentEelement){ A[j+1] = A[j] //자리 하나씩 이동 j = pos && a[j] > currentElem) { a[j + 1] = a[j]; j--; } a[j +..
선택정렬 입력 배열 전체에서 최솟값을 '선택'하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여 배열의 1번 원소와 자리를 바꾸고 이러한 방식을 반복하는 정렬하는 알고리즘 불안정 정렬(동일한 키 값의 요소 순서가 정렬후 유지x) 이유 : 대용량 데이터에서는 비효율. (비교하는 횟수가 많음) 최선의 경우와 최악의 경우 시간복잡도가 같다. 수도코드 및 시간복잡도 입력 : 크기가 n인 배열 A 출력 : 정렬된 배열 A for i = 0 to n-2 { min = i for j=i+1 to n-1{ if A[j] < A[min] min = j } A[i] A[min] } return 배열A i for 루프가 n-1번 수행되는데, i = 0일때 n-1번 비교, i..
스택(stack) 스택(stack) = 쌓다 -> 데이트러르 차곡차곡 쌓아 올린 형태의 자료구조 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조 top을 통해서 삭제, 삽입 가능 = 후입선출 (LIFO = Last In First Out) 스택 구현 배열 기반으로 구현 동적배열 기반으로 구현 연결 리스트로 구현 배열 기반으로 구현 //배열 기반으로 stack 구현 #include #include #include typedef struct ArrayStack { int top; int capacity; int* array; }Stack; //주어진 capacity 크기로 stack을 생성하는 함수 Stack* createStack(int capacity) { Stack* stack = (Stack*)..
