※중간고사대비용_C언어_라이브러리(작성중)

● 3주차_삽입식 힙(최대힙,최소힙)

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
#define SIZE 101
 
typedef int type;
 
typedef struct _heap {
    type heap[SIZE];
    int size;
}heap;
 
int Parent(int i)
{
    return i/2;
}
 
int LeftChild(int i)
{
    return 2 * i;
}
 
int RightChild(int i)
{
    return 2 * i + 1;
}
 
//삽입식 힙(최대힙) 
// UpHeap, DownHeap, InsertHeap, DeleteHeap
void max_Upheap(heap* H,int i) 
{
    while (i > 1 && H->heap[i] > H->heap[Parent(i)])
    {
        type tmp = H->heap[i];
        H->heap[i] = H->heap[Parent(i)];
        H->heap[Parent(i)] = tmp;
 
        i = Parent(i);
    }
}
 
void max_DownHeap(heap* H,int i) 
{
    int Best = i;
    int L = LeftChild(i);
    int R = RightChild(i);
 
    if (L <= H->size && H->heap[L] > H->heap[Best])Best = L;
    if (R <= H->size && H->heap[R] > H->heap[Best])Best = R;
 
    if (Best != i)
    {
        type tmp = H->heap[i];
        H->heap[i] = H->heap[Best];
        H->heap[Best] = tmp;
 
        max_DownHeap(H, Best);
    }
 
}
 
void Max_InsertHeap(heap* H,type data) 
{
    if (H->size >= SIZE)return;
 
    H->heap[++H->size] = data;
 
    max_Upheap(H, H->size);
    
    printf("0\n");
}
 
type Max_DeleteHeap(heap* H)
{
    if (H->size <= 0)return -1;
 
    type root = H->heap[1];
 
    H->heap[1] = H->heap[H->size--];
 
    max_DownHeap(H, 1);
 
    return root;
}
 
//삽입식 힙(최소힙) 
// UpHeap, DownHeap, InsertHeap, DeleteHeap
 
void min_Upheap(heap* H,int i) 
{
    while (i > 1 && H->heap[i] < H->heap[Parent(i)])
    {
        type tmp = H->heap[i];
        H->heap[i] = H->heap[Parent(i)];
        H->heap[Parent(i)] = tmp;
 
        i = Parent(i);
    }
}
 
void min_DownHeap(heap* H,int i) 
{
    int Smallest = i;
    int L = LeftChild(i);
    int R = RightChild(i);
 
    if (L <= H->size && H->heap[L] < H->heap[Smallest])Smallest = L;
    if (R <= H->size && H->heap[R] < H->heap[Smallest])Smallest = R;
 
    if (Smallest != i)
    {
        type tmp = H->heap[i];
        H->heap[i] = H->heap[Smallest];
        H->heap[Smallest] = tmp;
 
        min_DownHeap(H, Smallest);
    }
 
}
 
void Min_InsertHeap(heap* H,type data) 
{
    if (H->size >= SIZE)return;
 
    H->heap[++H->size] = data;
 
    min_Upheap(H, H->size);
 
    printf("0\n");
}
 
 
type Min_DeleteHeap(heap* H)
{
    if (H->size <= 0)return -1;
 
    type root = H->heap[1];
 
    H->heap[1] = H->heap[H->size--];
 
    min_DownHeap(H, 1);
 
    return root;
}
 
 
//PrintHeap
void PrintHeap(heap* H) 
{
    for (int i = 1; i <= H->size; i++)printf(" %d", H->heap[i]);
    printf("\n");
}
 
 
int main()
{
    char menu;
    int input;
    heap* Max_Heap = (heap*)malloc(sizeof(heap));
    heap* Min_Heap = (heap*)malloc(sizeof(heap));
    Max_Heap->size = 0;
    Min_Heap->size = 0;
 
    while (1) 
    {
        scanf("%c", &menu);
        getchar();
        if (menu == 'i')
        {
            scanf("%d", &input);
            getchar();
            Min_InsertHeap(Min_Heap, input);
        }
        else if (menu == 'd')
        {
            type result = Min_DeleteHeap(Min_Heap);
            printf("%d\n", result);
 
        }        
        else if (menu == 'p')
        {
            PrintHeap(Min_Heap);
        }
        else if (menu == 'q')
        {
            break;
        }
    }
 
 
    return 0;
}

 

