[CS50] Week3: Algorithms

(1) Linear Search

-순서대로 선형 검색

-7개의 락커에서 50이 들어있는 락커를 처음부터 순서대로 열어가면서 찾기

 

(2) Binary Search

-미리 정렬이 되어있을 때 사용 가능

-중간 락커를 열어서 확인해보고 찾으려는 숫자가 확인한 숫자보다 작으면 왼쪽에서 search, 크면 오른 쪽에서 search

 

(3) Big O, Big Omega, Big Theta Notation

-알고리즘의 효율성은 대개 실행 시간의 차수로 표현되며, 그래프의 모양이 중요

-O는 최악의 경우, Ω(omega)는 최적의 경우, Θ(theta)는 상한과 하한이 동일한 경우

Linear Search: O(n), Ω(1)

Binary Search: O(log n), Ω(1)

 

(4) Data Structure

-struct를 이용하여 사용자 정의 데이터 타입을 만들 수 있음

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

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

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

    people[0].name = "Carter";
    people[0].number = "+1-617-495-1000";

    people[1].name = "David";
    people[1].number = "+1-617-495-1000";

    people[2].name = "John";
    people[2].number = "+1-949-468-2750";

    // Search for name
    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
        if (strcmp(people[i].name, name) == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

 

(5) Selection Sort

<pseudocode>

For i from 0 to n–1
    Find smallest number between numbers[i] and numbers[n-1]
    Swap smallest number with numbers[i]

 

필요한 단계 = (n - 1) + (n - 2) + (n - 3) + ... + 1 = n(n-1)/2

시간복잡도: O(n²), Ω(n²), Θ(n²)

 

(4) Bubble Sort

<pseudocode>

Repeat n-1 times
    For i from 0 to n–2
        If numbers[i] and numbers[i+1] out of order
            Swap them
    If no swaps
        Quit

 

swapping 해가면서 올라가는 모습이 거품 같아서 버블 정렬

필요한 단계 = (n - 1) + (n - 2) + (n - 3) + ... + 1 = n(n-1)/2

시간복잡도: O(n²), Ω(n)

 

(5) Recursion

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

void draw(int n);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int n)
{
    // If nothing to draw
    if (n <= 0)
    {
        return;
    }

    // Draw pyramid of height n - 1
    draw(n - 1);

    // Draw one more row of width n
    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}

 

 

(6) Merge Sort 

-재귀를 활용하여 훨씬 효율적인 알고리즘인 merge sort를 이용할 수 있음

<pseudocode>

If only one number
    Quit
Else
    Sort left half of number
    Sort right half of number
    Merge sorted halves

 

시간복잡도: O(n logn), Ω(n logn), Θ(n logn)