본문 바로가기
NOTES/CS50

[CS50] Chapter 4. 알고리즘

보노졍 2023. 2. 13. 21:33

 

최초작성일: 2023-02-11
마지막 수정일: 2023-02-13

부스트코스 <모두를 위한 컴퓨터 과학 (CS50 2019)> 강의 수강

4. 알고리즘

1. 검색 알고리즘

  • 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다.
  • 선형 검색, 이진 검색

 

  • 배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조
  • 컴퓨터는 모든 숫자를 한 번에 파악할 수 없고 배열 속 내용물을 하나씩 볼 수 있다.
  • 그래서 배열 속에서 특정 값을 찾는 검색 알고리즘이 필요

선형 검색

  • 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사
0부터 (n - 1)까지의 i
	만약 i번째 요소가 50이면
    	True를 반환
50이 없으면
	False 반환

이진 검색

  • 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작해 찾고자 하는 값과 비교.
  • 그보다 작은 인덱스 또는 큰 인덱스로 이동을 반복
남은 배열이 없다면
	False 반환
만약 가운데 요소가 50이면
	True를 반환
50이 가운데 요소보다 작으면
	왼쪽 반을 탐색
50이 가운데 요소보다 크면
	오른쪽 반을 탐색

 

2. 알고리즘 표기법

  • 처리하는 데이터가 많아지고 작업이 복잡해질수록 실행 시간이 중요해짐
  • 알고리즘의 실행 시간의 상한과 하한을 표기할 수 있다.
  • Big O, Big Ω

 

실행 시간

프로그램이나 알고리즘이 동작하는 데 걸리는 시간

  • 몇 초가 걸리는지
  • 몇 번의 계산 과정이 필요한지

Big O 빅 오 표기법

알고리즘을 수행하는 데 필요한 시간의 상한선

  • O는 'on the order of'의 약자. '~만큼의 정도로 커지는'
  • O(n): on the order of n
  • 대략적인 추정값을 표기하는 것
  • 계수 생략. 차수만 나타냄
  • 문제가 충분히 크다면 n의 차수가 같을 때 곱해진 계수는 거의 영향을 주지 못함
Big - O 알고리즘
O(n^2)  
O(nlogn)  
O(n) 선형 검색
O(logn) 이진 검색
O(1)  

 

Big Ω 빅 오메가 표기법

최상의 경우. 알고리즘 실행 시간의 하한

  • Big-O의 반대
Big Ω  알고리즘
Ω(n^2)  
Ω(nlogn)  
Ω(n) 배열 안에 존재하는 값의 개수 세기
Ω(logn)  
Ω(1) 선형 검색, 이진 검색

 

Omega 값과 Big-O 값 중 어느 것이 좋아야 좋은 알고리즘인가?

  • Big-O
  • 컴퓨터 과학자가 가장 걱정하는 부분은 최악의 경우에 프로그램이 어떻게 동작할지, 또는 평균적으로 어떻게 동작하는지.

 

3. 선형 검색

  • 주어진 배열 또는 구조체에서 선형 검색을 할 수 있다.
  • 선형 검색, 구조체

선형 검색

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

효율성 & 비효율성

  • 선형 검색 알고리즘은 정확하지만 효율적이지 못함.
  • 선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에 유용
  • 정렬은 시간이 오래 걸리고 공간을 더 차지하지만, 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시간을 단축할 수 있음.

예시

특정 숫자 찾기
#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // numbers 배열 정의 및 값 입력
    int numbers[] = {4, 8, 15, 16, 23, 42};

    // 값 50 검색
    for (int i = 0; i < 6; i++)
    {
        if (numbers[i] == 50)
        {
            printf("Found\n");
            return 0;   //main 함수 종료
        }
    }
    printf("Not found\n");
    return 1;   //main 함수 종료
}
전화번호부에서 특정 이름 찾아 전화번호 출력
#include <stdio.h>
#include <cs50.h>
#include <string.h>

int main(void)
{
    string names[4] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    string numbers[4] = {"617-555-0100", "617-555-0101", "617-555-0102", "617-555-0103"};
    // 이름과 전화번호의 순서가 반드시 일치할까?

    for (int i = 0; i < 4; i++)
    {
        // if (names[i] == "EMMA") -> 안 됨
        //C에서 '=='는 문자열에 사용 불가. 문자열 속 문자를 하나씩 비교해야.
        if (strcmp(names[i], "EMMA") == 0)  //문자열비교함수. 같으면 0을 반환
        {
            printf("%s\n", numbers[i]);
            return 0;
        }
        printf("Not found\n");
        return 1;
    }
}
  • 이름과 번호의 인덱스가 일치해야 함.
  • 만약 각각 정렬이라도 한다면?
#include <stdio.h>
#include <cs50.h>
#include <string.h>

// 캡슐화

