기타/C언어: 34개의 글
[C] 쉘정렬 사용 예제 삽입 정렬은 이미 정렬된 배열이나 대충 정렬된 배열에 대해서는 매우 뛰어난 성능을 보이지만 그렇지 않은 경우에는 속도가 매우 느리다. 이것은 삽입 정렬이 바로 인접한 요소와 비교를 하기 때문이다. 쉘 정렬은 이 같은 문제점을 해결하기 위해서 h만큼의 간격으로 떨어진 레코드를 삽입 정렬하는 방법이다. 쉘 정렬은 안정성이 없다 쉘 정렬은 h 값에 의해 성능이 좌우된다.h = 3 * h +1 이 가장 효율이 좋다고 한다. #include #include // 최대 효율 h 지정 h = 3*h+1 void shell_sort1(int a[], int n){ int i, j, k, h, v; for (h = 1; h 0; h /= 3){ for (i = 0; i v){ a[k] = a[k..
[C] 버블 정렬 예제 정리 버블 정렬은 인접한 배열의 요소를 비교 교환하여 전체적으로는 대충 정렬을 하면서 최대값을 배열의 제일 뒤로 보내는 것을 반복한다. 버블 정렬은 비교 교환하며 최대 값을 제일 뒤로 보내기 때문에 정렬의 전과정을 하지 않아도 이미 정렬되어 있는 경우가 많다. 또한 안정성이 있다. #include void bubble_sort(int a[], int n){ int i, j, t; for (i = 0; i
[C] 삽입 정렬 예제 정리 삽입 정렬은 이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 동작을 반복적으로 하는 정렬 방법이다. 삽입 정렬은 선택 정렬과 달리 같은 키에 대한 순서가 보장되므로 안정성이 있다.(단, 작은 값 비교시 t){ a[j] = a[j - 1]; j--; } a[j] = t; } } 위의 코드에서 사실 변수 t 는 불필요하다. 하지만 굳이 t를 쓴 이유는 속도 향상을 위해서이다.이 부분에서 a[i]를 쓰는 것과 단순한 t를 쓰는 것은 차이가 있다.a[i]를 쓸 경우 컴파일러는 a의 값(주소)를 읽어서 i를 더하는 식의 복잡한 처리를 하지만, 단순히 t를 쓸 때는 t의 값을 읽어오는 것으로 처리는 끝난다.자주 호출이 필요한 내부 루프의 경우는 이렇게 임시 변수를 많이 사용한..
[C] 선택정렬 SelectSort 코드 선택정렬은 배열의 첫번째 항목부터 배열의 최소값을 탐색하여 교환하며 정렬하는 방식이다. 선택정렬의 장점은 교환이 최소화 된다는 것이다.비교 횟수는 최소 값을 찾기 위해 N의제곱/2 이지만 교환 횟수는 많아야 N번이다.이런 특징으로 선택 정렬은 큰 레코드와 작은 키를 직접 정렬할 때 굉장히 유용하다. 하지만 비교를 위한 이중 루프를 돌기 때문에 O()의 성능을 가진다.그래서 선택 정렬은 N의 수가 커지면 그 실행 시간은 제곱으로 늘어난다. #include // 선택 정렬 void select_sort(int a[], int n){ int min; int minindex; int i, j; for (i = 0; i
[C] 하노이의 탑 구현하기 (재귀, 비재귀) 하노이의 탑 게임은 세 개의 기둥과 서로 다른 크기의 N개의 원반으로 구성된다.이 원반들은 세 개의 기둥 중의 하나에 반드시 꽂혀 있어야 하며, 자신보다 작은 원반 위에는 그 원반을 놓을 수 없다.즉 원반은 아래에 가장 큰 것이 와야 하며 위로 갈 수록 원반은 작아져야 한다. 문제는 기둥 1에 N개의 원반이 모두 꽂혀 있는 것에서 시작한다. 물론 이 원반들은 크기순으로 배열되어 있다.이 원반을 기둥 2를 이용하여 기둥 3으로 모두 옮기는 것이다. ex > N == 31. 기둥 1의 원반을 기둥 3으로 옮긴다.2. 기둥 1의 원반을 기둥 2로 옮긴다.3. 기둥 3의 원반을 기둥 2로 옮긴다.4. 기둥 1의 원반을 기둥 3으로 옮긴다.5. 기둥 2의 원반을 기둥..
[C] 피보나치 수열 구하기 피보나치 수열은 연속된 두개의 수의 합이 다음 번 숫자가 되는 수열이다. F[N] = F[N-1] + F[N-2] 단, F[1] = F[2] = 1 #include // 피보나치 수열 int fibonacci(int n){ if (n == 1 || n == 2){ return 1; } else{ return fibonacci(n - 1) + fibonacci(n - 2); } } void main(void){ printf("fibonacci index 5 : %d", fibonacci(5)); printf("\nfibonacci index 8 : %d", fibonacci(8)); return 0; } 출처: https://hyeonstorage.tistory.com/354?..
[C] 재귀함수를 비재귀함수로 바꾸기 2 (재귀함수 2개) 재귀함수가 2개인 재귀함수의 경우 재귀함수들과 실제 작업하는 부분의 순서에 따라 비재귀 함수로 변경하는 방법이 조금 복잡하다. 1. 실제작업하는 부분이 처음에 실행될 때 (1) 재귀 함수 // 전위 표기법 void preorder_traverse(node *t){ if (t != tail){ visit(t); // 실제 작업하는 부분 preorder_traverse(t->left); // 재귀 1 preorder_traverse(t->right); // 재귀 2 } } (2) 비재귀 함수 // 전위 표기법 비재귀 함수 void non_recursive_preorder_traverse(node *t){ push(t); while (!is_stack..
[C] 재귀함수를 비재귀 함수로 바꾸기 1 (재귀 한번) 재귀 호출을 사용하는 함수는 그렇지 않은 함수에 비해 속도가 느리다. (항상 그런것은 아니다.)이는 재귀 호출이 연속적인 함수 호출로 이루어지기에 함수를 호출하기 위한 준비(오버헤드)에 소요되는 시간이 많기 때문이다.속도가 별로 필요가 없는 경우에는 재귀 함수를 그대로 사용해도 되지만 속도를 요하는 내부 루프 내라면 비재귀 함수로 바꾸어야 한다. 재귀 호출을 사용하는 함수는 시스템 다운의 우려가 있다.재귀 함수는 자신을 수없이 많이 호출하는 경우가 많다. 함수를 호출할 때는 인자 리스트와 지역 변수, 그리고 호출하는 곳의 주소를 내부 스택에 저장해두어야 하는데 재귀 호출이 빠지지 않고 계속해서 더해지는 경우에는 내부 스택의 영역을 벗어나 힘 영역까..
[C] Tree 로 전위, 중위, 후위 표기법 출력하기 후위 표기법 연산을 Tree에 입력하여, 전위, 중위, 후위 표기법으로 출력 한다. * 중위 표기법의 경우 정상적인 연산이 되도록 표시하려면 괄호를 추가하는 보완이 필요하다. Colored By Color Scripter™#include #include typedef struct _node{ int key; struct _node *left; struct _node *right; }node; node *head, *tail; #define MAX 100 node *stack[MAX]; int top; void init_stack(void){ top = -1; } node *push(node *t){ if (top >= MAX - 1){ printf(..
[C] Queue 리스트로 구현 Queue를 리스트로 구현하게 되면, 동적으로 메모리를 할당할 수 있어 전체 메모리가 full 되지 않는한, overflow가 발생하지 않는다.하지만 배열에 비해서 링크 처리를 해줘야 하며, 링크만큼의 크기를 차지한다. 큐는 처리에 지연이 발생할때, 입려된 명령이나 자료를 대기하기 위해 많이 사용한다.특히 BIOS 키보드 버퍼나 마우스 이벤트를 큐에 저장하여 순서대로 처리하는데 사용한다. #include typedef struct _dnode{ int key; struct _dnode *prev; struct _dnode *next; }dnode; dnode *head, *tail; void init_queue(void){ head = (dnode*)malloc(sizeo..