[CS50] 알고리즘과 자료구조

42서울 7기 라피신을 대비하여 정리한 CS50 2019 과정을 간략히 복기하여 재업로드한 내용입니다.

1. 알고리즘

1) 🔎 검색 알고리즘

• 배열 : 한 자료형의 여러 값들이 메모리상에 모여 있는 구조
  • 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근한다.
• 검색 알고리즘은 배열이 정렬되어 있는지 여부에 따라 아래와 같은 방법으로 나뉜다:
  • 선형 검색
  • 이진 검색

선형 검색 (N)

For i from 0 to n–1

    If i'th element is 50

        Return true

Return false

• 배열이 정렬되어 있지 않은 경우
  • 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사

이진 검색 (logN)

If no items

    Return false

If middle item is 50

    Return true

Else if 50 < middle item

    Search left half

Else if 50 > middle item

    Search right half

• 배열이 정렬되어 있는 경우
  • 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복

2) 📝 알고리즘 표기법

• 알고리즘은 직선으로 그려지는 선형의 형태이거나, 조금 더 굴곡이거나, 로그 형태일 수 있다. 이러한 형태는 문제의 크기가 증가함에 따라 문제 해결에 필요한 시간이 얼마나 증가하는지를 나타낸다.
  

Big-O 표기법 (상한)

• 위 그림에서, 문제의 크기가 충분히 커진다면 O(n) 과 O(n/2) 의 그래프는 매우 비슷해져 구분이 무의미해진다.
• 마찬가지로 O(log2n) 의 경우 log2, log3...log 등등 밑으로 어떤 숫자가 오든 구분이 무의미해진다.
• 따라서 대표적인 실행 시간은 아래와 같이 몇 가지 경우로 추려질 수 있다:
  • O(n^2)
  • O(n log n)
  • O(n)
  • O(log n)
  • O(1)

Big-Ω 표기법 (하한)

• 위의 Big O 가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω 는 알고리즘 실행 시간의 하한을 나타낸 것.
  • Ω(n^2)
  • Ω(n log n)
  • Ω(n)
  • Ω(log n)
  • Ω(1)
• 예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n) 이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1) 이다.

3) 🔚 선형 검색

• 선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다.
  • 즉, 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 한다.

효율성과 비효율성

• 선형 검색 알고리즘은 정확하지만 낮은 효율성을 보인다.
  • 리스트의 길이가 n 이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n 번만큼 실행된다.
  • 이 최악의 상황이란 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우를 말한다.
  • 반대로 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우인데, 평균적으로 선형 검색이 최악의 상황에서 종료되는 것에 가깝다고 가정할 수 있다.
• 선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다.
• 다만 검색 이전에 자료를 정렬한다면 다른 검색 알고리즘을 사용해 효율성을 높일 수 있을 것이다.

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    string numbers[] = {"617–555–0100", "617–555–0101", "617–555–0102", "617–555–0103"};

    for (int i = 0; i < 4; i++)
    {
        if (strcmp(names[i], "EMMA") == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

• 위 코드는 한 인물의 이름과 전화번호를 names 배열과 numbers 배열로 각각 따로 정의하였다.
  • 이 경우에는 names 배열과 numbers 배열이 서로 같은 인덱스를 가져야 한다는 한계가 있다.
• 인물 또는 전화번호를 정렬하면, 인덱스가 흐트러지며 이름과 전화번호를 연결지을 수 없을 것이다.

typedef struct
{
    string name;
    string number;
}
person;

int main(void)
{
    person people[4];

    people[0].name = "EMMA";
    people[0].number = "617–555–0100";
    people[1].name = "RODRIGO";
    people[1].number = "617–555–0101";
    people[2].name = "BRIAN";
    people[2].number = "617–555–0102";
    people[3].name = "DAVID";
    people[3].number = "617–555–0103";

    // EMMA 검색
    for (int i = 0; i < 4; i++)
    {
       ...
    }
    return 1;
}

• 따라서 위와 같이 구조체를 사용하여 관련 있는 값들을 하나의 자료형으로 묶어 관리한다면, 자료의 정렬이 훨씬 간편해지고, 따라서 검색의 용이함도 높아질 것이다.

4) 🛁 버블 정렬

• 앞서 말했듯, 자료의 양이 방대해질수록 검색 이전에 잘 정렬해 두는 것이 확장성과 효율성을 높이는 데 중요한 조건이 된다.
• 어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능하다.
  • 버블 정렬 이란 그러한 정렬 알고리즘 중 하나이다.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

• 버블 정렬 : 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방식
  • 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중
    • 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식과 닮아 있다.
  • 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 있다.
• 버블 정렬을 구현하려면 중첩 루프를 돌아야 하고, n 개의 값이 주어졌을 때 각 루프는 각각 n-1 번, n-2 번 반복되므로 (n-1)*(n-2) = n^2-3n+2 번의 비교 및 교환이 필요하다.
  • 위 식에서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2) 이라고 말할 수 있다.
  • 정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 Ω(n^2) 이다.