typedef struct      // 새로운 타입을 정의한다.
                    // struct(구조체)는 C에 미리 정의된 키워드
                    // 여러가지 자료형을 담을 수 있음
{
    string name;
    string number;
}
person;     // 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";

    for (int i = 0; i < 4; i++)
    {
        if (strcmp(people[i].name, "EMMA") == 0)
        {
            printf("%s\n", people[i].number);
            return 0;
        }
        printf("Not found\n");
        return 1;
    }
}
  • 새로운 자료형으로 구조체(struct)를 정의해서 이름과 번호를 묶어줌
  • 더욱 확장성 있는 전화번호부 검색 프로그램을 만들 수 있다.

 

4. 버블 정렬 (Bubble sort)

  • 버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다.

버블 정렬

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

  • 간단하고 직관적인 방법
  • 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중
  • 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 있음
  • n개의 원소에 대해 버블 정렬을 한 번 수행할 때마다 n번째의 원소가 제 자리를 찾음.
(n-1)번 반복
    i가 0에서 (n-2)까지
        만약 i번째와 (i+1)번째 요소의 순서가 잘못되었다면
            둘을 바꾼다

버블 정렬의 실행 시간 상한

  • 바깥 반복문 (n - 1)번, 안쪽 반복문 (n - 1)번 반복
    (n - 1) x (n - 1) -> O(n^2)
  • 이진 검색이 선형 검색보다 좋다고 하는 것은 옳지 않다.
  • 이진 검색은 정렬하는 과정이 필요하기 때문
  • 검색을 여러 번 반복해야 하는 상황이라면 먼저 한 번 정렬해두고 빠른 검색법을 이용하는 게 장기적인 이득을 볼 수 있다.

버블 정렬의 실행 시간 하한

  • 버블 정렬의 빅오메가는 Ω(n^2)
  • 이미 정렬된 입력이 들어왔다 해도 버블 정렬 알고리즘은 여전히 모두 확인하도록 되어 있기 때문에.

5. 선택 정렬 (Selection sort)

  • 선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다.

선택 정렬

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

  • 교환 횟수는 최소화, 각 자료 비교 횟수는 증가
  • 한 번의 교환이 일어나기 위해 정렬되지 않은 모든 수와 비교가 이루어져야 함.
i는 0부터 (n-1)까지
    i번째 항목부터 마지막 항목 사이에서 가장 작은 항목을 찾는다.
    가장 작은 항목을 i번째 항목과 바꾼다.

