[CS50X] 2024 Week3 Algorithms

 

알고리즘을 배울 때면 항상 중학생 때 들었던 가우스 일화가 생각난다.

1 + 2 + 3 + ... + 99 + 100 = ??? 이 계산을 해보라는 것이였는데

자연스럽게 1 + 2, 3 + 3 을 하면서 계산했던 기억이 난다.

선생님은 10초 만에 시간이 끝났다며 계산을 한 사람이 있는지 물었는데 아무도 없었다.

아마 계산기를 써도 그렇게 빠르게 하긴 어려울 것이다.

근데 가우스는 10살 무렵에 이 계산을 10초 안에 했다고 한다.

그의 비법은 거꾸로 뒤집어 2번 더하는 것이였다.

1 + 2 + 3 + ... + 99 + 100

100 + 99 + 97 + ... + 2 + 1

= 101 + 101 + ... + 101  --> 101 * 100

10100 이라는 수가 나오는데 2번 더했으니 2로 나누면

5050이라는 수가 나오는 것이다. 

알고리즘과 사고의 힘인 것 같다. 가우스의 힘인가?

 

 

 

Linear search

선형 탐색은 한 방향으로 쭉 탐색하는 것이다.

10개의 사물함이 있는데 그 중 하나에 3만원이 들어있다고 한다면

모든 사물함을 1부터 10이나 10부터 1과 같은 방식으로 열어보는 것이다.

간단한 의사코드로 표현하면 다음과 같다.

For i from 0 to n-1
    If 3 is behind doors[i]
        Return true
Return false

 

Linear Search 구현

#include <stdio.h>

int LinearSearch(int numbers[], int len, int val);

int main(void)
{
    int numbers[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    printf("%i\n", LinearSearch(numbers, 10, 3));

}

int LinearSearch(int numbers[], int len, int val)
{
    for (int i = 0; i < len; i++)
    {
        if (numbers[i] == val)
        {
            return numbers[i];
        }
    }
    return -1;
}

 

 

Binary search

 

이진 탐색은 정렬이 되어있을 때만 사용 가능한 탐색 알고리즘이다. 이래서 정렬에 환장하는구나

똑같이 100개의 사물함이 있는데 1~100만원이 순서대로 들어있다고 했을때 30만원을 찾는다면

우선 중간으로 가서 값을 확인한다. 50만원이 나오면 이제 1~49번 사물함을 탐색한다.

중간 지점으로 가면 25만원을 확인할 수 있다. 이제 25~49번 사물함을 탐색한다.

중간 지점으로 가면 37만원을 확인 할 수 있다. 이제 25~37번 사물함을 탐색한다.

중간 지점으로 가면 31만원을 확인 할 수 있다. 이제 25~31번 사물함을 탐색한다.

중간 지점으로 가면 28만원을 확인 할 수 있다. 이제 29~31번 사물함을 탐색한다.

중간 지점으로 가면 30만원을 확인할 수 있다. 찾으려는 값을 찾았다.

이런 방식으로 이진 탐색은 진행된다. 

의사코드로 나타낸다면 다음과 같다.

if 사물함이 존재하지 않는다면 반복을 멈추고 실패를 알림
if 사물함[중간] = 찾으려는 값 이면 멈추고 성공을 알림
else if 사물함[중간] > 찾으려는 값
    사물함[0] ~ 사물함[중간-1] 에서 다시 탐색
else if 사물함[중간] < 찾으려는 값
    사물함[중간+1] ~ 사물함[끝] 에서 다시 탐색

 

Binary Search 구현

#include <stdio.h>

int BinarySearch(int numbers[], int start, int last, int val);

int main(void)
{
    int numbers[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    printf("%i\n", BinarySearch(numbers, 0, 10, 3));
}

int BinarySearch(int numbers[], int start, int last, int val)
{
    if (start > last)
    {
        return -1;
    }
    int middle = (start + last) / 2;
    if (numbers[middle] > val)
    {
        return BinarySearch(numbers , start, middle - 1, val);
    }
    else if (numbers[middle] < val)
    {
        return BinarySearch(numbers, middle + 1, last, val);
    }
    else
    {
        return numbers[middle];
    }
}

 

 

 

Running time

 

선형탐색과 이진탐색의 시간과 문제 크기에 대한 그래프를 그려보면 이런 모양이 되는데

여기서 O Big-O 표기법으로  최대 시간을 뜻한다. 즉 1~100 까지 탐색하는데 찾으려는 수가 맨 뒤에 있는

최악의 경우에서의 시간을 나타내는 것이다.

- O(1)

실행하는 시간이 상수 시간 걸리고 문제가 커져도 항상 같은 시간이 걸린다.

ex) 첫 번째로 온 학생을 찾는다.

 

- O(log n)

로그 시간이 걸리는 경우로 문제가 n만큼 커지면 시간은 log n 만큼 더 걸린다.

ex) 이진탐색

 