● 4주차_상향식 힙(최대힙,최소힙) ※중복키들도 다룰수 있다.

기억해야할 점 :

• 루트노드( i=1) 포함해서 RBuildHeap 작업한다.

    void max_RBuildHeap(heap* H) 
{
	for (int i = Parent(H->size); i >= 1; i--)max_DownHeap(H, i);
}

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
#define SIZE 101
 
typedef int type;
 
typedef struct _heap {
    type heap[SIZE];
    int size;
}heap;
 
int Parent(int i)
{
    return i/2;
}
 
int LeftChild(int i)
{
    return 2 * i;
}
 
int RightChild(int i)
{
    return 2 * i + 1;
}
 
//상향식 힙(최대힙) 
// DownHeap, RBuildHeap,RePlaceSortHeap
 
 
void max_DownHeap(heap* H,int i) 
{
    int Best = i;
    int L = LeftChild(i);
    int R = RightChild(i);
 
    if (L <= H->size && H->heap[L] > H->heap[Best])Best = L;
    if (R <= H->size && H->heap[R] > H->heap[Best])Best = R;
 
    if (Best != i)
    {
        type tmp = H->heap[i];
        H->heap[i] = H->heap[Best];
        H->heap[Best] = tmp;
 
        max_DownHeap(H, Best);
    }
 
}
 
void max_RBuildHeap(heap* H) 
{
    for (int i = Parent(H->size); i >= 1; i--)max_DownHeap(H, i);
}
 
void Max_RePlaceSortHeap(heap*H) {
    
    max_RBuildHeap(H);
 
    int origin_size = H->size;
 
    for (int i = origin_size; i >= 1; i--) 
    {
        type tmp = H->heap[1];
        H->heap[1] = H->heap[H->size];
        H->heap[H->size] = tmp;
 
        H->size--;
 
        max_DownHeap(H,1);
    }
 
    H->size = origin_size;
 
}
 
 
 
 
 
//상향식 힙(최소힙) 
// DownHeap, RBuildHeap,RePlaceSortHeap
 
void min_DownHeap(heap* H, int i)
{
    int Smallest = i;
    int L = LeftChild(i);
    int R = RightChild(i);
 
    if (L <= H->size && H->heap[L] < H->heap[Smallest])Smallest = L;
    if (R <= H->size && H->heap[R] < H->heap[Smallest])Smallest = R;
 
    if (Smallest != i)
    {
        type tmp = H->heap[i];
        H->heap[i] = H->heap[Smallest];
        H->heap[Smallest] = tmp;
 
        min_DownHeap(H, Smallest);
    }
 
}
 
void min_RBuildHeap(heap* H) 
{
    for (int i = Parent(H->size); i >= 1; i--)min_DownHeap(H, i);
}
 
void Min_RePlaceSortHeap(heap*H) {
    
    min_RBuildHeap(H);
 
    int origin_size = H->size;
 
    for (int i = origin_size; i > 1; i--) 
    {
        type tmp = H->heap[1];
        H->heap[1] = H->heap[H->size];
        H->heap[H->size] = tmp;
 
        H->size--;
 
        min_DownHeap(H,1);
    }
 
    H->size = origin_size;
 
}
 
 
 
void min_Upheap(heap* H,int i) 
{
    while (i > 1 && H->heap[i] < H->heap[Parent(i)])
    {
        type tmp = H->heap[i];
        H->heap[i] = H->heap[Parent(i)];
        H->heap[Parent(i)] = tmp;
 
        i = Parent(i);
    }
}
 
 
//PrintHeap
void PrintHeap(heap* H) 
{
    for (int i = 1; i <= H->size; i++)printf(" %d", H->heap[i]);
    printf("\n");
}
 
 
int main()
{
    char menu;
    int input;
    heap* Max_Heap = (heap*)malloc(sizeof(heap));
    heap* Min_Heap = (heap*)malloc(sizeof(heap));
 
    int N;
 
    scanf("%d", &N);
 
    Max_Heap->size = N;
    Min_Heap->size = N;
 
    for (int i = 1; i <= N; i++)scanf("%d", &(Min_Heap->heap[i]));
 
    Min_RePlaceSortHeap(Min_Heap);
 
    PrintHeap(Min_Heap);
 
    /*
    for (int i = 1; i <= N; i++)scanf("%d", &(Max_Heap->heap[i]));
    Max_RePlaceSortHeap(Max_Heap);
 
    PrintHeap(Max_Heap);
    
 
    */
 
    free(Max_Heap);
    free(Min_Heap);
 
    return 0;
}

 

