부스트코스 - 모두를 위한 컴퓨터 과학 (CS50 2019) - 알고리즘

검색 알고리즘

7개의 박스가 있다. 각각의 박스에는 특정 숫자가 들어있고 이 숫자들은 정렬되어있지않고 랜덤한 위치에 랜덤한 숫자가 들어있다. 그리고 무조건 하나는 50 이라는 숫자가 들어있다. 이 50을 찾기위한 방법이 무엇이 있을까?

조건1

1. 7개의 박스에 랜덤한 숫자가 정렬되지않은 상태로 들어가있다.
2. 7개의 박스중 하나는 무조건 50이라는 숫자가 들어있다.
3. 이 7개의 상자에서 50을 찾는 가장 빠른 방법은 어떤것이 있을까?

가장 단순하게 생각할 수 있는 방법은 그냥 처음부터 끝까지 순차적으로 박스를 열어서 확인하는것이다. 가장 첫번째 박스에 50이 들어있다면 한번에 끝날것이고 가장 마지막 박스에 50이 들어있다면 7개의 상자를 모두 열어보아야 할것이다.

여기서 50이 가장 빨리 찾아지는경우는 순전히 우연이다.

조건2

1. 조건1과 모든 조건이 동일하지만 이번엔 7개의 박스안에 숫자는 정렬되어있다.

이번엔 정렬되어있는 숫자가 들어있는 박스 7개에서 50을 찾는 방법이다. 정렬되어있기때문에 50을 찾기 위해 할수있는 방법은

1. 정렬되지않았던 박스를 확인할때처럼 처음부터 끝까지 열어본다.
2. 가운데박스를 확인하고 50보다 작으면 오른쪽 50보다 크다면 왼쪽을 확인한다.
3. 선택한 방향의 남은 박스갯수에서 절반에 해당하는 위치의 상자를 확인하고 2번은 반복한다.

위와같은방법은 첫주 강의에서도 나왔던 전화번호부에서 가장 빨리 원하는 전화번호를 찾는 방법으로 소개되었던 방법과 동일하다.

첫번째 방법은 선형탐색이고 두번째방법은 이진탐색 알고리즘이다.

선형탐색 알고리즘 의사코드

For i from 0 to n–1

    If i'th element is 50

        Return true

Return false

이진탐색 알고리즘 의사코드

If no items

    Return false // 찾는 값이 없을때

If middle item is 50

    Return true // 찾는값이 한번에 50이 나왔을때

Else if 50 < middle item

    Search left half

Else if 50 > middle item

    Search right half

알고리즘 표기법

위와 같은 그림을 공식으로 표기한것이 알고리즘 표기법인데 Big-O 라는 표기법을 사용한다.

n 과 n/2 는 전화번호부에서 특정 전화번호를 찾을때 한장씩 순서대로 넘기며 찾는방법과 똑같이 순차적이지만 두장씩 넘기는 방법의 표기법이다.

만약 데이터가 무수히 많아진다면 n 과 n/2 는 서로 무한히 가까워질것이고 겹쳐보이기도 할것이다. 때문에 Big-O 에서는 두 경우를 하나의 표기법으로 사용한다.

n, n/2 => O(n)
log2n => O(log n)

대표적인 알고리즘들이 있는데 그에대한 표기는 아래와 같다. 목록의 아래쪽에 위치할수록 더 빠른 실행시간을 갖는다고 볼 수 있다.

O(n2)
O(n log n)
O(n)
O(log n)
O(1)

Big-O 는 실행시간에 따른 표기인데 프로그램이나 알고리즘이 동작하는데 걸리는 시간을 말한다.

처음에 나왔던 선형탐색을 Big-O 를 사용하여 표기법으로 표시하면

O(n) // 선형탐색

최악의 경우 선형탐색은 주어진 n 을 모두 탐색해야하기때문에 O(n)의 실행시간을 가진다.

이진탐색을 Big-O 로 표기하면

O(log n) // 이진탐색

log n 이 왜 이진탐색인지 강의에선 따로 설명은 없지만 log 에 대해서 간단하게 정리하고 넘어가려고 한다.

로그는 지수를 다른 방법으로 표기한것으로 2 에 4승은 (2 * 2 * 2 * 2) 이런식으로 2를 4번 곱한것이고 결과는 16이 된다. 그렇다면 2를 몇 제곱해야 16이 되는지 알려면 16을 2로 계속 나눈 몫의 갯수가 정답일것이다. 이걸 log로 표현하면 log2(16) = 4 로 표기가 가능하다.

