크래프톤

1. RB Tree 삽입 - 내용 정리 2. RB Tree 삭제 - 내용 정리

1. 큐를 이용해 순차적으로 탐색(BFS 방식?) 조건을 3가지로 구분해서 구현 자식 노드가 없는 경우 왼쪽 자식 노드만 있는 경우 오른쪽 자식 노드만 있는 경우 void levelOrderTraversal(BSTNode *root) { Queue *q = malloc(sizeof(Queue)); BSTNode *cur; q->head = NULL; q->tail = NULL; enqueue(&(q->head), &(q->tail), root); while (!isEmpty(q->head)) { cur = dequeue(&(q->head), &(q->tail)); printf("%d ", cur->item); if (cur->left == NULL && cur->right != NULL) { enqueu..

1. 두 개의 트리 구조적 일치 확인하기(값, 구조 동일) 트리의 노드를 비교해가면서 다르면 0을 반환 int identical(BTNode *tree1, BTNode *tree2) { int result1, result2; if (tree1->item != tree2->item) { return 0; } if (tree1 == NULL && tree2 == NULL) { return 1; } result1 = identical(tree1->left, tree2->left); result2 = identical(tree1->right, tree2->right); if (result1 == result2) { return 1; } else { return 0; } } 2. 트리의 최대 높이 구하기 노드가 ..

1. 연결 리스트를 이용해 스택 만들기 큐는 선입선출(FiFO : First In, First Out)이고, 스택은 후입선출(LIFO : Last In, First Out)이므로 구현이 약간 다름 void createStackFromLinkedList(LinkedList *ll, Stack *s) { ListNode *cur = ll->head; ListNode *cur_s = s->ll.head; ListNode *new_node; if (cur == NULL) { return; } while (cur != NULL) { // 새로운 노드를 만들고 메모리 할당을 받아 주소를 저장 new_node = malloc(sizeof(ListNode)); // 스택에 노드가 있는 경우 if (s->ll.head ..

1. 연결 리스트를 이용해 큐를 만들기 큐에 첫 번째 노드를 생성하는 경우(큐가 비었을 경우) 큐가 비지 않고 노드가 있는 경우로 나누어서 노드를 추가 void createQueueFromLinkedList(LinkedList *ll, Queue *q) { ListNode *cur = ll->head; ListNode *tail, *new_Node = NULL; if (cur == NULL) { return; } while (cur != NULL) { // 새로운 노드에 메모리를 할당 받아 주소값을 저장 new_Node = malloc(sizeof(ListNode)); if (q->ll.head == NULL) { // 큐가 비었다면 연결 리스트의 cur값의 item을 new_Node의 item에 저장 ..

1. 홀수를 가진 노드를 뒤로 넣어 정렬하기 해결하지 못한 문제 분석하다가 홀수를 처리하는 과정에서 포인터를 이상한 곳에 지정해 세그멘테이션 폴트 발생 꼬리가 현재 노드(홀수)를 next로 가리킴 현재(홀수)의 전 노드가 현재(홀수)의 next를 가리킴 현재(홀수)의 next를 지움(NULL) cur를 이전 노드로 이동 꼬리 노드를 현재(홀수) 이동시킨 노드로 이동 void moveOddItemsToBack(LinkedList *ll) { ListNode *cur, *prev, *tail; cur = ll->head; int size = ll->size; while (cur != NULL) { prev = cur; cur = cur->next; tail = prev; } cur = ll->head; pr..

1. 정렬하면서 노드 삽입하기 ll->head가 없는경우 가장 작은 수가 들어오는 경우 중간 크기의 수가 들어오는 경우 가장 큰 수가 들어오는 경우 int insertSortedLL(LinkedList *ll, int item) { ListNode *pre, *cur, *temp; if (ll->head == NULL) { cur = ll->head; ll->head = malloc(sizeof(ListNode)); ll->head->item = item; ll->head->next = NULL; ll->size++; printf("Head 추가\n"); return 0; } cur = ll->head; pre = NULL; while (cur != NULL) { if (cur->item == item)..