- O(n)

선형 시간이 걸리는 경우로 문제가 n만큼 커지만 시간은 n 만큼 더 걸린다.

ex) 선형 탐색

 

- O(nlog n)

선형 로그 시간이 걸리는 경우로 문제가 n만큼 커지만 시간은 nlog n 만큼 더 걸린다.

ex) 병합 정렬 

 

- O(n^2)

2차 시간이 걸리는 경우로 문제가 n만큼 커지만 시간은 n^2 만큼 더 걸린다.

ex) 선택 정렬

 

 

* Ω, θ 에 대해서

이러한 기호에는 Big - O 말고도 오메가와 세타가 있다.

Ω 는 최상의 경우에서의 복잡도이다. 

만약 0~9중 5를 찾는 선형 탐색을 실행하는데 우연히 5가 맨 앞에 있었다면

바로 찾고 프로그램은 종료될 것이다. 

선형 탐색은 O(n) 이지만 Ω(1) 인 것이다. 이진 탐색도 마찬가지이다.

사실 알고리즘을 짤 때 최선의 시간을 가정하지 않기 때문에 O의 비교가 우선이다.

하지만 만약 알고리즘을 비교하는데 같은 O()를 갖는다면 Ω 의 비교를 고려해 볼 수 있다.

또한 어떻게 정렬되어 있는지에 따른 영향도 받을 수 있다.

θ 는 O와 Ω 가 같은 경우이다. 

 

 

 

 

Selection sort

알고리즘에 있어서 정렬은 상당히 중요한데 

선택 정렬에 대해 먼저 생각해보면, 오름차순 정렬 한다 했을때 

가장 작은 수를 계속 앞으로 가져온다.

0~9 가 무작위로 흩어져있다고 가정해보자.

7 3 1 9 5 8 2 6 0 4 에서 우선 가장 작은 수를 찾는다.

0 가 가장 작기 때문에 0와 맨 앞에 숫자를 바꾼다. 

0 3 1 9 5 8 2 6 7 4 

맨앞에서 2번째 숫자 부터 끝까지 중 가장 작은 수를 찾는다.

1 이 가장 작기 때문에 1과 맨 앞에서 2번째 숫자를 바꾼다.

0 1 3 9 5 8 2 6 7 4 

이것을 반복해서 정렬하려면

n-1 , n-2, n-3 ...1 이렇게 n 번 반복해야 한다. 상수를 무시하고

표현하면 O(n^2) 만큼의 시간이 걸린다.

의사코드로 나타내면

for i가 0 ~ n-1 까지 n 번 만큼 반복한다.
    숫자[i] 와 숫자[n-1] 에서 가장 작은 수를 찾는다
    가장 작은 수와 숫자[i] 위치를 바꾼다.

 

* 선택 정렬 Ω 에 대해 생각해보면

이미 정렬이 되어있다 하더라도 선택 정렬은 그대로 실행된다.

정렬이 완성됨을 확인하는 구간이 없다. 

따라서 Ω(n^2) 이 되므로 θ(n^2) 이 된다.

정렬이 최악으로 되어있으나 최선으로 되어있으나 알고리즘을 실행하는 시간은 같다.

 

 

 

 

Bubble sort

 

버블 정렬은 정렬할때 뒤 부터 정리가 되는데 그 모습이 거품이 올라가는 것 같아서

이름이 버블 정렬이다.

위의 예시와 같이 숫자를 정렬할 때

버블 정렬은 첫번째 자리부터 끝 자리 까지 당장 앞의 두 숫자를 비교하고 내가 정렬하려는 규칙과 맞게 자리를 바꾼다.

7 3 1 9 5 8 2 6 0 4 이 숫자에서 1회 돌면

3 1 7 5 8 2 6 0 4 9 가 된다. 2회 돌면

1 3 5 7 2 6 0 4 8 9 ---3회

1 3 5 2 6 0 4 7 8 9 ---4회

1 3 2 5 0 4 6 7 8 9 ---5회

1 2 3 0 4 5 6 7 8 9 ---6회

1 2 0 3 4 5 6 7 8 9 ---7회

1 0 2 3 4 5 6 7 8 9 ---8회

0 1 2 3 4 5 6 7 8 9 ---9회 

이렇게 정렬 되는 것이다. 절대 안잊으려 직접해봤는데 이해가 잘된다.

의사코드로 나타내면

n-1번 반복
 만약 0~n-2번째 자리까지 앞자리와 뒷자리 순서가 안맞으면 자리 바꿈
 만약 더이상 바꿀게 없다면 종료

 

 * 버블 정렬 Ω 에 대해 생각해보면