5) 🔘 선택 정렬

For i from 0 to n–1

    Find smallest item between i'th item and last item

    Swap smallest item with i'th item

• 선택정렬 : 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬
  • 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가
• 선택 정렬에서도 마찬가지로 두 번의 루프를 도는데, 바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾아야 한다.
  • 따라서 소요 시간의 상한은 O(n^2) 이며, 하한도 마찬가지로 Ω(n^2) 이다.

6) 🛠 정렬 알고리즘 최적화

• 버블 정렬을 예로 들어, 불필요한 교환은 발생하지 않도록 코드를 수정해 본다.

Repeat until no swaps

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

• 기존에는 바깥쪽 루프의 조건이 Repeat n–1 times 로, 정렬이 전부 끝나도 무조건 n-1 번 만큼 반복되어야 했다.
  • 어떤 한 루프에서, 안쪽 루프가 전부 돌 때까지 단 한 번의 교환도 일어나지 않았다면, 모든 자리가 정렬되어 있는 경우를 뜻할 것이다.
  • 따라서 바깥쪽 루프를 교환이 일어나지 않을때 까지만 수행하도록 조건을 수정하면, 불필요한 교환을 없앨 수 있다.
• 최종적으로 버블 정렬의 하한은 Ω(n) 이 되어, 경우에 따라서는 선택 정렬보다 빠른 방법이 될 수 있다.

7) 🔝 재귀

• 함수를 함수 내에서 재사용하는 것을 "재귀적으로 호출한다" 라고 한다.

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
    int height = get_int("Height: ");

    draw(height);
}

void draw(int h)
{
    // 높이가 0이라면 (그릴 필요가 없다면)
    if (h == 0)
    {
        return;
    }

    // 높이가 h-1인 피라미드 그리기
    draw(h - 1);

    // 피라미드에서 폭이 h인 한 층 그리기
    for (int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}

• 이 코드는 아래와 같은 피라미드 모양을 출력한다.

#
##
###
####

• 여기서 내부적으로 호출된 draw 함수를 따라가다 보면 h = 0 인 상황이 온다. 그 때는 아무것도 출력을 하지 않도록 하는 조건문을 추가해줘야 한다.
  • 재귀 (Recursion) 는 무한루프에 빠지기 쉽기 때문에 항상 Base case 와 Recursive case 를 구분해야 한다.
    • Base case : 자기 자신을 호출하지 않고 바로 답을 알 수 있는 경우(= 따로 풀어야할 부분문제가 없음)
      • 재귀적으로 문제를 해결한다 = 같은 형태의 더 작은 문제(부분 문제 = Subproblem)를 푼다
    • Recursive case : Recursion을 반복하다 보면 Base case에 수렴하게 하는 조건

• 위 트리처럼, 재귀함수에서 재귀 호출 은 depth 를 한 단계 늘리는 것이고, for 반복문은 해당 depth 에서의 노드의 개수, 즉 폭 을 넓힌다고 이해해 봤다.

8) 🗂 병합 정렬

• 병합 정렬 : 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식
  • 재귀적으로 구현된다.
  • 최악의 경우에도 O(n log n) 의 시간 복잡도가 보장된다.

