knockon rev 1week TIL

1. 헤더파일

1) 헤더파일

- #include <stdio.h>, #include <stdlib.h>와 같이 사용됨. 여러 함수들이 들어있음

2) 헤더파일의 역할

 

• 함수, 구조체, 상수, 매크로 등의 선언부를 담고 있는 파일.
• 중복 선언을 방지하고, 여러 .c 파일에서 같은 선언을 공유할 수 있게 해줌.

C 컴파일러는 .h파일을 전처리 단계에서 텍스트처럼 그대로 가져와 포함시킴.

 

 

2) 코드 이해

//다음과 같은 코드를 이해하고, 작성해봅시다.
//main.c
#include "hacker.h" // 사용자 정의 헤더파일 포함

int main(){
    // new_hacker 함수를 통해 hacker 구조체 포인터 생성 및 초기화
    hacker* qwertyou = new_hacker();

    // 이름과 나이 출력
    printf("%s's age is %d\n", qwertyou->name, qwertyou->age);
    
    // 이름과 레벨 출력
    printf("%s's level is %d\n", qwertyou->name, qwertyou->level);

    // 보유 기술 목록 출력
    printf("\n\n-----qwertyou's skill list-----\n");
    for(int i = 0; i < qwertyou->skill_num; i++){
        printf("%s's skill%d : %s\n", qwertyou->name, i, qwertyou->skill_list[i]);
    }
}

 

//hacker.h
#pragma once // 헤더파일 중복 포함 방지

#include <string.h>  // 문자열 처리 함수들 (strcpy 등)
#include <stdio.h>   // 표준 입출력 함수 (printf, scanf 등)
#include <unistd.h>  // write 함수 사용을 위한 헤더
#include <stdlib.h>  // 동적 메모리 함수 (malloc, free 등)

// 해커 정보를 담는 구조체 정의
typedef struct hacker {
    char name[50];       // 이름
    unsigned int age;    // 나이
    char** skill_list;   // 보유 기술 목록 (문자열 배열)
    int skill_num;       // 기술 개수
    int level;           // 레벨
} hacker;

// 함수 선언
int input_name(hacker*);
int input_age(hacker*);
int input_new_skill(hacker*);

// 해커 객체를 생성하고 입력받는 함수 정의
hacker* new_hacker() {
    hacker* new_ptr = (hacker*)malloc(sizeof(hacker)); // 구조체 메모리 동적 할당

    memset(new_ptr->name, '\0', sizeof(new_ptr->name)); // 이름 초기화
    new_ptr->skill_num = 0;  // 기술 개수 초기화
    new_ptr->level = 1;      // 레벨 기본값

    new_ptr->skill_list = (char**)malloc(sizeof(char*)); // 기술 목록 포인터 초기화

    // 사용자로부터 정보 입력받기
    input_name(new_ptr);
    input_age(new_ptr);
    input_new_skill(new_ptr);

    return new_ptr; // 초기화된 구조체 포인터 반환
}

// 이름 입력
int input_name(hacker* ptr){
    write(1, "Input the name : ", 17); // 출력 (write는 시스템 콜)
    return scanf("%s", ptr->name);     // 사용자로부터 문자열 입력
}

// 나이 입력
int input_age(hacker* ptr){
    printf("Input the age : ");
    return scanf("%u", &ptr->age);
}

// 기술 입력 및 skill_list에 추가
int input_new_skill(hacker* ptr){
    write(1, "Input new Skill : ", 18);
    
    char buf[50] = {0,};        // 입력 버퍼 초기화
    scanf("%s", buf);           // 기술 입력받기

    char* tmp = (char*)malloc(strlen(buf)+1); // 입력받은 문자열 크기만큼 동적 할당
    strcpy(tmp, buf);                          // 버퍼 내용을 tmp로 복사

    ptr->skill_num++;                  // 기술 개수 증가
    increase_size(&(ptr->skill_list)); // skill_list 배열 크기 증가

    ptr->skill_list[ptr->skill_num - 1] = tmp; // 새로운 기술 추가
    return ptr->skill_num;
}

