CS50_알고리즘

검색 알고리즘

선형 검색

배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는 지를 검사한다.

 

이진 검색

만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은 인덱스 또는 큰 인덱스로 이동을 반복한다.

알고리즘 표기법

Big O는 알고리즘 실행시간의 상한을 나타낸 것이다.

O(n)은 on the order of 의 약자로 쉽게 생각하면 ~만큼의 정도로 커지는 것이라고 볼 수 있다.

O(n)은 n만큼 거지는 것이므로 n이 늘어날 수록 선형적으로 증가하게 된다.

따라서 logn과 같은 형태가 되어야 좋은 성능을 낸다고 할 수 있겠다.

• O(n^^2)
• O(n log n)
• O(n) -선형검색
• O(log n) - 이진 검색
• O(1)

Big Ω는 알고리즘 실행 시간의 하한을 나타낸다.

예를 들어 선형 검색에서는 n개의 항목이 있을때, 최대 n번의 검색을 해야 하므로 상한이 o(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼 수 도 있으므로 하한은  Ω(1)이 된다.  

• Ω(n^^2)
• Ω(n log n)
• Ω(n) - 배열 안에 존재하는 값의 개수 세기
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

알고리즘은 보통의 상황보다 최악의 조건을 생각해야 하므로 알고리즘 실행시간의 상한이 낮은 것을 더 중요하게 생각해봐야 한다.

 

선형 검색

선형 검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다.

이렇게 해서 선형 검색은 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 한다.

 

선형 검색은 정확하지만 효율적이지 못하다.

하지만 자료가 정렬되어 있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에는 유용할 수도 있다.

 

버블 정렬

정렬 알고리즘 중 하나이다.

두개의 인접

한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다.

버블 정렬은 단 두개의 요소만 정렬해주는 좁은 범위의 정렬에 집중한다.

간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 있다.

선택 정렬

배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫번재 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.

선택 정렬은 교환횟수를 최소화하는 반면 자료를 비교하는 횟수는 증가한다.

 

정렬 알고리즘의 실행시간

실행시간의 상한 Big O

• O(n^2): 선택정렬, 버블 정렬
• O(n log n) : 병합정
• O(n):선형 검색
• O(log n):이진검색
• O(1)

실행시간의 하한

• Ω(n^2) : 선택 정렬, 버블 정렬
• Ω(n log n) : 병합 정렬
• Ω(n) : 버블 정렬(정렬이 잘 되어 있는 상황)
• Ω(log n)
• Ω(1) : 선형검색, 이진검색

 

재귀

함수가 본인 스스로를 호출해서 사용하는 것을 재귀라고 한다.

 

#로 이루어진 피라미드를 만들어 보면,

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

void draw(int h);

int main(void)
{
    // 사용자로부터 피라미드의 높이를 입력 받아 저장
    int height = get_int("Height: ");

    // 피라미드 그리기
    draw(height);
}

void draw(int h)
{
    // 높이가 h인 피라미드 그리기
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

높이를 입력 받아 중첩 루프를 통해 피라미드를 출력해주는 draw 함수를 정의한 것이다.

 

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

h라는 높이를 받았을 때, h-1 높이로 draw 함수를 먼저 호출하고, 그 후에 h만큼의 #을 출력한다.

여기서 내부적으로 호출된 draw함수를 따라가다 보면 h=0인 상황이 오게 된다.

따라서 그 때는 아무것도 출력을 하지 않도록 조건문을 추가하면 된다.

 

반복문을 써도 되는데 재귀를 사용하는 이유는

불필요하게 길어지는 코드를 줄여서 가독성을 높이고,

변수 할당이 적어 버그 발생도 적어지기 때문이다.

병합 정렬

원소가 한개가 될 때가지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.

 

즉 46123578이란 수가 있다면

 

4512 | 3578 로 반으로 나누고

 

45 | 12 | 3578 로 또 반으로 나누고

 

4 | 5 | 1 | 2 | 3578 이 된다.

 

그럼 이때 두숫자를 다시 병합하면서

 

작은 숫자가 먼저 오도록 한다.

 

그리고 다음 두숫자끼리를 병합하면서

 

작은 숫자가 먼저오도록 한다.

 

이렇게 반대편도 진행하다보면

 

결국 모든 숫자를 병합하면서 작은 숫자를 먼저오게 정렬시킬 수 있다.

https://www.boostcourse.org/cs112

모두를 위한 컴퓨터 과학 (CS50 2019)