선택 정렬의 실행 시간 - 빅 오

  • n개 항목을 확인. 최솟값 찾아서 옮긴 후 (n-1)개 항목 확인...
    n + (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 -> O(n^2)

선택 정렬의 실행 시간 - 빅오메가

  • 정렬되어 있다 해도 그것이 최솟값인지 모르기 때문에 똑같이 확인하는 과정을 거칠 것임.
    Ω(n^2)

 

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

  • 여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있다.

버블 정렬 개선

교환이 없을 때까지 반복
    i가 0에서 (n-2)까지
        만약 i번째와 (i+1)번째 요소의 순서가 잘못되었다면
            둘을 바꾼다
  • 이미 정렬되어 교환이 일어나지 않으면 반복이 멈추는 조건을 추가.
    -> 최선의 경우 n - 1번이면 됨. -> Ω(n)
    Big Ω 알고리즘
    Ω(n^2) 선택 정렬
    Ω(nlogn)  
    Ω(n) 개선된 버블 정렬
    Ω(logn)  
    Ω(1) 선형 검색, 이진 검색

7. 재귀 (Recursion)

  • 함수를 재귀적으로 사용하는 코드를 작성할 수 있다.
  • 재귀

전화번호부에서 Mike Smith 찾기

  1. 전화번호부를 든다.
  2. 전화번호부의 중간을 편다.
  3. 페이지를 살펴본다.
  4. Smith가 그 페이지에 있으면
    1. Mike에게 전화
  5. Smith가 그보다 앞에 있으면
    1. 책의 왼쪽 반을 찾아본다.
  6. Smith가 그보다 뒤에 있으면
    1. 책의 오른쪽 반을 찾아본다.
  7. 끝까지 반복해도 Smith가 없으면 탐색을 그만 둔다.
  • 함수가 내부에서 자기 자신을 호출 -> 재귀함수(recursion function)

재귀

  • 함수가 본인 스스로를 호출해서 사용
  • 재귀적 정의: 물체의 구조를 그 물체 자체를 이용해서 설명하는 것
  • 시작점에 대해서는 직접 이건 특별한 경우이니 아무것도 하지 말라고 재귀적으로 자신을 호출하지 않게 알려줘야 함.

피라미드 그리기 - 반복문

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

void draw(int h);

int main(void)
{
    int height = get_int("Height: ");

    draw(height);
}
// 중첩 반복문
void draw(int h)
{
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

피라미드 그리기 - 재귀

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

void draw(int h);

int main(void)
{
    int height = get_int("Height: ");

    draw(height);
}

void draw(int h)
{
    if (h == 0)     //시작점. 하드 코딩된 조건문으로 의도치 않은 반복을 막음.
    {
        return;
    }

    draw(h - 1);

    for (int i = 0; i < h; i++)     // 마지막 한 줄
    {
        printf("#");
    }
    printf("\n");
}
  • draw(4) 호출 -> draw(3) 호출 -> draw(2) -> draw(1) -> draw(0) 호출
  • 재귀적으로 스스로를 호출하면서 기존 문제보다 더 작은 크기의 문제를 풀어간다.

스택

  • 재귀 함수에서 동일한 함수를 계속해서 호출할 때마다 함수를 위한 메모리가 계속 할당됨.
  • 스택: 함수가 호출될 때마다 사용되는 메모리
  • 컴퓨터가 일을 처리할 때 관리하는 역할인 운영체제는 함수를 실행할 수 있게 일정량의 바이트를 주고, 그 공간에 함수의 변수나 다른 것들을 저장할 수 있게 함.
  • 재귀함수를 이용하다보면 함수가 계속 호출되어 스택 공간이 초과되는 경우 발생.
  • 재귀를 사용할 때는 과도하게 스택 메모리가 사용되지 않도록 주의해야.

 

8. 병합 정렬 (Merge sort)

  • 재귀를 활용한 병합 정렬을 구현할 수 있다.

병합 정렬

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

받은 입력에 항목이 하나라면
    그냥 반환
그렇지 않으면
    왼쪽 절반을 정렬
    오른쪽 절반을 정렬
    하나의 배열로 합침
  • 나누어지고 합쳐지는 중간 단계의 배열을 임시로 저장하고 함수가 종료될 때까지 기억하고 있어야 하기 때문에 메모리의 필요한 공간이 늘어남.
  • n개의 원소가 있을 때 완전히 다 나누어지기까지 호출되는 함수의 개수가 log n개
  • 합쳐지는 과정에서 각 원소들의 크기를 비교하여 n번의 비교 과정이 있음

예시

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
...

병합 정렬의 실행 시간

  • 실행 시간의 상한: O(n log n)
    • 숫자들을 반으로 나누는 데 O(log n)의 시간, 반으로 나눈 부분들을 다시 정렬해 병합하는 데 각각 O(n)의 시간
  • 실행 시간의 하한: Ω(n log n)
    • 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요
      Big-O 알고리즘
      O(n^2) 버블 정렬, 선택 정렬
      O(nlogn) 병합 정렬
      O(n) 선형 검색
      O(logn) 이진 검색
      O(1)  

      Big Ω 알고리즘
      Ω(n^2) 선택 정렬
      Ω(nlogn) 병합 정렬
      Ω(n) 개선된 버블 정렬
      Ω(logn)  
      Ω(1) 선형 검색, 이진 검색
  • 최악의 경우 다른 정렬보다 훨씬 빠르지만 최선의 경우 시간을 낭비

theta(Θ) 빅 세타 표기법

  • 어떤 알고리즘의 상한선과 하한선이 같을 때 이 표기법 사용.
    Big-Θ 알고리즘
    Θ(n^2) 선택 정렬
    Θ(nlogn) 병합 정렬
    Θ(n)  
    Θ(logn)  
    Θ(1)  

병합 정렬 - 배열의 병합 구현

def merge(a_list, b_list):
    sorted_list = [0] * (len(a_list) + len(b_list))
    i = j = k = 0   # a_list, b_list, sorted_list의 인덱스

    while i < len(a_list) and j < len(b_list):
        if a_list[i] < b_list[j]:       # 더 작은 걸 정렬된 리스트의 앞에 넣기
            sorted_list[k] = a_list[i]
            k += 1
            i += 1
        else:
            sorted_list[k] = b_list[j]
            k += 1
            j += 1
    while i < len(a_list):              # a_list나 b_list 중 남아있는 것 마저 넣기
        sorted_list[k] = a_list[i]
        k += 1
        i += 1
    while j < len(b_list):
        sorted_list[k] = b_list[j]
        k += 1
        j += 1
    return sorted_list                  # 정렬된 리스트 반환


def merge_sort(unsorted_list):
    if len(unsorted_list) <= 1:     # 배열에 수가 하나 이하일 땐
        return unsorted_list        # 그냥 리턴

    mid = len(unsorted_list) // 2   # 그게 아니라면 리스트 반으로
    left = unsorted_list[:mid]
    right = unsorted_list[mid:]

    left_sorted = merge_sort(left)      # 반으로 나눈 리스트를 각각 병합 정렬
    right_sorted = merge_sort(right)
    return merge(left_sorted, right_sorted)     # 정렬된 리스트를 병합해 리턴


data = [7, 4, 5, 2, 6, 3, 8, 1]

print(merge_sort(data))
'''
[1, 2, 3, 4, 5, 6, 7, 8]
'''

'NOTES > CS50' 카테고리의 다른 글

[CS50] Chapter 6. 자료구조  (0) 2023.03.04
[CS50] Chapter 5. 메모리  (0) 2023.02.25
[CS50] Chapter 3. 배열  (2) 2023.02.04
[CS50] Chapter 2. C언어  (1) 2023.01.30
[CS50] Chapter 1. 컴퓨팅 사고  (0) 2023.01.30

'NOTES/CS50' Related Articles

티스토리툴바