[CS50 2019] 3. Algorithms

in Study #CS #C

모두를 위한 컴퓨터 과학

1. 알고리즘 표기법

Big-O 표기법

  • 알고리즘의 시간복잡도를 나타내는 방법 (O는 “on the order of”의 약자로, “~만큼의 정도로 커지는” 것을 의미)
  • 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간복잡도를 가진다는 의미
  • ex. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)과 같다.

많이 사용되는 Big-O 표기

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

Big-Ω 표기법

  • Big-O가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big-Ω는 알고리즘 실행 시간의 하한을 나타내는 것
  • 즉, Big-O는 최악의 경우에 대한 실행 시간, Big-Ω는 최선의 경우에 대한 실행 시간을 표현

많이 사용되는 Big-Ω 표기

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

2. 검색 알고리즘

만약 어떤 값이 배열 안에 속해 있는지를 찾아보기 위해서는 배열이 정렬되어 있는지 여부에 따라 아래와 같은 방법을 사용할 수 있다.

선형 검색

  • 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사
  • 정확하지만 아주 효율적이지 못한 방법
  • 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용
For i from 0 to n–1

    If i'th element is 50
        Return true
        
Return false

✔ 시간 복잡도

  • 최악의 경우: O(n)
  • 최선의 경우: Ω(1)

이진 검색

  • 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은 인덱스 또는 큰 인덱스로 이동을 반복
  • 선형 검색에 비해 효율적으로 동작하지만, 정렬되어 있지 않은 데이터에 대해서는 사용할 수 없음
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

✔ 시간 복잡도

  • 최악의 경우: O(log n)
  • 최선의 경우: Ω(1)

3. 정렬 알고리즘

버블 정렬

  • 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬
  • 단 2개의 요소만 정렬해주는 좁은 범위의 정렬에 집중
  • but, 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 있음
Repeat until no swaps
    For i from 0 to n–2
        If i'th and i+1'th elements out of order
            Swap them

✔ 시간 복잡도
n개의 값이 주어졌을 때 각 루프는 n-1번, n-2번 반복되므로 (n-1)*(n-2) = n^2-3n+2

  • 최악의 경우: O(n^2)
  • 최선의 경우: Ω(n)

선택 정렬

  • 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치의 수와 교환해주는 방식의 정렬
  • 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가
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)/2

  • 최악의 경우: O(n^2)
  • 최선의 경우: Ω(n^2)

병합 정렬

  • 분할 정복 알고리즘을 기반으로 하는 정렬 알고리즘
  • 배열을 두 부분으로 나눈 후, 각 부분을 재귀적으로 정렬하고, 정렬된 부분 배열을 합쳐 전체 배열을 정렬하는 방식
  • 분할 - 정복 - 병합의 단계를 거침
On input of n elements
    if n < 2
        return
    else
        sort left half of elements
        sort right half of elements
        merge sorted halves

✔ 시간 복잡도
숫자들을 반으로 나누는 데 O(log n), 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸림

  • 최악의 경우: O(n log n)
  • 최선의 경우: Ω(n log n)

💡 재귀 함수

  • 함수가 자기 자신을 호출해서 사용하는 것
  • 분할 정복 알고리즘에서 자주 사용됨


동일한 기능의 프로그램을 재귀를 이용하여 작성해보자.

⭐️ Code 1 (for문 사용)

int sigma(int n)
{
    if(n < 1)
    {
        return 0;
    }
    
    int sum = 0;
    for(int i=1; i<=n; i++)
    {
        sum += 1;
    }
    return sum;
}

⭐️ Code 2 (재귀 함수 사용)

int sigma(int n)
{
    if(n <= 0)
    {
        return 0;
    }
    else
    {
        return (n + sigma(n-1));
    }
}

✔ 재귀 함수를 사용할 때 주의할 점!

  • 스택: 함수가 호출될 때마다 사용되는 메모리
  • 재귀 함수를 이용하다 보면 함수가 종료되지 않고, 함수가 계속해서 호출되는 경우가 발생하기도 함
  • 이 경우 스택 공간은 초과되고 프로그램 충돌 발생 (Stack Overflow)
  • 따라서 재귀 함수를 사용할 때는 과도하게 스택 메모리가 사용되지 않도록 종료 조건을 설정해주어야 함