728x90 알고리즘47 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) i (0 tmp; j--) { a[j] = a[j - 1]; // tmp가 더 작으므로 정렬된 부분을 한 칸씩 뒤로 미룸 } a[j] = tmp; // 찾은 자리 j에 tmp를 넣음 } } 시간 복잡도: O(n^2) - avg, worst (best는 O(n)) 2023. 9. 22. 선택 정렬(Selection Sort) 선택 정렬(Selection sort) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 1. 정렬되지 않은 부분에서 가장 작은 키의 값을 선택 2. 아직 정렬하지 않은 부분의 첫 번째 요소와 교환 이 과정을 n-1회 반복 void selection(int a[], int n) { int i, j; for (i = 0; i < n - 1; i++) { int min = i; for (j = i + 1; j < n; j++) if (a[j] < a[min]) min = j; swap(a[i], a[min]); } } 시간복잡도: O(n^2) - best, avg, worst 모두 동일 2023. 9. 22. 버블 정렬(Bubble Sort) 버블 정렬(Bubble sort) 서로 인접한 두 원소를 비교하여 정렬되어 있지 않은 경우에 교환하는 정렬 알고리즘 *일련의 비교 과정을 패스(pass)라고 함 비교 횟수: (n-1) + (n-2) + ... + 1 = n(n-1)/2 이므로 시간복잡도 O(n^2) (best, avg, worst 모두) #include #include #define swap(x, y) do {int t = x; x = y; y = t;} while(0) void bubble(int a[], int n) { int i, j; for (i = n-1; i > 0; i--) { for (j = 0; j a[j + 1]) swap(a[j], a[j + 1]); } } } int main.. 2023. 9. 22. 재귀 알고리즘 직접 재귀: 자신과 같은 함수를 호출 간접 재귀: 함수 a가 함수 b를 호출하고 다시 함수 b가 함수 a를 호출하는 구조 순차곱셈 (팩토리얼) int factorial(int n){ if(n > 0) return n * factorial(n-1); else return 1; } 유클리드 호제법(최대공약수) int gcd(int x, int y){ if(y == 0) return x; else return gcd(y, x%y); } 하노이의 탑 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제. 모든 원반은 규칙에 맞게 첫 번째 기둥에 쌓여 있고, 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮겨야 함. 해결 방법: 맨 밑의 원반을 제외한 위의 원.. 2023. 9. 22. 큐 큐(queue): 선입선출 구조 인큐(enqueue): 데이터를 넣음 디큐(dequeue): 데이터를 꺼냄 프런트(front): 데이터를 꺼내는 쪽 리어(rear): 데이터를 넣는 쪽 배열로 큐 만들기 배열 que[]={1, 2, 3} 인큐: que[3] = 4; 디큐: x = que[0]; -> 이후의 모든 요소를 한 칸씩 앞으로 옮김: 복잡도 O(n) ! 링 버퍼로 큐 만들기 링 버퍼: 배열의 처음과 끝이 연결되었다고 보는 자료구조 첫 번째 요소가 front, 마지막 요소가 rear-1 프런트와 리어의 값을 업데이트하며 인큐와 디큐를 수행하므로 복잡도 O(1) ! 헤더파일 IntQueue.h #ifndef __IntQueue #define __IntQueue typedef struct { int ma.. 2023. 9. 22. 스택 IntStack.h #ifndef __IntStack #define __IntStack typedef struct { int max; //스택 용량 int ptr; //스택 포인터 int* stk; //스택 첫 요소 포인터 } IntStack; int Initialize(IntStack* s, int max); int Push(IntStack* s, int x); int Pop(IntStack* s, int* x); int Peek(const IntStack* s, int* x); void Clear(IntStack* s); int Capacity(const IntStack* s); int Size(const IntStack* s); int IsEmpty(const IntStack* s); int IsF.. 2023. 9. 22. 이전 1 ··· 3 4 5 6 7 8 다음