● 5주차_합병정렬, 퀵정렬 ※중복키도 다룰 수 있다.

=> 합병정렬(오름차순asc 내림차순dsc)

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
void Merge_dsc(int* A,int start, int mid ,int end) 
{
    int L = start;
    int R = mid + 1;
 
    int* B = (int*)malloc(sizeof(int) * (end - start + 1));
    int B_idx = 0;
 
    while (L <= mid && R <= end)
    {
        if (A[L] > A[R])
        {
            B[B_idx] = A[L];
            L++;
        }
        else
        {
            B[B_idx] = A[R];
            R++;
        }
 
        B_idx++;
    }
 
    while (L <= mid)
    {
        B[B_idx] = A[L];
        L++;
        B_idx++;
    }
    while (R <= end)
    {
        B[B_idx] = A[R];
        R++;
        B_idx++;
    }
 
    for (int i = 0; i < (end - start + 1); i++)A[start + i] = B[i];
 
    free(B);
}
 
void Merge_asc(int* A,int start, int mid ,int end) 
{
    int L = start;
    int R = mid + 1;
 
    int* B = (int*)malloc(sizeof(int) * (end - start + 1));
    int B_idx = 0;
 
    while (L <= mid && R <= end)
    {
        if (A[L] < A[R]) 
        {
            B[B_idx] = A[L];
            L++;
        }
        else
        {
            B[B_idx] = A[R];
            R++;
        }
 
        B_idx++;
    }
 
    while (L<=mid)
    {
        B[B_idx] = A[L];
        L++;
        B_idx++;
    }
    while (R<=end)
    {
        B[B_idx] = A[R];
        R++;
        B_idx++;
    }
 
    for (int i = 0; i < (end - start + 1); i++)A[start + i] = B[i];
 
    free(B);
}
 
 
void MergeSort(int* A, int start, int end) 
{
    if (start + 1 > end)return;
 
    //분할
 
    int mid = (start + end) / 2;
 
    MergeSort(A, start, mid);
    MergeSort(A, mid +1, end);
 
    //정복//내림차순 Merge
    Merge_dsc(A,start,mid,end);
    
    //★여기만 교체 하면 된다.
    /*
    //정복//오름차순 Merge
    Merge_asc(A,start,mid,end);    
    */
}
 
 
void PrintArr(int* A, int size)
{
    for (int i = 0; i < size; i++)printf(" %d", A[i]);
    printf("\n");
}
 
