부스트코스 CS50 코칭스터디2기 6주차

승아·2021년 2월 26일
cs50부스트코스코칭스터디2기
0

CS50 코칭스터디2기

목록 보기
6/6

📌 자료구조

자료구조

  • 자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미합니다.
  1. 데이터 값의 모임
  2. 데이터 간의 관계
  3. 데이터에 적용할 수 있는 함수나 명령
  • 자료구조를 배우는 이유?
    - 문제를 해결하기 위한 무기이기 때문에
  • realloc
    - 메모리와 포인터에서 배운 개념을 배열에 응용해 봅시다. 처음에 정의한 배열이 가득 찬 상태에서 새로운 값을 추가하고 싶다면?
    💡 포인터를 초기화시키지 않고 값을 저장하면 어떤 오류가 발생할 수 있을까요?
    - 포인터를 초기화하지 않으면 접근이 허용되지 않는 주소 혹은 의도하지 않은 주소를 가리킬 수 있어 예상치 못한 오류가 발생할 수 있다.
    💡 이미 할당된 메모리의 크기를 조절할 때 임시 메모리를 새로 할당해줘야 하는 이유는 무엇인가요?
    - 기존에 사용하고 있던 메모리 뒤에는 다른 데이터들이 담겨 있을 수 있다. 이 상태에서 데이터를 뒤에 더 쓴다면 데이터를 덮어쓰는 일이 발생할 수 있을 수 있다. 때문에 새로 realloc을 써서 데이터를 할당해줘야 된다.

연결리스트

  • 단일 연결리스트(Singly Linked List)
    - 노드와 포인터를 이용해서 선형으로 구조화 시킨 자료구조 입니다.
    - 강의에 소개된 모든 자료구조를 처음부터 짜보겠다는 생각도 좋지만, 각 자료구조가 언제 쓰이면 좋을지를 아는 것이 더 중요 합니다.
    💡 연결 리스트를 배열과 비교했을 때 장단점은 무엇이 있을까요?
    - 장점 : 배열과 달리 유동적으로 크기 조절이 가능해 연속적인 메모리 영역이 필요하지 않다.
    - 단점 : 배열은 인덱싱을 통해 무조건적으로 원하는 데이터 값을 O(1)에 접근할 수 있지만 그와 달리 연결 리스트는 맨 앞, 혹은 맨 뒤 (이중 연결 리스트 일시)에 있는 데이터 값만 O(1)에 접근할 수 있으며, 임의의 값을 접근하려면 말씀하신대로 O(n)번에 데이터값을 접근한다. 또한 배열은 필요없는 데이터값이라도 시작 주소값과 크기를 기억하고 있기 때문에 데이터값 처리만 하면 되지만 연결리스트는 데이터를 저장하고 있는 각 주소가 다르니 필요없어진 데이터 노드에 대해 메모리 해제를 해줘야 한다.
    💡 연결 리스트의 중간에 node를 추가하거나 삭제하는 코드는 어떻게 작성할 수 있을까요?
    - 삽입 : 1 -> 2 -> 3 -> 4 에서 3과 4사이의 5라는 값을 넣고 싶을 때 5와 4를 연결하고 3을 5와 연결해준다.
    - 삭제 : 1 -> 2 -> 3 -> 4 에서 3을 삭제하고 싶을 때 2가 4를 가리키게 한 후 3을 삭제한다.

트리

  • 연결 리스트의 응용 : 1개의 포인터가 아닌 left/right 2개의 포인터로 새로운 데이터 구조를 만들 수 있습니다.
  • 재귀(Recursion) : 재귀를 사용해서 트리를 검색해 볼 수 있습니다.
//이진 검색 트리의 노드 구조체
typedef struct node
{
    // 노드의 값
    int number;

    // 왼쪽 자식 노드
    struct node *left;
 
   // 오른쪽 자식 노드
    struct node *right;
} node;

// 이진 검색 함수 (*tree는 이진 검색 트리를 가리키는 포인터)
bool search(node *tree)
{
    // 트리가 비어있는 경우 ‘false’를 반환하고 함수 종료
    if (tree == NULL)
    {
        return false;
    }
    // 현재 노드의 값이 50보다 크면 왼쪽 노드 검색
    else if (50 < tree->number)
    {
        return search(tree->left);
    }
    // 현재 노드의 값이 50보다 작으면 오른쪽 노드 검색
    else if (50 > tree->number)
    {
        return search(tree->right);
    }
    // 위 모든 조건이 만족하지 않으면 노드의 값이 50이므로 ‘true’ 반환
    else {
        return true;
    }
}

