[부스트코스 CS50] 6주차 심화 과정 💎 생각해보기

cs50 2기 6주차에서 배운 연결리스트, 트리, 트라이, 해쉬, 큐, 스택 등 여러 자료구조에 대해서 배웠다.

 

심화 과정으로 구조체와 배열, 구조체와 연결 리스트를 사용해서 스택과 큐를 구현해보았다.

 

 

📌 문제 1

구조체와 배열을 통해 스택을 구현해보는 문제였는데 스택에 대해서 잘 이해하고 있고 배열의 인덱스를 잘 활용한다면 풀 수 있지 않을까 생각했다.
pop 함수와 peek 함수의 내용을 구현해보는 문제였기 때문에 빈칸 채우기 느낌의 문제였기 때문에 어렵지 않게 풀 수 있었던 것 같다.

 

따라서, 아래와 같이 풀어보았다.

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

typedef struct stack{
    int top;
    int capacity;
    int* array;
} Stack;

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int *)malloc(stack->capacity*sizeof(int));
    return stack;
}

int isFull(Stack* stack) {
    return stack->top == stack->capacity-1;
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, int item) {
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}

int pop(Stack* stack) {
    // 이곳을 채워주세요!
    if (isEmpty(stack))
        return -9999;

    // 값을 꺼내고나서 후위 연산자를 통해 결과 이후 -1 해준다.
    return stack->array[stack->top--];
}

int peek(Stack* stack) {
    // 이곳을 채워주세요!
    if (isEmpty(stack))
        return -9999;

    // 가장 위에 있는 값을 가져온다.
    return stack->array[stack->top];
}

int main() {
    Stack* stack = createStack(100);

    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
    push(stack, 40);

    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));

    push(stack, 50);
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    return 0;
}

 

[실행 결과]

 

 

📌 문제 2

두 번째로는 1번 문제와 다르게 배열이 아닌 연결 리스트를 통해 스택을 구현해보는 문제였다.
배열을 통해 풀었을 때는 금방 풀었기 때문에 연결 리스트를 사용하는 것도 금방 풀 수 있을 것이라고 생각했다.
하지만 나는 연결 리스트에 대해서 어느 정도 이해하고 있었다고 생각했는데 막상 코드로 풀어쓰려고 하니 막막했다.
그래서 연결 리스트가 동작되는 과정들을 열심히 그려가며 문제를 풀었던 것 같다.

 

풀면서 막혔던 부분은 스택이기 때문에 값이 순서대로 들어가면 마지막에 들어간 값부터 나와야 하는데
pop을 했을 때 가장 첫 번째 들어간 값이 나오고 그 이후에서야 마지막에 들어간 값부터 나왔다.
왜 그럴까 생각해봤더니 root 노드에 첫 번째 값을 넣어둔 후에 이후의 값들을 추가해줬기 때문에
가장 처음으로 나오게 되는 값은 가장 처음에 들어간 값이 되었던 것이다.
이렇게 숫자가 들어갔던 거였다.

 

10  40  30  20

 

따라서 값을 빼낼 때 10  40  30  20 이런 순서대로 나오게 된 거였다.

 

이런 문제를 어떻게 해결하게 되었냐면 값을 넣어줄 때 root의 위치를 마지막에 들어간 값으로 옮겨주면서 해결할 수 있었다.
처음에 잘 이해가 안되서 직접 과정을 그려가면서 이해할 수 있었던 것 같다.

 

처음에 root는 NULL 로 초기화과 되어있기 때문에 [그림 1] 과 같이 root 에 처음에 입력된 새로운 node의 값을 넣어준다.

 

[그림 1] root 노드가 null 일 경우

 

[그림 2] 이후에 새로운 노드(new node)를 넣어주게 되면 (push)

[그림 2] 새로운 노드 추가

 

[그림 3] 새로운 노드(new node)는 현재 root를 가리키게 한다. ( node->next = (*root) )