// skill_list 배열 크기를 하나 더 늘리는 함수
void increase_size(char*** skill_list) {
    if (*skill_list == NULL) {
        *skill_list = (char**)malloc(sizeof(char*)); // 최초 생성
        (*skill_list)[0] = NULL;
        return;
    }

    int org_size = sizeof(*skill_list) / sizeof(char*);//포인터 크기만 계산하므로 원소 개수를 알 수 없음
    // char** new_ptr = (char**)malloc(sizeof(char*) * (ptr->skill_num));

    // 새로운 배열 생성
    char** new_ptr = (char**)malloc(sizeof(char*) * (org_size + 1));

    // 기존 내용 복사
    for (int i = 0; i < org_size; i++) {
        new_ptr[i] = (*skill_list)[i];
    }

    free(*skill_list);       // 기존 배열 메모리 해제
    *skill_list = new_ptr;   // 새 배열 주소로 교체
}

 

 

 

 

2. 연결리스트

 

1) 연결리스트와 배열의 차이점

- 메모리에 연속적으로 데이터가 저장되어있는 배열과는 달리 연결 리스트는 데이터와 포인터를 가진 노드가 서로 연결되어있는 방법으로 데이터를 저장하는 자료구조

- 데이터의 개수가 가변적이고 데이터를 추가하거나 삭제하는 작업에 용이

- 배열: 메모리에 연속적으로 저장됨 → 탐색은 빠르나, 삽입/삭제가 느림

- 연결 리스트: 메모리에 불연속적으로 저장되며, 각 노드가 다음 노드를 가리키는 방식 → 삽입/삭제가 빠름, 탐색은 느림

2) 단일 연결 리스트

(1) 구성

 

• 각 노드는 두 가지 요소를 가짐:
  • 데이터(data)
  • 다음 노드를 가리키는 포인터(next)
• 마지막 노드의 next는 NULL

typedef struct Node {
    int data;
    struct Node* next;
} Node;

 

(2) 새로운 노드 생성하는 법

Node* create_node(int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

(3) 노드 삭제하는 법

void delete_node(Node** head, int target) {
    Node* temp = *head;
    Node* prev = NULL;

    while (temp != NULL && temp->data != target) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return; // 찾는 노드 없음

    if (prev == NULL) {
        *head = temp->next; // 첫 번째 노드 삭제
    } else {
        prev->next = temp->next; // 중간 or 마지막 노드 삭제
    }

    free(temp);
}

(4) 데이터 탐색하는 법

Node* search_node(Node* head, int target) {
    while (head != NULL) {
        if (head->data == target) return head;
        head = head->next;
    }
    return NULL; // 찾는 값 없음
}

3) 이중 연결 리스트

(1) 구성

각 노드는 세 가지 요소를 가짐:

• 데이터(data)
• 이전 노드를 가리키는 포인터(prev)
• 다음 노드를 가리키는 포인터(next)

typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
} DNode;

(2) 새로운 노드 생성하는 법

DNode* create_dnode(int data) {
    DNode* new_node = (DNode*)malloc(sizeof(DNode));
    new_node->data = data;
    new_node->prev = NULL;
    new_node->next = NULL;
    return new_node;
}

(3) 노드 삭제하는 법

void delete_dnode(DNode** head, DNode* del_node) {
    if (*head == NULL || del_node == NULL) return;

    if (*head == del_node) *head = del_node->next;
    if (del_node->next) del_node->next->prev = del_node->prev;
    if (del_node->prev) del_node->prev->next = del_node->next;

    free(del_node);
}

(4) 데이터 탐색하는 법

DNode* search_dnode(DNode* head, int target) {
    while (head != NULL) {
        if (head->data == target) return head;
        head = head->next;
    }
    return NULL;
}

4) 원형 연결 리스트 

(1) 구성

 

• 마지막 노드의 next가 첫 번째 노드를 가리킴
• 구조는 단일 연결 리스트와 유사

typedef struct CNode {
    int data;
    struct CNode* next;
} CNode;

 

(2) 새로운 노드 생성하는 법

CNode* create_cnode(int data) {
    CNode* new_node = (CNode*)malloc(sizeof(CNode));
    new_node->data = data;
    new_node->next = new_node; // 자기 자신을 가리킴
    return new_node;
}

(3) 노드 삭제하는 법