해시 테이블

  • 해시테이블 : 키와 값이 하나의 쌍을 이루는 자료 구조

  • 해시 함수 : 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수

  • 해시 : 데이터를 변환하는 기법

  • 해시 함수를 이요한 충돌(Collision) 처리와 검색 시간의 공간 사이의 Trade off
    💡 값을 검색할 때 이진 검색 트리가 기본 연결 리스트에 비해 가지는 장점과 단점은 무엇이 있을까요?
    - 이진 검색 트리는 O(logn) 만에 검색이 가능하여 검색하는 데에 O(n)이 걸리는 연결리스트에 비해 시간이 적게 걸립니다. 하지만 노드 하나 당 두 개의 노드를 가리켜야 하기 때문에 메모리 사용량이 더 많습니다.

트라이(Trie)

  • 트리와 배열의 조합
    - 문자열을 저장하고 관리하기에 "매우" 적합한 자료 구조 입니다.
    - Trie는 트리 구조를 띄고 있으며 각 노드가 커다란 배열을 가지고 있습니다. 따라서, 직접 구현하시기에는 난이도가 매우 높은 자료 구조 입니다.
  • 어디에 쓸 수 있을까?
    - 검색엔진이나 사전의 자동 완성 기능 (현재 검색엔진은 Language Model을 사용한다.)
    💡 트라이가 해시 테이블에 비해 가지는 장점과 단점은 무엇일까요?
    - 해시 테이블은 O(1)의 시간 복잡도를 보장할 수는 없지만 (해시 함수 문제로 한 쪽에 솔려서 최악의 경우 O(n)까지 걸릴 수 있습니다!), 트라이는 O(m)의 시간 복잡도를 보장합니다! (m=문자열 길이, 보통 상수) 다만 트라이는 각 노드가 배열을 가져 아주 많은 메모리를 필요로 한다는 게 단점입니다.

스택, 큐 그리고 딕셔너리

  • Stack
    - LIFO(Last In First Out) / 후입 선출 구조
    - 뒤로가기, 계산기, 함수 호출 관리 등등 수많은 곳
  • Queue
    - FIFO(First In First Out) / 선입 선출 구조
    - 대기열, 프로세스 관리, 우선 순위 예약 등등 Queue 역시도 수 많은 곳에서 활용 된다.
  • Dictonary
    - 해시 테이블에 기반한 자료구조 입니다. 파이썬에 기본 자료구조 중 하나

팀미션 👩🏻‍💻

  1. 배열로 Stack 만들기
#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;
    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);

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

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

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

    push(stack, 40);
    push(stack, 50);
    push(stack, 60);

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

    printf("%d peek from stack\n", peek(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));
    printf("%d pop from stack\n", pop(stack));

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

    return 0;
}
  1. 연결리스트로 Stack 만들기
#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);
    node->next = *root;
    *root = node;
    printf("%d pushed to stack\n", data);
}

int pop(StackNode** root) {
    if (isEmpty(*root))
        return -9999;
    StackNode* temp = *root;
    *root = (*root)->next;
    int popped = temp->data;
    free(temp);

    /*
    // 메모리 누수 발생
    int popped = (*root)->data;
    *root = (*root)->next;
    */

    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;
}
  1. 배열로 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;
    }
    queue->rear = (queue->rear + 1)%queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;

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

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        return -9999;
    }
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1)%queue->capacity;
    queue->size = queue->size - 1;
    
    return item;
}


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));
    return 0;
}
  1. 뒤에서 k번째 노드는 무엇일까요?
  • 연결리스트의 사이즈를 구한 후 전체 - k 번째로 찾아가는 방법
#include <stdio.h>
#include <stdlib.h>

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

void append(Node* head, int data) {
    // 이 부분을 작성해 주세요!
    if (head->data == 0){
        head->data = data;
        return;
    }
    Node* item = (Node*)malloc(sizeof(Node));
    item->data = data;
    item->next = NULL;

    while(head->next != NULL) {
        head = head->next;
    }
    head->next = item;
}

int getLastNode (Node* head, int k) {
    // 이 부분을 작성해 주세요!
    int i = 1; //head 사이즈
    int cnt = 0;
    int data = 0;
       
    Node* temp = head;
    while(temp->next != NULL){ // head의 사이즈를 구한다
        i++;
        temp = temp->next;
    }

    cnt = i - k;
    if(cnt < 0){ // 사이즈를 벗어나면
        return -9999;
    }

    for(int j = 1; j<=cnt; j++){
        head = head->next;
    }
    data = head->data;

    return data;
}