int main()
{
    int* A = NULL;
    int N;
 
    scanf("%d", &N);
 
    A = (int*)malloc(sizeof(int) * N);
 
    for (int i = 0; i < N; i++)scanf("%d", &A[i]);
 
    MergeSort(A, 0, N - 1);
 
    PrintArr(A, N);
 
    free(A);
 
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
int FindIndex(int start, int end) 
{
    return (rand() % (end - start + 1) + start);
}
 
//오름차순 Partition
int Partition_asc(int* A, int start, int end)
{
    int index = FindIndex(start, end);
 
    int tmp = A[end];
    A[end] = A[index];
    A[index] = tmp;
 
    int L = start;
    int R = end - 1;
 
    while (1)
    {
        while (L <= R && A[L] <= A[end])L++;
        while (L <= R && A[R] >= A[end])R--;
 
        if (L <= R)
        {
            tmp = A[L];
            A[L] = A[R];
            A[R] = tmp;
 
        }
        else break;
    }
 
    tmp = A[L];
    A[L] = A[end];
    A[end] = tmp;
 
    return L;
}
//내림차순 Partition
int Partition_dsc(int* A, int start, int end)
{
    int index = FindIndex(start, end);
 
    int tmp = A[end];
    A[end] = A[index];
    A[index] = tmp;
 
    int L = start;
    int R = end - 1;
 
    while (1)
    {
        while (L <= R && A[L] >= A[end])L++;
        while (L <= R && A[R] <= A[end])R--;
 
        if (L <= R)
        {
            tmp = A[L];
            A[L] = A[R];
            A[R] = tmp;
 
        }
        else break;
    }
 
    tmp = A[L];
    A[L] = A[end];
    A[end] = tmp;
 
    return L;
}
 
 
void QuickSort(int* A, int start, int end)
{
    if (start >= end)return;
 
    //오름차순 Partition
    int index = Partition_asc(A,start,end);
 
    /*
    //내림차순 Partition
    int index = Partition_dsc(A,start,end);
    */
 
    //분할
    QuickSort(A, start, index - 1);
    QuickSort(A, index +1, end);
 
}
 
void PrintArr(int* A, int size)
{
    for (int i = 0; i < size; i++)printf(" %d", A[i]);
    printf("\n");
}
 
int main()
{
    int* A = NULL;
    int N;
 
    scanf("%d", &N);
 
    A = (int*)malloc(sizeof(int) * N);
 
    for (int i = 0; i < N; i++)scanf("%d", &A[i]);
 
    QuickSort(A, 0, N - 1);
 
    PrintArr(A, N);
 
    free(A);
 
    return 0;
}

 

● 6주차_이분탐색_1_조건에 맞는 값 검색용 코드(준비중)

 

● 6주차_이분탐색_2_조건에 맞는 값 중 최솟값 찾기(준비중)

 

● 6주차_이분탐색_3_임의의 물건들을 딱 통 몇개로 나눠 담을 수 있도록 하는 통의 용량의 최솟값 찾기(준비중)

 

● 7주차_1_BSTree (삭제 대상이 2차일 때, FindMin(), FindMax() 후계자 탐색 코드 포함)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable : 4996)
 
typedef int type;
 
typedef struct _BSTree {
 
    struct _BSTree* left;
    struct _BSTree* right;
    type data;
 
}Node;
 
//트리할당 X, 트리의 노드 할당 O
Node* CreateBST(type data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->data = data;
 
 
    return newNode;
}
 
//SearchBST()
Node* SearchBST(Node* p, type data)
{
    if (p == NULL) //찾을 data가 트리에 없다는 뜻
    {
        return p;
    }
    if (p->data > data)
    {
        return SearchBST(p->left, data);
    }
    else if (p->data < data)
    {
        return SearchBST(p->right, data);
    }
    else return p;
 
}
 
//InsertBST()
void InsertBST(Node** p, type data)
{
    if ((*p) == NULL)
    {
        (*p) = CreateBST(data);
        return;
    }
 
    if ((*p)->data > data)
    {
        InsertBST(&((*p)->left), data);
    }
    else if ((*p)->data < data)
    {
        InsertBST(&((*p)->right), data);
    }
    else
    {
        //중복된 data가 트리에 존재
        return;
    }
}
 
//DeleteBST()
//삭제 대상이 2차일 때, 후계자 고르는 것이 2가지 방식이 존재
 
//방식1_ FindMin
//↘
//↙
 
Node* FindMin(Node* p)
{
    Node* tmp = p->right;
 
    while (tmp->left != NULL)
    {
        tmp = tmp->left;
    }
 
    return tmp;
}
 