만약 이미 정렬되어 있다면 n-1번 바꿀 것이 있나 확인하고 없어서 종료된다.

그렇기 때문에 Ω(n) 이 되는 것이다.

여기서 선택정렬과 비교해보면 선택정렬과 O(n^2)으로 같은데 

선택정렬 : Ω(n^2)   버블정렬 : Ω(n) 로 다르다.

이것의 의미는 정렬하려는 대상이 현재 어떤 상태로 되어있느냐에 따라 

시간이 달라지고 선택해야하는 알고리즘도 달라질 수 있음을 뜻한다.

 

 

 

 

 

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)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            printf("#");
        }
        printf("\n");
    }
    
}

 

2중 for문 중첩을 통해 피라미드 모양을 찍는 프로그램을 만들어봤다.

이 경우 시간 복잡도는 O(n^2)으로 상당히 큰 편이다.

생각을 조금 바꿔서 피라미드는 전 # 에 #을 하나 더한 것이라 생각하고

재귀로 구현하면 어떨까?

#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");
}

 

이런 식으로 구현할 수 있는데 정확히 똑같이 작동하지만 

어디에서도 이중 for문은 볼 수 없고 for문 하나와 자기 자신을 호출하는 함수로 이루어진다.

 

* 재귀로 구현했을 때 장점

1. 가독성이 좋아진다. 이중 for문 보다 훨씬 읽기 편해진다.

2. 계산이 빨라진다. 

2중 for문의 O(n^2)보다 빨라지는건 확실하다.

하지만 재귀가 아무런 댓가 없이 빨라지는 것은 아니다.

재귀는 자기자신 함수를 계속 호출하기 때문에 더 넓은 공간을 필요로 한다.

즉 공간을 댓가로 시간을 얻는 것이다.

재귀가 만능은 아니지만 특별한 상황이 아니고선 재귀로 구현하는 것이 유리할 듯 하다.

 

 

 

 

 

Merge Sort

병합 정렬은 재귀를 이용한 빠른 정렬 방법이다.

왼쪽 정렬, 오른쪽 정렬,  합치기를 재귀로 반복한다.

정렬하고 병합하기를 가장 작은 단위부터 하는 것이다.

예를 들면  3 2 4 1 을 정렬 한다고 해보면

3 2 | 4 1 이렇게 나눠지고 

3 | 2 이렇게 나눠진다. 더 쪼갤 수 없는 작은 단위가 되었을 때 부터 병합이 시작된다.

3 | 2 에서 각각은 숫자가 1개이기 때문에 이미 정렬이 된 상태이다. 

여기서 합치면 2 3 이렇게 되는데 합치는 로직이 왼쪽과 오른쪽을 비교해서 순차적으로 합치는 것이다.

4 | 1 을 합치면 1 4 가 된다. 

2 3 | 1 4 여기서 합치면 1 2 3 4 가 된다.

의사코드로 나타내면 다음과 같다.

if 나눠지지 않으면
    return 종료
else 나눠진다면
    왼쪽 정렬
    오른쪽 정렬
    합치기

 

병합 정렬의 시간 복잡도를 생각해보면 직관적으로 떠올리기 쉽지 않다.

 

6 3 4 1 5 2 7 0 이라는 숫자를 8개를 정렬한다고 했을때 

이진 탐색때도 마찬가지지만 2로 쪼갠걸 2로 쪼개는 방식은 횟수가 log n 과 같은데 

즉 8을 2번씩 쪼개는 것은 8 > 4 > 2 > 1 총 3회 일어난다는 것이다. log 8 과 같다.

숫자가 8개 있으므로 총 3회가 겹겹이 걸쳐서 일어나는데

각 회차당 합치는 것은 갯수만큼의 시간이 걸린다. 즉 8 이므로 8번씩 3번 반복하는 꼴이 된다.

위 예시에서는 24라는 숫자가 나오고

시간 복잡도로 표기하면 O(n log n) 이 된다.

 

 * 병합 정렬 Ω 에 대해 생각해보면

만약 이미 정렬되어 있다고 해도 각 과정은 똑같이 실행된다.

나눠지지 않을 때 까지 재귀를 도는 것이지 완성됐을 때에 관련된 것은 없다.

그렇기 때문에 Ω(n log n) 이 되는 것이다.

여기서 버블정렬과 비교해보면 최선의 경우에선 버블 정렬이 더 빠를 수 있다.

버블정렬 : Ω(n)   병합정렬 : Ω(n log n)

 

 

 

p.s 선택정렬, 버블정렬, 병합정렬의 실제 코드는 포인터의 개념을 배운 후 번외편으로 구현해야겠다.

2024.03.05 - [Course/Harvard CS50X] - [CS50X] Week3 번외편(Sort 구현 - Selection, Bubble, Merge, 비트연산자 )