void delete_cnode(CNode** head, int target) {
    if (*head == NULL) return;

    CNode *curr = *head, *prev = NULL;

    // 첫 노드가 대상일 경우 따로 처리
    if (curr->data == target) {
        while (curr->next != *head) curr = curr->next;
        curr->next = (*head)->next;
        free(*head);
        *head = curr->next;
        return;
    }

    curr = *head;
    do {
        prev = curr;
        curr = curr->next;
        if (curr->data == target) {
            prev->next = curr->next;
            free(curr);
            return;
        }
    } while (curr != *head);
}

(4) 데이터 탐색하는 법

CNode* search_cnode(CNode* head, int target) {
    if (head == NULL) return NULL;

    CNode* curr = head;
    do {
        if (curr->data == target) return curr;
        curr = curr->next;
    } while (curr != head);

    return NULL;
}

5) 도전 과제

 

(1) 헤더파일을 이용하여 이중 연결 리스트를 구현

dlist.h

#pragma once
typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
} DNode;

DNode* create_dnode(int);
void delete_dnode(DNode**, DNode*);
DNode* search_dnode(DNode*, int);

(2) 헤더파일을 이용하여 원형 연결 리스트를 구현

clist.h

#pragma once
typedef struct CNode {
    int data;
    struct CNode* next;
} CNode;

CNode* create_cnode(int);
void delete_cnode(CNode**, int);
CNode* search_cnode(CNode*, int);

 

3. 스택&큐

1) 스택

(1) 스택의 특성

- 후입선출(LIFO, Last In First Out)의 구조로 이루어진 자료구조

- 항상 스택의 한 쪽 끝에서만 데이터를 넣고 꺼낼 수 있음

- 데이터를 넣는 과정을 Push, 다시 데이터를 꺼내는 과정을 Pop

- 사용 예: 함수 호출 스택, 웹 브라우저 뒤로 가기, 괄호 검사

(2) 스택의 작동 원리

 

• 배열 혹은 연결 리스트의 한 쪽 끝을 Top이라 정의하고
• Top을 기준으로 삽입/삭제가 이루어짐
• Top이 -1이면 스택이 비어있는 상태

 

(3) push와 pop

연산	설명	예시
Push	데이터 삽입	Push(10) → [10]
Pop	가장 최근 값 꺼내기	Pop() → 10, 결과: []

 

2) 큐 

(1) 큐의 특성

- 선입선출(FIFO, First In First Out)의 구조로 이루어진 자료구조

- 큐의 한 쪽 끝에서는 데이터 삽입만 가능하고, 반대쪽 끝에서는 삭제만 가능

- 데이터를 넣는 과정을 Enqueue, 다시 데이터를 꺼내는 과정을 Dequeue

- 사용 예: 프린터 작업 대기열, BFS 탐색, 실시간 작업 처리

(2) 큐의 작동 원리

 

• Front와 Rear 포인터 사용
• Enqueue → rear 위치에 삽입
• Dequeue → front 위치에서 삭제
• front == rear이면 비어있는 상태

 

(3) Enqueue와 Dequeue

연산	설명	예시
Enqueue	데이터 삽입	Enqueue(10) → [10]
Dequeue	가장 먼저 값 꺼내기	Dequeue() → 10, 결과: []

 

3) 도전 과제

(1) 배열과 연결 리스트를 활용하여 push와 pop 기능이 작동하는 스택을 구현해 봅시다.

배열 기반 스택

#include <stdio.h>
#define SIZE 100

int stack[SIZE];
int top = -1;

void push(int value) {
    if (top < SIZE - 1) {
        stack[++top] = value;
    } else {
        printf("Stack Overflow!\n");
    }
}

int pop() {
    if (top >= 0) {
        return stack[top--];
    } else {
        printf("Stack Underflow!\n");
        return -1;
    }
}

연결리스트 기반 스택

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* top = NULL;

void push(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = top;
    top = new_node;
}

int pop() {
    if (top == NULL) {
        printf("Stack Underflow!\n");
        return -1;
    }
    int val = top->data;
    Node* temp = top;
    top = top->next;
    free(temp);
    return val;
}

 

(2) 배열과 연결 리스트를 활용하여 Enqueue와 Dequeue 기능이 동작하는 큐를 구현해봅시다.

배열 기반 큐

#include <stdio.h>
#define SIZE 100

int queue[SIZE];
int front = 0, rear = 0;

