This is CS50 (4) Algorithms

Index

Searching

Big-O

Linear search

Structs

Sorting

Selection sort

Recursion

Merge sort

 

1. 검색 알고리즘 search

1) 선형 검색 Linear Search

psudocode

For i from 0 to n–1
    If i'th element is 50
        Return true
Return false

2) 이진 탐색 알고리즘 Binary Search: 분할 정복 기법

psudocode

If no items
    Return false
If middle item is 50
    Return true
Else if 50 < middle item
    Search left half
Else if 50 > middle item
    Search right half

 

Q. 만약 정렬되지 않은 배열이 있다면, 선형 검색이 빠를까요 이진 검색이 빠를까요?

정렬되지 않은 배열의 경우에는 선형 검색이 더 빠르다.

1. 선형 검색

- 시간 복잡도: O(n), n이 배열의 원소 갯수이다.

- 정렬되지 않은 배열, 정렬된 배열 모두 적용된다.

 

2. 이진 검색

- 시간 복잡도: O(log n), n이 배열의 원소 갯수이다.

- 정렬된 배열에 적용된다.

 

정렬되지 않은 배열을 이진 검색을 이용할 경우, 배열을 정리해야 하는데 그만큼의 시간이 소요되기 때문에 선형 검색이 빠르다.

2. 알고리즘 표기법

Big O 표기법

가장 대표적인 실행시간

• O(n^2)
• O(n log n)
• O(n): 이진 탐색 linear search
• O(log n): 이진 탐색 binary search
• O(1)

가장 대표적인 big Ω 실행시간

• Ω(n2)
• Ω(n log n)
• Ω(n): counting the number of items
• Ω(log n)
• Ω(1): 선형 탐색 linear search, 이진 탐색 binary search

Big-O 값보다 Omega 값이 좋아야 좋은 알고리즘이다.

 

3. 선형 검색 linear search

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

 

return 0; : 성공

return 1; : 실패

 

typedef struct {} : 자료형 선언

 

4. 버블 정렬 bubble sort

정의

두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법

 

특징

정렬 알고리즘 중 하나

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

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

 

psudocode

Repeat n–1 times
    For i from 0 to n–2
        If i'th and i+1'th elements out of order
            Swap them

 

버블 정렬의 수행 시간

(n-1) * (n-1)

n^2 - 1n - 1n + 1

n^2 - 2n + 1

= O(n^2)

 

알고리즘 별 실행시간

• O(n^2): bubble sort
• O(n log n)
• O(n): linear search
• O(log n): binary search
• O(1)

Q. 버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적이게 될까요?

효율적인 경우: 데이터가 크기가 작거나 정렬되어 있지 않을 때

비효율적인 경우: 데이터가 크기가 크거나 정렬되어 있을 때

 

5. 선택 정렬 selection sort

정의

매번 목표를 세워 가장 작은 값을 찾고 다음 작은 값을 찾는 방법을 선택정렬이라고 한다.

 

특징

1. 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.
2. 몇 번의 교환을 해주었는지 횟수를 셀 필요가 없다. 하지만 이 과정은 훨씬 더 많은 비교가 필요하므로 비용이 많이 든다.
3. 선택 정렬은 최선의 경우에도 최악의 경우에서 수행하는 횟수만큼 비교와 교환을 해주어야 하기 때문에, 정렬된 배열의 경우에는 비효율적이다.

psudocode

For i from 0 to n–1
    Find smallest item between i'th item and last item
    Swap smallest item with i'th item

 

선택 정렬의 수행시간

n + (n-1) + (n-2) + ... + 1

n(n+1)/2

(n^2 + n)/2

n^2/2 + n/2

O(n^2)

 

알고리즘 별 수행시간

• O(n^2): bubble sort, selection sort
• O(n log n)
• O(n): linear search
• O(log n): binary search
• O(1)

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

버블 정렬에 조건문을 추가하면 효율성을 더 올릴 수 있다.

이전 버블정렬

Repeat n–1 times
    For i from 0 to n–2
        If i'th and i+1'th elements out of order
            Swap them



조건문을 추가한 버블정렬

Repeat until no swaps
    For i from 0 to n–2
        If i'th and i+1'th elements out of order
            Swap them

 

알고리즘 별 수행시간

• Ω(n2): selection sort, bubble sort
• Ω(n log n)
• Ω(n): bubble sort
• Ω(log n)
• Ω(1): linear search, binary search

선택 정렬의 실행 시간의 하한도 버블 정렬처럼 더 단축시킬 수 있을까요?

버블 정렬은 이미 정렬된 배열에 대해 최선의 경우 시간 복잡도를 𝑂 ( 𝑛 ) O(n)로 최적화할 수 있지만, 선택 정렬은 그러한 최적화를 적용할 수 없습니다. 선택 정렬은 모든 경우에 대해 𝑂 ( 𝑛 2 ) O(n 2 ) 시간 복잡도를 가지며, 이는 알고리즘의 본질적인 작동 방식에 기인합니다.

 

7. 재귀 recursion

더 효율적인 알고리즘을 작성하는 법

특정 Line으로 가라고 알려줄 필요도 없이 무엇을 할지만 알려주면 된다.

Pick up phone book
 Open to middle of phone book
 Look at page
 If Smith is on page
     Call Mike
 Else if Smith is earlier in book
     **Search left half of book**
 Else if Smith is later in book
     **Search right half of book**
 Else
     Quit

 

정의

함수가 본인 스스로를 호출해서 사용하는 것

 

스택

동일한 함수를 계속해서 호출할 때마다 함수를 위한 메모리가 계속해서 할당된다.

함수가 호출될 때마다 사용하는 메모리

재귀를 사용할 때에는 과도하게 스택 메모리가 사용되지 않도록 주의해야 한다.

 

재귀적 정의 recursive definition

눈에 보이는 혹은 가상의 물체의 구조를 그 물체의 자체를 이용해서 설명하는 것

이진 탐색이나 분할 정복법에서처럼 기존 문제보다 더 작은 크기의 문제들을 풀어 간다.

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

void draw(int h);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int h)
{
    // If nothing to draw
    if (h == 0)
    {
        return;
    }

    // Draw pyramid of height h – 1
    draw(h – 1);

    // Draw one more row of width h
    for (int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}

 

8. 병합 정렬 merge sort

정의

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

If only one item
  Return
Else
    Sort left half of items
    Sort right half of items
    Merge sorted halves

 

단계

세단계로 구성된다.

1. 왼쪽 정렬

2. 오른쪽 정렬

2. 두 배열의 병합

 

시간 복잡도

• O(n^2): bubble sort, selection sort
• O(n log n): merge sort
• O(n): linear search
• O(log n): binary search
• O(1)

Omega 별 수행시간

• Ω(n2): selection sort, bubble sort
• Ω(n log n): merge sort
• Ω(n): bubble sort
• Ω(log n)
• Ω(1): linear search, binary search

Theta Θ

어떤 알고리즘의 상한선과 하한선이 같을 때 사용

• Θ(n2): selection sort, bubble sort
• Θ(n log n): merge sort
• Θ(n): bubble sort
• Θ(log n)
• Ω(1): linear search, binary search

Q. 병합 정렬을 선택 정렬이나 버블 정렬과 비교했을 때 장점과 단점은 무엇이 있을까요?

장점

- 안정적임

- n log n 성능을 보장함

- 대용량 데이터에 적합함

- 동시에 수행할 수 있음

- 정렬 여부에 관계 없이 예측 가능한 성능

단점

- n만큼의 추가 공간이 필요함

- 데이터가 작을 때 느림

- 구현하기 복잡함