//방식1_ FindMax
//↙
//↘
Node* FindMax(Node* p)
{
    Node* tmp = p->left;
 
    while (tmp->right != NULL)
    {
        tmp = tmp->right;
    }
 
    return tmp;
}
 
 
void DeleteBST(Node** p, type data)
{
    //삭제할 노드가 트리에 없다는 뜻
    if ((*p) == NULL)
    {
        return;
    }
 
    if ((*p)->data > data)
    {
        DeleteBST(&((*p)->left), data);
    }
    else if ((*p)->data < data)
    {
        DeleteBST(&((*p)->right), data);
    }
    else
    {
        //0차
        if ((*p)->left == NULL && (*p)->right == NULL)
        {
            free(*p);
 
            //◆놓친 부분
            (*p) = NULL;
        }
        //1치
        else if ((*p)->left == NULL)
        {
            Node* tmp = (*p)->right;
            free(*p);
            (*p) = tmp;
 
        }
        else if ((*p)->right == NULL)
        {
            Node* tmp = (*p)->left;
            free(*p);
            (*p) = tmp;
 
        }
        //2치
        else
        {
 
            //방식1_FindMin방식
            Node* tmp = FindMin((*p));
            (*p)->data = tmp->data;
            DeleteBST(&(*p)->right, tmp->data);
 
            /*
            //방식2_FindMax방식
            Node* tmp = FindMax((*p));
            (*p)->data = tmp->data;
            DeleteBST(&(*p)->left, tmp->data);
            */
 
        }
    }
}
 
void PreOrder(Node* p)//D L R
{
    if (p == NULL) return;
 
    printf(" %d", p->data);
 
    if (p->left != NULL)PreOrder(p->left);
 
    if (p->right != NULL)PreOrder(p->right);
}
 
void FreeTree(Node* p)//L R D
{
    if (p == NULL) return;
 
    if (p->left != NULL)FreeTree(p->left);
 
    if (p->right != NULL)FreeTree(p->right);
 
    free(p);
}
 
int main()
{
    Node* root = NULL;
    char command;
    int key;
 
    while (1)
    {
        scanf("%c", &command);
 
        if (command == 'i')
        {
            scanf("%d", &key);
            getchar();
            InsertBST(&root, key);
 
        }
        else if (command == 'd')
        {
            scanf("%d", &key);
            getchar();
            Node* search = SearchBST(root, key);
            if (search != NULL) {
                printf("%d\n", search->data);
                DeleteBST(&root, key);
            }
            else {
                printf("X\n");
            }
        }
        else if (command == 's')
        {
            scanf("%d", &key);
            getchar();
            Node* search = SearchBST(root, key);
            if (search != NULL) {
                printf("%d\n", search->data);
            }
            else {
                printf("X\n");
            }
 
        }
        else if (command == 'p')
        {
            PreOrder(root);
            printf("\n");
        }
        else if (command == 'q')
        {
            FreeTree(root);
            break;
        }
    }
 
    return 0;
}

● 7주차_2 : AVLTree 삽입,삭제 부분

기억해야할 점 :

• Rebalance메소드 

1. LL RR LR RL를 한번에 조건절로 모두 나눠야함
2. LL, RR의 L2, R2 의 GetBF값 >=0 || GetBF값 <= 0 로 0포함해야 오류가 나지 않는다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable : 4996)
 
typedef int type;
 
//BTree 구조체 
typedef struct _AVLTree
{
    type data;
    struct _AVLTree* Left;
    struct _AVLTree* Right;
}Node;
 
 
//노드 메모리 할당 메소드
Node* CreateNode(type data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->Left = NULL;
    newNode->Right = NULL;
}
 
//노드 검색 메소드
Node* Search(Node* p,type data)
{
    if (p == NULL)return p;
 
    if (p->data > data)
    {
        return Search(p->Left, data);
    }
    else if (p->data < data)
    {
        return Search(p->Right, data);
    }
    else return p;
}
 
void PreOrder(Node* p)
{
    if (p == NULL) return;
 
    printf(" %d", p->data);
 
    if (p->Left != NULL) PreOrder(p->Left);
    if (p->Right != NULL) PreOrder(p->Right);
}
 
//회전 메소드
Node* LL(Node* L1) 
{
    Node* L2 = L1->Left;
    L1->Left = L2->Right;
    L2->Right = L1;
 
    return L2;
}
 
Node* RR(Node* R1)
{
    Node* R2 = R1->Right;
    R1->Right = R2->Left;
    R2->Left = R1;
    return R2;
}
 
Node* LR(Node* L1)
{
    Node* L2 = L1->Left;
 
    L1->Left = RR(L2);
 
    return LL(L1);
}
 