Merge Sort(A[], p, r) {    // 배열 A[p...r]을 정렬한다.
  if(p<r) then {
    q <- (p+q)/2;
    mergesort(A, p, q);
    mergesort(A, q+1, r);
    merge(A, p, q, r);
  }
}

merge(A[], p, q, r) {
  정렬되어 있는 두 배열 A[p...q]와 A[q+1...r]을 합하여
  정렬된 하나의 배열 A[p...r]을 만든다.
}

2. 자료구조

1) 배열의 크기 조정하기: realloc

• 일정한 크기의 배열이 주어졌을 때, 그 크기를 키우려면 어떻게 해야 할까
  • 현재 배열이 저장되어 있는 메모리 위치를 제외하고, 그 주변으로는 이미 다른 데이터가 저장되어 있을 확률이 높다.
  • 안전하게, 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다.
    • 이런 작업은 O(n), 즉 배열의 크기 n 만큼의 실행 시간이 소요될 것이다.

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

int main(void)
{
    //int 자료형 3개로 이루어진 list 라는 포인터를 선언하고 메모리 할당
    int *list = malloc(3 * sizeof(int));

    // 포인터가 잘 선언되었는지 확인
    if (list == NULL)
        return 1;

    // list 배열의 각 인덱스에 값 저장
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    //int 자료형 4개 크기의 tmp 라는 포인터를 선언하고 메모리 할당
    int *tmp = malloc(4 * sizeof(int));

    if (tmp == NULL)
        return 1;

    // list의 값을 tmp로 복사
    for (int i = 0; i < 3; i++)
        tmp[i] = list[i];

    // tmp배열의 네 번째 값도 저장
    tmp[3] = 4;

    // list의 메모리를 초기화
    free(list);

    // list가 tmp와 같은 곳을 가리키도록 지정
    list = tmp;

    // 새로운 배열 list의 값 확인
    for (int i = 0; i < 4; i++)
        printf("%i\n", list[i]);

    // list의 메모리 초기화
    free(list);
}

• 기존의 배열을 옮기기 위해, malloc() 함수를 사용하여 메모리 상의 더 큰 공간을 새로 할당했다.
• 새롭게 할당받은 공간을 가리키는 포인터 tmp 를 인덱싱해, 각 요소에 기존 배열 list 의 값들을 복사했다.
• list 가 사용하고 있던 공간은 더 이상 필요가 없으므로, 반드시 free() 함수를 이용해 할당을 해제한다.

• 이처럼 새로운 배열을 만들어서 기존 배열을 옮기려는 경우, malloc() 과 값 복사 과정을 한 번에 수행하는 realloc() 함수를 사용할 수 있다.

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

int main(void)
{
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
        return 1;
        
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // tmp 포인터에 메모리를 할당하고 list의 값 복사
    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
        return 1;

    // list가 tmp와 같은 곳을 가리키도록 지정
    list = tmp;

    // 새로운 list의 네 번째 값 저장
    list[3] = 4;

    // list의 값 확인
    for (int i = 0; i < 4; i++)
        printf("%i\n", list[i]);

    //list 의 메모리 초기화
    free(list);
}

2) 데이터 구조: 연결 리스트

• 데이터 구조 : 사용자가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체
  • 일종의 메모리 레이아웃, 또는 지도

배열의 특성과 장단점

• 배열은 고정된 메모리 덩어리라고 할 수 있다.
• 따라서 배열의 크기를 조절해 더 많은 값을 넣고 싶다면 최소한 기존 배열의 크기 이상의 새로운 메모리 공간을 할당하여, 기존 값들을 모두 새로운 공간으로 복사해야 한다.
  • 따라서 최소한 O(n) 의 실행 시간이 소요된다.
• 그러나 배열의 강력한 장점은 (대괄호를 사용한) 인덱싱이다.
  • 이는 랜덤 접근 이라는 방식으로 일정한 시간에 접근할 수 있게 해 준다.
  • 무작위로 접근한다는 뜻이 아니라, 앞 또는 뒤에서부터 순회할 필요 없이 괄호 안에 0, 1, 2 등을 써서 바로 그 자리로 접근할 수 있다는 뜻이다.
  • 따라서 배열은 탐색에 있어 아주 빠르다.

