[모두의 컴퓨터과학] 알고리즘

검색 알고리즘

• 선형 검색: 차례대로 하나씩 비교하며 찾는 것
• 이진 탐색: 정렬되어 있는 배열에서 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은 인덱스 or 큰 인덱스로 이동을 반복한다.

알고리즘 표기법

big-O

• 알고리즘이 얼마나 효율적인지 표기하는 방법
• 상수는 생략하여 표기한다.
• 선형 검색: O(n), 이진 탐색: O(log n)

big-omega

• 최선의 경우를 표기함
• 선형 탐색, 이진 탐색의 경우 최선의 경우는 1임

선형검색

• C에서 배열에 자료를 넣고 싶을땐

int number[6] = {4, 8, 15, 16, 23, 42};

• 위와 같은 식으로 중괄호를 이용해 할 수 있다.

선형검색

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

int main(void)
{
    int number[6] = {4, 8, 15, 16, 23, 42};
    for (int i = 0; i < 6; i++)
    {
        if (number[i] == 50)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

• 그러나 string에는 ==를 쓸 수 없다
• 문자열의 글자 하나하나씩 ==로 비교해야 한다.
• strcmp(문자열, 문자열): 두 문자여링 같다면 0을 리턴한다.

phonebook

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

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

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

• 새로운 자료형을 써서 개선

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

typedef struct // 여러 자료형을 담아 새로운 자료형으로 만든다
{
    string name;
    string number;
}
person;

int main(void)
{
    person people[4];
    people[0].name = "EMMA";
    people[1].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"

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

버블 정렬

• 이진 탐색을 하기 위해선 먼저 배열을 정렬해야한다. 정렬은 얼마나 시간이 걸릴까?
• 버블 정렬: (n -1) * (n - 1) = O(n^2)

Repeat n - 1 times
    For i from 0 to n - 2
        if i'th and i+1'th elements out of order
            swap them

• 버블 정렬을 사용하면 선형검색에 비해 이진탐색이 더 효율적이지 않다
• 버블정렬은 최선의 경우도 O(n^2)이다.

선택 정렬

• 매번 가장 작은 값을 찾고 앞에다 둔다.

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 + (n -1) + ... + 1) = O(n(n+1) / 2) = O(n^2)
• 컴퓨터는 최솟값을 찾기 위해선 무조건 배열의 모든 인덱스를 방문해야하기 때문에 선택정렬은 최선의 경우에도 O(n^2)다

정렬 알고리즘의 실행시간

• 교환이 일어나지 않을 때 알고리즘을 종료한다면 버블 정렬은 최선의 경우가 더 빨라질 수 있다.
• 이 경우 최선의 경우는 O(n)이다.

재귀

• 프로그램이나 알고리즘이 스스로를 계속 호출하는 것

피라미드 만들기

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

void draw(int h);

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

void draw(int h)
{
    if (h == 0)
    {
        return;
    }
    draw(h-1); // h-1 높이의 피라미드를 그리고
    for (int i = 0; i < h; i++) //한 줄을 추가한다.
    {
        printf("#")
    }
    printf("\n")
}

병합 정렬(Merge sort)

• 재귀를 이용한 정렬
• 여기서 merge는 두 배열중에서 가장 작은 값을 꺼내 다른 배열의 가장 작은 값 앞에 두는 과정이다.

if only one item
    return
else
    sort left half of items
    sort right half of items
    merge sorted halves

• 계속 절반으로 나누는 식의 알고리즘으로 log함수로 표현할 수 있다.
• n개를 merge하는 과정을 log n 번 반복하기 때문에 O(nlogn)이다.
• 최선의 경우도 O(nlogn)이다.

theta

• 어떤 알고리즘의 상한선과 하한선이 같을 때 theta표기법으로 표현한다.
• 병합 정렬은 theta(n log n)이다.

출처: 부스트코스 모두의 컴퓨터과학