Node* RL(Node* R1)
{
    Node* R2 = R1->Right;
 
    R1->Right = LL(R2);
 
    return RR(R1);
}
 
 
//단말노드 높이 : 1
int GetHeight(Node* p)
{
    if (p == NULL) return 0;
 
    return ((GetHeight(p->Left)> GetHeight(p->Right))? GetHeight(p->Left)+1 : GetHeight(p->Right)+1);
}
 
//단말 노드 BF :0
int GetBF(Node* p)
{
    if (p == NULL) return 0;
 
    return GetHeight(p->Left) - GetHeight(p->Right);
}
 
//rebalance
//주의1_
//한방에 4가지 Case 다 나눈다.
//그래야 오류가 안남
 
//주의2_
//LL 상황 : L2의 BF값 조건 >=0
//RR 상황 : R2의 BF값 조건 <=0
void Rebalance(Node** p)
{
    int BF = GetBF(*p);
    
    if (BF > 1 && GetBF((*p)->Left) >= 0) 
    {
        (*p) = LL(*p);
    }
    else if (BF > 1 && GetBF((*p)->Left) < 0)
    {
        (*p) = LR(*p);
    }
    else if (BF < -1 && GetBF((*p)->Right) <= 0)
    {
        (*p) = RR(*p);
    }
    else if (BF < -1 && GetBF((*p)->Right) > 0)
    {
        (*p) = RL(*p);
    }
}
 
void InsertAVL(Node** p,type data)
{
    if (*p == NULL)
    {
        *p = CreateNode(data);
 
        //return(x)
    }
    else 
    {
        if ((*p)->data > data)InsertAVL(&((*p)->Left), data);
        else if ((*p)->data < data)InsertAVL(&((*p)->Right), data);
        else return;
 
    }
 
    Rebalance(p);
}
 
Node* FindMin(Node* p)
{
    Node* tmp = p->Right;
 
    while (tmp->Left != NULL)tmp = tmp->Left;
 
    return tmp;
}
Node* FindMax(Node* p)
{
    Node* tmp = p->Left;
 
    while (tmp->Right != NULL)tmp = tmp->Right;
 
    return tmp;
}
 
void DeleteAVL(Node** p , type data)
{
    if ((*p) == NULL) 
    {
        return;
    }
 
    if ((*p)->data > data)DeleteAVL(&((*p)->Left), data);
    else if ((*p)->data < data)DeleteAVL(&((*p)->Right), data);
    else
    {
        //0차
        if ((*p)->Left == NULL && (*p)->Right == NULL)
        {
            free(*p);
            (*p) = NULL;
        }
        //1차
        else if ((*p)->Left == NULL)
        {
            Node* tmp = (*p)->Right;
            free(*p);
            (*p) = tmp;
        }
        else if ((*p)->Right == NULL)
        {
            Node* tmp = (*p)->Left;
            free(*p);
            (*p) = tmp;
 
        }
        //2차
        else 
        {
            Node* tmp = FindMin(*p);
            (*p)->data = tmp->data;
            DeleteAVL(&(*p)->Right, tmp->data);
        /*
         최솟값 노드 삭제 부분
            Node* tmp = FindMax(*p);
            (*p)->data = tmp->data;
            DeleteAVL(&(*p)->Left, tmp->data);
        */
        }
 
    }
 
 
     Rebalance(p);
 
}
 
int main()
{
    Node* root = NULL;
    int data;
    char command;
 
    while (1)
    {
        scanf("%c", &command);
 
        if (command == 'i')
        {
            scanf("%d", &data);
            InsertAVL(&root, data);
 
        }
        else if (command == 's')
        {
            scanf("%d", &data);
            Node* search = Search(root, data);
            if (search == NULL) {
                printf("X\n");
            }
            else {
                printf("%d\n", search->data);
            }
 
        }
        else if (command == 'p')
        {
            PreOrder(root);
            printf("\n");
        }
        else if (command == 'd')
        {
            scanf("%d", &data);
            Node* search = Search(root, data);
            if (search == NULL) {
                printf("X\n");
            }
            else {
                printf("%d\n", search->data);
                DeleteAVL(&(root), data);
            }
        }
        else if (command == 'q')
        {
            break;
        }
 
 
    }
 
 
    return 0;
}