이진탐색은 1000페이지의 전화번호부가 있을때 절반씩 나눠가면서 전화번호를 찾는 방법이고 이방법은 2번씩 나누어서 정확히 몇번만에 전화번호부에서 전화번호를 찾을 수 있는지 찾는 방법이라고 설명 할 수 있고 log2(1000) = ?? 로 표현이 가능하다.

어차피 이진법은 절반씩 즉 2로 나누기때문에 밑의 값인 2는 제외하고 log(1000) 즉 log n 으로 표현할 수 있다.

Big-O 는 실행시간의 표기법인데 또다른표기법으로 Omega가 존재한다. 이는 Big-O 의 반대되는 표현이다. Big-O 가 실행시간의 상한선이라면 (그래서 선형탐색일때 가장 최악의 경우를 가정했기때문에 O(n) 으로 표기한다.) Omega 는 실행시간의 하한을 나타낸다.

Big-O : 실행시간의 상한선 즉 가장 최악의 경우
Omega : 실행시간의 하한선 즉 가장 운이좋은경우

오메가의 표기법은 아래와 같다.

Ω(n2) // Omega n 의 제곱
Ω(n log n) // Omega n 로그 n
Ω(n)
Ω(log n)
Ω(1) 

선형탐색을 오메가로 표기하면

Ω(1) 

위와같이 표기할 수 있는데 찾으려는값이 가장 첫번째에 있을때 한번에 끝낼수 있으므로 오메가에서는 가장 빠른 표기법을 갖는다.

이진탐색을 오메가로 표현하면

Ω(1) 

선형탐색과 동일하게 한번에 찾을 수 있는 경우가 있기때문에 위와같이 표현 가능하다.

그렇다면 두개의 표기법중에 우선시 해야할 표기법은 무엇일까? 정답은 Big-O 이다. 항상 프로그래밍은 최악의 상황과 평균적인 상황을 가정하고 코드를 작성해야한다.

선형검색

선형검색 코드작성 (int 형 탐색)

int main(void) {
    int numbers[6] = {4, 8, 15, 16, 23, 42}; // 배열을 정적으로 초기화
    //int numbers[6] = {0,};  이런식으로 사용하면 6칸의 배열을 모두 0으로 초기화 할 수 있다.
    for (int i = 0; i < 6; i++) { // 정수형 변수 i 를 선언하고 0으로 초기화; i 가 6보다 작으면; i 는 1씩 증가하여 다시 변수 i에 저장
        if (numbers[i] == 50) { // numbers[0] = 4, numbers[1] = 8 ... numbers 배열을 처음부터 탐색하면서 50과 같은수가 있으면
            printf("Found\n"); // Found 텍스트를 출력
        }
    }
    printf("Not Found\n"); // 배열을 다 탐색하고도 50을 못찾으면 Not Found 출력
}

선형검색 코드작성 (문자 형 탐색)

int main(void) {
    char *names[4] = {"EMMA", "HTML", "CSS", "JAVASCRIPT"};
    // string names[4] = {"EMMA", "HTML", "CSS", "JAVASCRIPT"}; CS50 에서 사용
    for (int i = 0; i < 4; i++) {
        if (names[i] == "EMMA") {
            printf("Found\n");
            return 0; // return 을 해주지않으면 found 가 되더라도 not found 까지 출력해버린다. 
        }
    }
    printf("Not Found\n");
    return 1;
}

위와같은 코드는 첫번째 코드로직과 동일하지만 동작하지않습니다. 이유는 관계연산자인 == 이 C언어에서는 문자열에 사용할 수 없습니다. 같은 맥락으로 switch 구문에도 숫자는 가능하지만 문자열 사용은 불가능합니다.

문자열은 문자열 자체가 배열로 포함됩니다. 정수형 같은경우는 4byte 라는 하나의 메모리영역을 갖고 정수를 저장하지만 문자열은 1byte로 한 메모리영역당 한글자씩만 저장하게됩니다.

따라서 두 문자열을 비교하려면 문자열속에서 문자를 한글자씩 비교를 해야합니다.

다행히도 C 에서는 문자열을 비교하여 두 문자열이 같다면 0을 반환해주는 함수가 존재합니다

#include <string.h> // strcmp 를 사용하기위해 필요한 라이브러리
strcmp(names[i], "EMMA");

전화번호부에서 연락처 찾기

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

