알고리즘/자료구조(C) 22

병합 정렬(Merge Sort)

병합 정렬(Merge sort) 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 후 둘을 병합하여 정렬하는 알고리즘 배열의 요소 개수가 2개 이상인 경우: 1. 앞부분을 병합 정렬로 정렬 2. 뒷부분을 병합 정렬로 정렬 3. 배열의 앞부분과 뒷부분을 병합 (두 배열의 요소를 하나씩 선택하여 비교한 후 작은 값을 대입) #include #include static int* buff; //작업용 배열 static void __mergesort(int a[], int left, int right) { if (left < right) { int center = (left + right) / 2; int p = 0; int i; int j = 0; int k = left; __mergesort(a, left, ce..

선택 정렬(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 모두 동일

버블 정렬(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..

재귀 알고리즘

직접 재귀: 자신과 같은 함수를 호출 간접 재귀: 함수 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개의 기둥 사이에서 옮기는 문제. 모든 원반은 규칙에 맞게 첫 번째 기둥에 쌓여 있고, 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮겨야 함. 해결 방법: 맨 밑의 원반을 제외한 위의 원..

큐(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..

구조체

구조체: 임의의 데이터를 다시 조합하여 만드는 자료구조 구조체 태그: struct와 함께 쓰임 구조체 멤버: 구조체를 구성하는 요소 struct xyz { int x; long y; double z; }; a.x //struct xyz형을 갖는 객체 a p->x //sturct xyz형에 대한 포인터 p typedef struct xyz XYZ; //구조체 자료형은 'struct + 구조체 태그'. 이를 typedef로 간단하게 나타냄 typedef struct { int x; long y; double z; } XYZ;