[그림 3] 새로운 노드는 root 노드를 가리킨다.

 

[그림 4] root 노드에 새로운 노드(new node)를 할당해준다. ( (*root) = node )
정확히 말하면 root 노드의 위치를 새로운 노드로 옮겨준다고 생각하면 쉽게 이해할 수 있다.

[그림 4] 그리고 root 노드에 새로운 노드를 할당해준다.

 

이렇게 값을 추가하게 되면 next 를 root 노드를 가리키게 하고 root 노드의 위치를 바꿔주면 된다.

 

그럼 pop 을 할 때 다음과 같이 진행하면 된다.

 

root 노드를 tmp 노드에 할당해준다. ( StackNode* tmp = (*root) )
root 노드와 tmp 노드는 같은 노드이기 때문에 그럼 다음과 같이 생각해볼 수 있다.

 

그리고 꺼내려고 하는 값을 저장해두고 (tmp->data)
root 노드를 tmp의 next 에 위치한 노드를 할당해준다. ( (*root) = tmp->next )
그럼 아래의 그림과 같이 이해할 수 있다.

 

그럼 값도 꺼냈고 root 노드이 위치도 바꿔주었으니 필요없는 tmp 노드는 free 함수를 통해 메모리를 해제해준다.

 

 

따라서, 코드는 !

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

typedef struct stackNode {
    int data;
    struct stackNode* next;
} StackNode;

StackNode* createStackNode(int data) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    node->data = data;
    node->next = NULL;
    return node;
}

int isEmpty(StackNode* root) {
    return !root;
}

void push(StackNode** root, int data) {
    // 이 부분을 구현해 주세요!
    StackNode* node = createStackNode(data);

    if ((*root) == NULL) { // root 노드가 NULL 일 경우
        (*root) = node;
    }

    node->next = (*root); // node 가 root 노드는 가리킨다.
    (*root) = node;       // root 노드에 node 를 할당해준다. = root 노드를 node 로 옮겨준다.

    printf("%d pushed to stack\n", data);
}

int pop(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    int popped;
    // 이 부분을 구현해 주세요!
    StackNode* tmp = (*root); // 임시로 root 노드를 저장해둔다.

    popped = tmp->data; // 꺼낼 값을 저장한다.
    (*root) = tmp->next; // root 노드를 다음 값의 위치로 옮겨준다.

    free(tmp); // 메모리를 해제해주면서 노드를 삭제한다.

    return popped;
}

int peek(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    return (*root)->data;
}

int main() {
    StackNode* root = NULL;

    push(&root, 10);
    push(&root, 20);
    push(&root, 30);
    push(&root, 40);

    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));

    push(&root, 50);
    printf("%d peeked from stack\n", peek(&root));
    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));
    printf("%d pop from stack\n", pop(&root));
    return 0;
}

 

[실행 결과]

 

 

📌 문제 3

세 번째 문제는 배열을 통해 큐를 구현하는 문제였다.
여기서 size와 capacity 를 잘 활용해서 큐를 구현하는 것이 중요하다는 생각이 들었다.
배열은 일정한 크기를 가지고 있기 때문에 일정한 크기를 잘 활용해 큐를 구현해줘야 한다.
따라서 정해진 용량을 이용해서 큐를 구현해보았다.

 

이 문제에서는 다른 값들은 0 으로 초기화를 해주었는데 눈에 띄는 값들은 capacity 의 값이 1000 이었고 rear 의 값이 capacity-1 인 999였다. 그럼 여기서 넣을 때에는 rear 위치의 값에 넣어주어야하고 뺄 때는 front 위치의 값을 빼주어야 하는데...
어떻게 구현해줘야 할까 생각을 많이했던 것 같다. 용량과 마지막 위치는 정해져있고 ? 도대체 뭘까 ...?

 