int main(void) {
    char *names[4] = {"EMMA", "HONG", "KIM", "JUN"};
    char *numbers[4] = {"010-1234-1111", "010-1234-1112", "010-1234-1113", "010-1234-1114"};

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

정상적으로 동작하는 코드이다. 그러나 문제가 조금 있어보인다. 일단 프로그래밍은 항상 최악의상황을 가정해야하기때문에 만약 저 배열이 4개가 아니라 수백개 수만개라면?

첫번째 데이터가 “EMMA” 의 연락처라는 보장을 할 수 있을까? 데이터의 순서에 변동이 생겨도 데이터의 불변셩이 유지되어야하는데 위의 코드는 그러한 불변성 유지가 불가능한 코드이다.

개선한 전화번호 찾기 개선하려는 코드에는 구조체 라는 문법을 사용합니다.

// 구조체를 정의할때 내부에 어떤 데이터를 담을건지 변수명과 데이터 타입을 정해줘야한다.
typedef struct {
    string name;
    string number;
} person; // 마지막에 붙는 이름으로 구조체를 사용 할 수 있다.

int main(void) {
    person people[4]; // 구조체 person 타입을 가진 people[4]의 배열을 생성한다.
    // people 에는 이제 구조체에 정의된 name 과 number 를 갖고있고 아래처럼 사용가능하다.
    people[0].name = "EMMA";
    people[0].number = "010-1234-1111";

    people[1].name = "HONG";
    people[1].number = "010-1234-1112";

    people[2].name = "KANG";
    people[2].number = "010-1234-1113";

    people[3].name = "KIM";
    people[3].number = "010-1234-1114";

    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;
}

위 코드를 실행하면 결과는 동일하게 나오지면 데이터의 일관성과 불변성을 유지할 수 있게되었다. name 과 number 는 세트로 수정되어져야만하고 동일한 구조체 내에 있기때문에 특정 인덱스에 대해서 항상 같은결과값을 리턴할 수 있게 되었다.

우리가 흔히 아는 회원가입을 구조체로 정의한다면 아래와 같이 정의할 수 있겠다.

typedef struct {
    string id;
    string password;
    string name;
    string number;
    string email;
    string address;
    int age;
} member;

//구조체를 사용하거나 값을 넣고싶을때에는
int main(void) {
    member m1;
    m1.id = "test";
    m1.password = "1234567890";
    m1.name = "홍길동"
    .
    .
    .
}

버블정렬

버블정렬은 두개의 인접한 값을 비교하면서 위치를 교환하는 방법으로 거품이 생겨나는것과 비슷하다고해서 버블정렬이라고 부릅니다.

// 버블정렬로 오름차순으로 정렬
6, 3, 8, 5, 2, 7, 4, 1

1 cycle

// 6과 3을 비교 index < index + 1
3, 6, 8, 5, 2, 7, 4, 1
// 6 과 8을 비교
3, 6, 8, 5, 2, 7, 4, 1
// 8 과 5를 비교
3, 6, 5, 8, 2, 7, 4, 1
// 8 과 2를 비교
3, 6, 5, 2, 8, 7, 4, 1
// 8 과 7을 비교
3, 6, 5, 2, 7, 8, 4, 1
// 8 과 4 비교
3, 6, 5, 2, 7, 4, 8, 1
// 8 과 1 비교
3, 6, 5, 2, 7, 4, 1, 8

/*
result
n = 8
1사이클 수행횟수 7번
수식 : n - 1
*/

2 cycle

// 3과 6을 비교
3, 6, 5, 2, 7, 4, 1, 8
// 6 과 5을 비교
3, 5, 6, 2, 7, 4, 1, 8
// 6 과 2을 비교
3, 5, 2, 6, 7, 4, 1, 8
.
.
.
3, 5, 2, 6, 4, 1, 7, 8

/*
result
n = 8
2사이클 수행횟수 6번
수식 : n - 2
*/

의사코드

// 중첩 루프를 돌아야하고 첫번째 루프는 n-1 만큼 두번째 루프틑 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(n2) 으로 지금껏 봤던것중에 가장 느린 실행시간을 갖는다.
버블정렬은 정렬의 여부에 관계없이 무조건 처음부터 끝까지 비교하면서 배열을 탐색하기때문에 가장 선의 경우는 가장 최악의 경우와 실행시간 상한선 하한선이 동일하다.

선택정렬

선택정렬은 0 번쨰 인덱스를 선택하고 다른수와 비교하다가 더 작은수가 나오면 그 숫자를 기억하고 있다가 n-1만큼 루프를 돌고 더 작은값이 없으면 기억하고 있던 가장 작은값과 0번째 인덱스의 값을 교환하는 방법이다.

// 선택정렬로 오름차순으로 정렬
6, 3, 8, 5, 2, 7, 4, 1

1cycle

// 0번인덱스를 선택하고 n-1 만큼 루프를 돌면서 가장 작은값을 찾아 바꾼다.
6, 3, 8, 5, 2, 7, 4, 1

2cycle

// 1번 인덱스를 선택하고 n-2만큼 루프를 돌면서 가장 작은값을 찾아 바꾼다.
1, 2, 8, 5, 3, 7, 4, 6

.
.
.
결국 모든수가 정렬이 될것이다.

선택정렬도 버블정렬과 같이 이중루프를 사용해야하며 첫번째 루프는 선택된값을 저장하고 두번짜 루프에서 선택된값과 나머지 배열의 값을들 비교하는 루프를 돌다가 더 작은 값이 나오면 기억해 두었다가 선택되었던 인덱스의 값과 교환하게된다.

의사코드

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(n2) 이된다.

정렬 알고리즘의 실행시간

아주 비효율적인 알고리즘 두가지를 보았다. 더 좋게 만들수는 없을까?
버블정렬같은경우 인접해있는 값과의 비교를통해 교환을 진행하는데 만약 제대로 졍렬되어있는 배열이라면 버블정렬에서는 n-1 번만 루프를 돌고 코드실행을 종료 할 수 있다.

따라서 버블정렬코드에 교환할 값이 없다면 벗어나는 코드를 추가해주면 Omega 인 실행시간 하한선은 Ω(n) 이 될것이다.

선택정렬은 정렬이 되어있더라도 무조건 전체 배열을 탐색해야하기때문에 실행시간을 더 줄일 수 있는 방법이 없다.

재귀

재귀는 이해하기에 약간의 난이도가 필요한 알고리즘이긴하지만 중첩반복문을 좀더 가독성있고 우아하게 표현이 가능하다.

그리고 어떠한 특정 부분에서는 중첩루프보다 재귀알고리즘을 무조건 써야하는경우도 생길 수 있다.

1. 번화번호부를 집어든다.
2. 전화번호부 중간을 펼친다.
3. 펼친 부분을 살펴본다.
4. if 원하는 정보가 있다면
5.      전화를 건다.
6. else if 없으면 펼쳐진 양쪽중에 왼쪽에 데이터가 존재한다면 왼쪽절반만 남긴다.
7.      남긴정보에서 다시 절반만 펼쳐본다.
8       3번으로 돌아가 반복한다.
1. else if 없으면 펼쳐진 양쪽중에 오른쪽에 데이터가 존재한다면 오른쪽 절반만 남긴다.
2.      남긴정보에서 다시 절반만 펼쳐본다.
3.     3번으로 돌아가 반복한다.
4.  else 모든경우에 다 해당하지 않는다면
13.     종료

여기 가장 첫 시간에 배웠던 의사코드 작성 내용중에 좀더 효율적으로 만들어 재귀알고리즘을 만들 수 있다.

1. 번화번호부를 집어든다.
2. 전화번호부 중간을 펼친다.
3. 펼친 부분을 살펴본다.
4. if 원하는 정보가 있다면
5.      전화를 건다.
6. else if 없으면 펼쳐진 양쪽중에 왼쪽에 데이터가 존재한다면 왼쪽절반만 남긴다.
7.      남긴정보에서 다시 절반만 펼쳐본다.
8       전화번호부의 왼쪽 절반에서 찾는다.
1. else if 없으면 펼쳐진 양쪽중에 오른쪽에 데이터가 존재한다면 오른쪽 절반만 남긴다.
2.      남긴정보에서 다시 절반만 펼쳐본다.
3.      전화번호부의 오른쪽 절반에서 찾는다.
4.  else 모든경우에 다 해당하지 않는다면
5.      종료

첫번째 의사코드에서는 조건에 따라서 3번으로 다시 돌아가라는 말이 있었는데 이 부분이 찾는다 라는 함수의 반복으로 재귀알고리즘이 될 수 있다.

3번으로 돌아가 반복한다라는 말이 의적으론 재귀알고리즘과 비슷할 순 있는데 여기서 중요한점은 반복해서 같은 함수를 계속 호출한다는것이다.

*
**
***
****

위와같은 결과를 출력하기 위해서 코드를 어떻게 작성해야할까

기존처럼 중첩루프 사용

#include <stdio.h>

int get_int(char *text);
void draw(int h);

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

void draw(int h) {
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= i; j++) {
            printf("*");
        }
        printf("\n");
    }
}