void enqueue(int value) {
    if (rear < SIZE) {
        queue[rear++] = value;
    } else {
        printf("Queue Overflow!\n");
    }
}

int dequeue() {
    if (front < rear) {
        return queue[front++];
    } else {
        printf("Queue Underflow!\n");
        return -1;
    }
}

연결리스트 기반 큐

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* front = NULL;
Node* rear = NULL;

void enqueue(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = NULL;
    if (rear) rear->next = new_node;
    rear = new_node;
    if (!front) front = new_node;
}

int dequeue() {
    if (!front) {
        printf("Queue Underflow!\n");
        return -1;
    }
    int val = front->data;
    Node* temp = front;
    front = front->next;
    if (!front) rear = NULL;
    free(temp);
    return val;
}

 

 

4. 트리

1) 트리의 개념

- 나뭇가지처럼 노드들이 연결된 비선형적고 계층적인 자료구조

- 부모 노드와 자식 노드의 관계로 노드들이 연결되며 트리 구조를 이룸

- 루트 노드(root)에서 시작해 가지(branch)처럼 뻗어 나가며 확장됨

- 사이클이 없는 연결 그래프 형태

- 예: 파일 시스템, 조직도, 게임 트리, 이진 탐색 트리 등

2) 트리의 순회 방법

트리를 탐색하는 방법 3가지 (깊이우선 방식 기준):

• 전위 순회 (Preorder): Root → Left → Right
• 중위 순회 (Inorder): Left → Root → Right
• 후위 순회 (Postorder): Left → Right → Root

예시 트리:
        A
       / \
      B   C
     / \   \
    D   E   F

전위:   A B D E C F  
중위:   D B E A C F  
후위:   D E B F C A

3) 이진 트리, 완전 이진 트리

 

• 이진 트리: 모든 노드가 최대 2개의 자식 노드를 가지는 트리
• 완전 이진 트리: 마지막 레벨을 제외하고는 모든 레벨이 가득 차 있는 이진 트리. 마지막 레벨은 왼쪽부터 채워져야 함.

 

4) 이진 탐색 트리(BST)

• 왼쪽 서브트리는 현재 노드보다 작은 값
• 오른쪽 서브트리는 현재 노드보다 큰 값
• 탐색, 삽입, 삭제 연산을 평균 O(log n) 시간에 처리 가능 (균형 잡혔을 경우)

5) 도전 과제

(1) 트리에서 사용되는 용어 ( ex. 부모 노드, 자식 노드, 깊이, 높이, 차수, 등등) 들을 찾아보고 이해해봅시다.

용어	설명
루트 노드 (Root)	트리의 시작 노드
부모 노드 (Parent)	다른 노드의 상위 노드
자식 노드 (Child)	부모에 연결된 하위 노드
형제 노드 (Sibling)	같은 부모를 가지는 노드
단말 노드 (Leaf)	자식이 없는 노드
내부 노드 (Internal)	자식이 있는 노드
깊이 (Depth)	루트에서 특정 노드까지의 거리
높이 (Height)	특정 노드에서 가장 먼 단말 노드까지의 거리
차수 (Degree)	자식 노드의 수

(2) 다음의 구조체를 활용하여 트리 노드를 구현하고, 전위 순회, 중위 순회, 후위 순회 알고리즘을 만들어봅시다.

#include <stdio.h>
#include <stdlib.h>

// 트리 노드 정의
typedef struct TreeNode {
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 노드 생성 함수
TreeNode* createNode(char data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// 전위 순회: Root -> Left -> Right
void preorder(TreeNode* root) {
    if (root) {
        printf("%c ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// 중위 순회: Left -> Root -> Right
void inorder(TreeNode* root) {
    if (root) {
        inorder(root->left);
        printf("%c ", root->data);
        inorder(root->right);
    }
}

// 후위 순회: Left -> Right -> Root
void postorder(TreeNode* root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        printf("%c ", root->data);
    }
}

// 테스트용 메인 함수
int main() {
    /*
        예시 트리:
            A
           / \
          B   C
         / \   \
        D   E   F
    */
    TreeNode* root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');
    root->left->left = createNode('D');
    root->left->right = createNode('E');
    root->right->right = createNode('F');

    printf("Preorder: ");
    preorder(root);
    printf("\n");

    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("Postorder: ");
    postorder(root);
    printf("\n");

    return 0;
}