그래서 떠오른 방법이 나머지를 구해서 순서를 구해주는 방법이었다.
처음에 값을 입력할 때 rear의 값에 입력해주어야 하는데 0이 아니라 999로 되어있다.
그럼 용량은 1000 이고 rear가 가리키고 위치는 999 다.
이 값들을 이용해 0 번째 자리에 값을 어떻게 넣어줄 수 있을까?
rear의 값에서 1을 더하고 1000으로 나눈 나머지를 구하면 0이 나온다.
즉, 값을 넣는 위치는 rear+1 % capacity 가 된다.
값을 넣어주었으니 size 를 하나 증가시켜주면 끝 !

 

그럼 값을 빼낼 때는 front의 값을 빼주면 된다.
값을 빼내고 나서 front의 값은 그냥 1만 증가시켜주면 되지 않을까? 생각했었는데
그럼 계속해서 증가해서 1000이 넘어버리면 구할 수가 없게 된다.
따라서 이 경우에도 나머지 연산을 통해서 값을 증가시켜줄 수 있었다.
front + 1 % capacity
마지막으로 size를 하나 감소시켜주면 끝 !

 

추가적으로 queue 에 들어간 값들을 출력해주는 함수를 만들어서 출력해보았다.

 

그렇게 작성한 코드는 !

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

typedef struct queue {
    int front;
    int rear;
    int size;
    int capacity;
    int* array;
} Queue;

Queue* createQueue(int capacity) {
    Queue* queue = (Queue *)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->size = 0;
    queue->rear = capacity-1; // 왜 이렇게 초기화 했는지 잘 생각해 보세요!
    queue->array = (int *)malloc(sizeof(int)*queue->capacity);
    return queue;
}

int isFull(Queue* queue) {
    return (queue->size == queue->capacity);
}

int isEmpty(Queue* queue) {
    return (queue->size == 0);
}

void enqueue(Queue* queue, int item) {
    if (isFull(queue)) {
        return;
    }
    // 이 부분을 구현해 주세요!
    // 처음 enqueue를 하게 되면 rear 위치에 들어가고 그 이후에는 순차적으로 값이 들어가게 된다.
    queue->rear = (queue->rear + 1) % (queue->capacity); // 나머지 연산을 통해 들어갈 위치를 구해준다.
    queue->array[queue->rear] = item;
    queue->size++;

    printf("%d enqueued to queue\n", item);
}

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        return -9999;
    }
    int item = 0;
    // 이 부분을 구현해 주세요!
    item = queue->array[queue->front];

    // 나머지 연산을 통해 front 의 값을 증가시켜준다.
    queue->front = (queue->front + 1) % (queue->capacity);
    queue->size--;

    return item;
}

// 큐에 대한 내용을 출력하는 함수를 추가했다.
void print_queue(Queue* queue) {
    printf("print items from queue : ");

    for(int i = queue->front; i<=queue->rear; i++) {
        printf("%d ", queue->array[i]);
    }

    printf("\nFront item is %d\n", queue->array[queue->front]);
    printf("Rear item is %d\n", queue->array[queue->rear]);
}


int main() {
    Queue* queue = createQueue(1000);

    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);

    printf("%d dequeued from queue\n\n", dequeue(queue));

    print_queue(queue);

    return 0;
}

 [실행 결과]

 

 

자료구조에 대한 기본적인 이해는 되었는데 왜 항상 코드만 구현하려고 하면 어려운 건지 모르겠다 ㅠㅠ
정말 열심히 찾아가며 그림 그려가며 풀었던 것 같다.

 

6주간 부스트코스 스터디를 통해 공부를 했는데 나름 열심히 했다고 생각하는데
한편으로는 잘하는 사람이 너무나도 많다보니 자극 받아서 더 열심히 하려고 했던 것 같다.

 

이번 스터디가 끝나면 다른 분야도 공부해볼 예정이고 다른 스터디가 있다면 참여할 예정이다.
여러 분야에 대해서 배우는 건 너무 재미있는 일이다!