연결 리스트 (개념)

• 배열을 위해서는 값들이 마치 하나의 덩어리처럼 메모리 상의 연속된 위치에 저장되어야 한다.
• 따라서 배열의 크기가 커지다가 다른 값이 저장되어 있는 메모리 위치 직전까지 사용하게 되면, 더 이상 새로운 값을 배열에 추가할 수 없다.
• 각 값을 메모리상의 여러 군데에 나누어 저장하는 대신 다음 값의 메모리 주소를 함께 기억하도록 한 연결 리스트 구조는 이러한 문제를 해결할 수 있다.

typedef struct node
{
    int number;
    struct node *next;
}
node;

• 위 코드에서, node 라는 이름의 구조체는 number 와 *next 두 개의 필드가 함께 정의되어 있다.
  • number 는 각 node 가 가지는 값, *next 는 다음 node 를 가리키는 포인터다.
• 여기서 typedef struct 대신에 typedef struct node 라고 node 를 함께 명시해 주는 것은, 구조체 안에서 node 를 사용하기 위함이다.

연결 리스트 (구현)

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

// 연결 리스트의 기본 단위가 되는 node 구조체를 정의
typedef struct node
{
    //node 안에서 정수형 값이 저장되는 변수
    int number; 

    //다음 node의 주소를 가리키는 포인터
    struct node *next;
}
node;

int main(void)
{
    // list라는 이름의 node 포인터를 정의한다. 연결 리스트의 가장 첫 번째 node를 가리킬 것이다.
    // 현재에는 아무것도 가리키고 있지 않기 때문에 NULL 로 초기화한다.
    node *list = NULL;

    // 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킨다.
    node *n = malloc(sizeof(node));
    if (n == NULL)
        return 1;
        
    n->number = 1;

    // n 다음에 정의된 node가 없으므로 NULL로 초기화한다.
    n->next = NULL;

    // 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꾼다.
    list = n;

    // 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당한다.
    n = malloc(sizeof(node));
    if (n == NULL)
        return 1;

    n->number = 2;
    n->next = NULL;

    // list가 현재 가리키는 것은 첫 번째 node다. 
    // 이 (첫 번째) node의 다음 node를 n 포인터로 지정한다.
    list->next = n;

    n = malloc(sizeof(node));
    if (n == NULL)
        return 1;

    n->number = 3;
    n->next = NULL;

    // 현재 list는 여전히 첫 번째 node를 가리킨다.
    list->next->next = n;
    
    // 메모리를 해제해줄 때에는 list에 연결된 node들을 처음부터 방문하면서 free 한다.
    while (list != NULL)
    {
        // 임시 포인터 변수 tmp 를 선언하여 사용한다.
        node *tmp = list->next;
        
        // list가 현재 가리키는 것은 첫 번째 node다. 
        // tmp에 list->next 를 미리 저장해놓지 않았다면 list가 free되고 나서 나머지 요소들에 접근할 방법이 없어진다.
        free(list);
        list = tmp;
    }
}

• 배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있다.

  • 하지만 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능하다.

• 예를 들어, 연결 리스트에 값을 추가하거나 검색하는 경우 해당 위치까지 연결 리스트의 각 node 들을 따라 이동해야 한다.

  • 따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n) 이 된다.
  • 배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(log n) 의 실행 시간이 소요 되는 것에 비해서 다소 불리하다.

3) 🌳 연결 리스트: 트리

• 트리 : 연결리스트를 기반으로 한 새로운 데이터 구조
  • 연결리스트 에서의 각 노드 (연결 리스트 내의 한 요소를 지칭) 들의 연결이 1차원적으로 구성되어 있다면, 트리 에서의 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있다.
  • 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 된다.

• 가장 높은 층에서 트리가 시작되는 노드를 루트 라고 한다.
  • 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 자식 노드 라고 한다.
