[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..

[C] Queue 배열로 구현 Queue는 스택과 반대로 먼저 들어온 데이터가 먼저나가는 FIFO(First In First Out) 구조이다. 큐를 배열로 구현할 때는, Overflow를 주의해야 한다.큐는 put과 get이 다른 통로로 구성되어 있기 때문에 배열에서 자료가 들어오는(put) rear 와 자료가 나가는(get) front의 포인터를 유지한다.하지만 put()과 get()이 발생하면서 front 와 rear 포인터는 계속적으로 증가하고 제한된 크기의 배열을 넘어가게 된다. 이러한 문제를 막기위해 배열의 마지막+1 은 0 으로 전환해주는 원형 큐를 사용하기도 한다.원형 큐를 사용할 때 주의할 점은, rear의 포인터는 마지막 자료가 아닌 put() 수행시 들어올 자료의 공간을 가리킨다. 이..

[C] 사칙연산 계산 (후위표기법) 우리는 흔히 연산을 표현할 때 중위 표기법을 사용한다.중위 표기법을 사용하여 우선순위를 판단하여 연산 순서를 정한다.하지만, 컴퓨터는 순차적으로 처리하기 때문에 중위 표기법으로는 정확한 순서로 연산에 어려움이 있다. 따라서, 컴퓨터가 연산할 때는 후위표기법을 사용한다.후위표기법으로 변환하고, 후위표기법을 연산하는데 스택을 사용한다. (1) 중위표기법 -> 후위표기법 1. '(' 를 만나면 스택에 푸시한다.2. ')' 를 만나면 스택에서 '('가 나올 때까지 팝하여 출력하고 '(' 는 팝하여 버린다.3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지 팝하여 출력한 뒤에 자신을 푸시한다.4. 피연산자는 그냥 출력한다.5. 모든 입력이 끝나면 ..