void printList(Node* head) {
    // 이 부분을 작성해 주세요!
    while(1) {
        if(head->next == NULL){
            printf("%d ", head->data);
            break;
        }
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

int main() {

    Node* head = (Node*)malloc(sizeof(Node));
    for(int i = 1; i<=5; i++)
        append(head, i);

    printList(head);

    for(int i = 5; i>=1; i--)
        printf("%dth last node is %d\n", i, getLastNode(head, i));
}
  • Slow Pointer, Fast Pointer를 활용
int getLastNode (Node* head, int k) {
    Node* fast = head;
    Node* slow = head;
    int start = 1;

    while(fast->next!=NULL) {
        fast = fast->next;
        start++;

        if (start > n) {
            slow = slow->next;
        }
    }
    return slow->data;
}
  • 스택
int getLastNode (Node* head, int k) {
    Stack* stack = createStack(100);

    while(head->next != NULL){
        push(stack, head->data);
        head = head->next;
    }

    for(int i =0; i<k-1; i++){
        pop(stack);
    }
    return peek(stack);
}

회고 ✍🏻

자료구조라 쓰고 연결리스트라 읽는다..⭐️ 이번주차 핵심은 연결리스트!! 2학년 알고리즘 시간 때 열심히 배웠던 기억이 새록새록 난다. 개념은 쉽지만(?) 구현은 어려운 연결리스트. 포인터때문에 과정을 하나하나 그려보면서 구현해보았다.

이번 미션은 Stack과 Queue의 개념을 정확히 익히기 좋은 문제였다. 다만 2번문제에서 이중포인터 등장에 좀 당황했지만 당황하지 않고 구글링하여 완성된 코드를 보면서 이해하였다..ㅋ 4번 문제는 가장 단순하고 직관적이게 풀었다. 연결 리스트의 크기를 구해서 구한 크기 - k를 해준 값만큼 다시 찾아가 데이터를 얻는 방법을 이용했다. 너무 단순하게 풀어서 기대 안했는데 우수미션으로 선정됐다 ✌🏻 4번 문제를 낸 팀이 별로 없어서 선정된듯하다. 역시 가장 단순한 방법이라고 설명해주셨다. 그 외 알려주신 방법 중 포인터 두개를 활용해 푸는 방법, 스택을 이용해 푸는 방법을 풀어보았다. 포인터 두개를 활용해 푸는 방법은 나의 코드가 모범답안에 비해 너무 장황해서 모범답안을 적어놨다. 초짜는 역시 티가난다 ㅋ

마지막 스터디 😭 언제 6주가 흘렀는지 .. 시간 너무 빠르게 가는거 아니에요 ?! 월요일은 강의를 보고 화요일엔 문제풀고 수요일엔 회의를하고 금요일엔 라이브를 보면서 한 주를 마무리했는데 다음주부턴 그럴 수 없어 아쉽기도 하다. 시원 섭섭한 느낌 ~
이번 cs50 스터디를 통해 많은걸 얻고 가는것 같다. cs에 대한 개념뿐만 아니라 팀미션을 통해 서로의 생각을 공유하고 서로의 코드를 리뷰를 하면서 팀원들에게 나의 코드를 설명해주는 방법과 팀원들의 코드를 해석하는 방법 또한 배울 수 있어 좋았다. 그리고 리드부스터로써 팀원들을 따뜻하게 이끄는 방법 또한 배울 수 있었다. 😊 마지막으로 제일 좋았던건 라이브..! 현업 개발자분들이 문제를 풀이해주시고 질문에 답해주시면서 유익한 정보를 많이 얻을 수 있었다.
사실 리드부스터로써 우여곡절(?)도 많았지만 끝까지 함께 해준 팀원들 덕분에 훈훈하게 마무리 할 수 있었다. 팀원 중 한 분은 이번 스터디를 통해 컴공을 복전하실거라고 하셨다.. 👍🏻 cs50스터디 당연히 코딩입문자에게도 추천하지만 나같이 기초가 부족한 전공자에게는 더더욱 추천한다!

3기를 고민하시는 분들 당장 신청하세요 !! 😁

profile
승아
이전 포스트

부스트코스 CS50 코칭스터디2기 5주차

0개의 댓글