• 위 그림에 묘사된 트리는 이진 검색 트리 의 예시다.
  • 하나의 노드는 두 개의 자식 노드를 가진다.
  • 왼쪽 자식 노드는 자신의 값 보다 작고, 오른쪽 자식 노드는 자신의 값보다 크다.
    • 따라서 이런 트리 구조는 이진 검색을 수행하는데 유리하다.

//이진 검색 트리의 노드 구조체
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;
    }
}

• 이진 검색 트리를 활용하였을 때 검색 실행 시간과 노드 삽입 시간은 모두 O(log n) 이다.
  • 값을 검색할 때, 기본 연결 리스트는 검색 실행시간이 O(n) 으로 모든 변수를 다 찾아야 하는 반면 이진 검색 트리를 활용하면 검색 실행 시간이 O(log n) 이 되어 실행 시간 측면에서 효율성을 향상시킬 수 있다.
  • 그러나 더 복잡한 구조를 갖게 되어 많은 양의 메모리를 사용하게 된다. 즉 공간 복잡도를 증가시킨다.

4) 🧺 해시 테이블

• 해시 테이블 : 연결 리스트의 배열
  • 여러 값들을 몇 개의 바구니에 나눠 담는 상황 을 예로 들어 보자.
    • 각 값들은 해시 함수 라는 맞춤형 함수를 통해서 어떤 바구니에 담기는지가 결정된다.
    • 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어진다.
    • 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 ‘연결 리스트의 배열’, 즉 해시 테이블 이 된다.

• 위 그림은 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우다.
  • 해시 테이블에는 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리키게 된다.
• 해시 함수가 이상적이라면, 각 바구니에는 단 하나의 값들만 담길 것이다.
  • 이 때 검색 시간은 O(1) 이다.
• 하지만 최악의 상황에는 단 하나의 바구니에 모든 값들이 담겨서 O(n) 이 될 수도 있다.
• 일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에, 거의 O(1) 에 가깝다고 볼 수 있다.

5) 🔎 트라이(Trie)

• 트라이 : 트리 형태의 자료 구조
  • 각 노드가 ‘배열’로 이루어져 있다.
    • 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면, 이 노드는 a부터 z까지의 값을 가지는 배열이 된다.
    • 이 때 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z 배열)를 가리킨다.
• 트라이에서 값을 검색하는데 걸리는 시간은 문자열의 길이에 의해 한정된다.
• 이러한 트라이 구조는 찾고자 하는 문자열을 공간을 많이 사용하는 대신, 그 문자열의 길이의 속도만큼 초고속 탐색이 가능하다.

6) 📚 스택, 큐, 딕셔너리

큐

• 큐 : 값이 아래로 쌓이는 구조
  • 값을 넣고 뺄 때 선입 선출 또는 FIFO 라는 방식을 따른다. 즉 가장 먼저 들어온 값이 가장 먼저 나간다.
• 배열 이나 연결 리스트 를 통해 구현 가능

스택

• 스택 : 값이 위로 쌓이는 구조
  • 값을 넣고 뺄 때 후입 선출 또는 LIFO 라는 방식을 따른다. 즉 가장 나중에 들어온 값이 가장 먼저 나간다.
• 배열 이나 연결 리스트 를 통해 구현 가능

딕셔너리

• 딕셔너리 : 키 와 값 이라는 요소로 이루어짐
  • 키 에 해당하는 값 을 저장하고 읽어온다. 일반적인 의미에서 해시 테이블 과 동일한 개념이라고도 볼 수 있다.
    • 키 를 어떻게 정의할 것인지가 탐색의 효율성에 큰 영향을 미친다.

---

이렇게 부스트캠프의 CS50 강좌를 모두 수강 및 정리해 보았다.

앞 부분은 상당히 기초적인 내용이고, 뒷 부분은 스택이나 큐처럼 가장 흔히 접하게 되는 자료구조에 대해 다소 간단히 설명하고 끝낸 것 같아 추가 학습의 필요성을 느꼈다.

그래도 컴퓨터 과학의 가장 기초적인 흐름에 대해 짧은 시간 안에 간단히 정리하기 좋았던 강좌다.

(벨로그로 옮겨 정리하는 김에 수료증도 발급받아 보았다. 이왕이면 영어로... )