int get_int(char *text) {
    int getInt;
    printf("%s", text);
    scanf("%i", &getInt);
    return getInt;
}

재귀 알고리즘을 사용하여 출력하기 재귀는 조건을 만족할때까지 계속해서 자기 자신을 호출한다.

#include <stdio.h>

int get_int(char *text);
void draw(int h);

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

void draw(int h) {
    if (h == 0) {
        printf("end\n");
        return;
    }
    draw(h - 1); // 자기자신을 계속 호출
    for (int i = 0; i < h; i++) {
        printf("*");
    }
    printf("\n");
}

int get_int(char *text) {
    int getInt;
    printf("%s", text);
    scanf("%i", &getInt);
    return getInt;
}


/*
result

n = 4

end
*
**
***
****
*/

여기서 특이한 부분을 보면 재귀함수를 실행하면서 반복문이 계속 실행되는것이 아닌 재귀호출이 모두 끝난 다음에야 반복문의 출력이 이루어지는것을 볼 수 있다.

즉 재귀는 자기 자신을 종료지점을 맞을때까지 일단 계속 호출하는데 이때 호출하고 바로 출력을 하는것이 아니라 결과값은 메모리에 차곡차곡 쌓이게됩니다.

이때 쌓이는 방법은 스택방식으로 쌓이게되는데 스택은 가장 마지막에 들어간값이 가장 먼저 출력시키는 형태입니다. 물건이 쌓여있을때 가장 밑에물건을 꺼내려면 가장 마지막에 올려놨던 맨 위에 물건부터 치워야하는 원리와 같습니다.

