4. 알고리즘

1) 검색 알고리즘

배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조이다. 컴퓨터가 이 값에 접근할 때는 배열의 인덱스 하나하나에 접근하게 된다. 배열 안에 어떤 값이 있는지 확인하기 위해서는 다양한 방법이 있다.

2) 알고리즘 표기법

Big O - 알고리즘 실행 시간의 상한 (최악의 경우)

Big Ω - 알고리즘 실행 시간의 하한 (최선의 경우)

• O(n^2)

• O(n log n)

• O(n)

• O(log n)

• O(1)

3) 선형 검색

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

모든 자료를 확인하기에 정확하지만 비효율적인 방법이다.

자료가 정렬되어있지 않거나, 추가적인 정보가 없어 모든 자료를 확인해야 하는 경우 유용하다.

#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[0].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";

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

4) 버블 정렬

버블 정렬은 정렬 알고리즘 중 하나로, 인접한 두 개의 자료 값을 비교하고 위치를 교환하는 방식으로 정렬하는 방법이다. 두개의 요소만 정렬하는 좁은 범위의 정렬에 집중하기에 간단하지만 정렬에 너무 많은 자원을 낭비하는 방법이기도 하다.

3 6 8 5 2 7 4 1

3 6 8 5 2 7 4 1

3 6 5 8 2 7 4 1 <

3 6 5 2 8 7 4 1 <

3 6 5 2 7 8 4 1 <

3 6 5 2 ****7 4 8 1 <

3 6 5 2 ****7 4 1 8 <

…

1 2 3 4 5 6 7 8

O(n^2)

Ω(n^2)

5) 선택 정렬

선택 정렬은 배열 안의 자료 중 가장 작은 수를 찾아 첫 번째(혹은 마지막)의 수와 교환하는 방식의 정렬이다. 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

6 3 8 5 2 7 4 1

1 3 8 5 2 7 4 6

1 2 8 5 3 7 4 6

1 2 3 5 8 7 4 6

1 2 3 4 8 7 5 6

1 2 3 4 5 7 8 6

1 2 3 4 5 6 8 7

1 2 3 4 5 6 7 8

O(n^2)

Ω(n^2)

6) 정렬 알고리즘의 실행시간

정렬의 조건을 추가해 효율을 높일 수 잇다.

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬

• O(n log n)

• O(n): 선형 검색

• O(log n): 이진 검색

• O(1)

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬

• Ω(n log n)

• Ω(n)

• Ω(log n)

• Ω(1): 선형 검색, 이진 검색

⇒ 버블 정렬의 안쪽 루프에서 교환이 발생하지 않는다면 정렬이 잘된 상황이기에 바깥쪽 루프의 조건을 교환이 발생하지 않을때까지로 수정하면 하한 시간이 바뀐다.

실행시간의 하한

• Ω(n^2): 선택 정렬

• Ω(n log n)

• Ω(n): 버블 정렬

• Ω(log n)

• Ω(1): 선형 검색, 이진 검색

7) 재귀

재귀는 스스로를 호출해 사용하는 함수를 말한다.

문제를 작게 쪼개 가장 작은 단위까지 쪼갠 후 그 문제를 해결한다. 같은 방식으로 큰 단위의 문제를 해결하게 설정하면 된다.

재귀는 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우나 반복문의 중첩 횟수를 예측하기 어려운 경우 사용한다.

8) 병합 정렬

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

분할 > 병합의 과정을 재귀적으로 거친다.

7 4 5 2 6 3 8 1

7 4 5 2 | 6 3 8 1 < 분할

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 < 병합

…

1 2 3 4 5 6 7 8

O(n log n)

Ω(n log n)