위의 재귀코드는 실행되면 계속 자기 자신을 호출하면서 n = 4 라고 가정했을떄

push = ****
push = ***
push = **
push = * // last push

처럼 스택이 쌓이게되고 종료조건문을 만나면 종료구문을 리턴하고 쌓여있던 결과값중에 가장 마지막에 push 되었던 * 부터 순차적으로 출력이 됩니다.

어디에 사용할까? 예를 들면 이런 데이터가 있습니다.

const company = {
    salse: [
        {
            name: 'KIM',
            salary: 1000
        },
        {
            name: 'JHON',
            salary: 1200
        }
    ],
    developer: {
        frontend: [
            {
                name: 'KANG',
                salary: 2000,
            },
            {
                name: 'BONG',
                salary: 3000,
            }
        ],
        backend: [
            {
                name: 'PYTHON',
                salary: 2500
            }
        ]
    }
}

위의 데이터에서 얻고자하는 결과는 모든 직원의 급여의 합을 구하려고합니다.

각각의 부서는 하위부서를 가질 수 있고 최악의 경우에는 부서안에 부서가 얼마나 있을지 육안으로 확인 불가능할정도의 데이터를 갖고있는 부서일 수 있습니다.

하위부서가 많고 복잡할 수록

for () {
    for () {
        for () {
            for () {
              ............
            }
        }
    }
}

이러한 형태를 가질 수 밖에 없습니다. 이러한 데이터에서 원하는 결과값을 출력하기위해서는 재귀함수를 사용해야지만 가독성도 줄이고 결과의 정확성을 보장 할 수 있습니다.

그리고 데이터에서 어떤 하위부서가 추가되더라도 코드의 수정은 전혀 필요없이 그대로 사용가능합니다.

병합정렬

병합정렬은 위의 재귀알고리즘을 활용한 정렬방법이다.

7 4 5 2 6 3 8 1

위와같이 정렬되지않은 숫자가 주어졌을때 병합정렬은 전화번호부에서 연락처를 찾던 방법과 비슷하다. 배열의 절반을 나누는데 더이상 나눌수 없을때까지 즉 각각 따로 분할될때까지 절반씩 계속 나눈후 왼쪽과 오른쪽 절반씩을 비교하면서 정렬해 나가는 방식이다.

7 | 4 | 5 | 2 | 6 | 3 | 8 | 1

더이상 쪼갤수 없을때까지 절반씩 나눈다면 위와같은 모습이 될거고 이제 병합을하면서 정렬을 진행하면된다.

4 7 | 5 | 2 | 6 | 3 | 8 | 1

4 7 | 2 5 | 6 | 3 | 8 | 1

2 4 5 7 | 6 | 3 | 8 | 1

// 위와 동일한 과정을 거쳐 오른쪽 절반도 병합정렬
2 4 5 7 | 1 3 6 8

1 2 3 4 5 6 7 8

병합정렬의 실행시간의 상한은 O(n log n) 인데 숫자들을 더이상 나눌수 없을때까지 절반씩 나누는데 걸리는 시간이 O(log n) 이고 다시 정렬하며 병합되어지는 시간이 O(n) 이기 때문이다.

정렬의 여부와 상관없이 실행시간의 하한선도 Ω(n log n) 으로 동일하다