원본 생성일: 2023-02-11
마지막 변경: 2023년 2월 13일

부스트 과정에 참여하기 부분

4. 알고리즘

1. 검색 알고리즘

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

배열은 하나의 데이터 유형의 여러 값을 메모리에 저장하는 구조입니다.
컴퓨터는 한 번에 모든 숫자를 파악할 수 없으며 배열의 내용을 한 번에 하나씩만 볼 수 있습니다.
따라서 배열에서 특정 값을 찾으려면 검색 알고리즘이 필요합니다.

선형 검색

처음부터 끝까지 1씩 증가시켜 배열의 인덱스를 방문하고 값이 해당 인덱스에 속하는지 확인합니다.
0에서 (n-1)까지의 i 만약 i번째 요소가 50이면 True를 반환 50이 없으면 False 반환

이진 검색

배열이 정렬되면 배열의 중간 색인에서 시작하여 찾고 있는 값과 비교하십시오.
더 작거나 더 큰 색인을 얻으려면 움직임을 반복하십시오.
남은 배열이 없다면 False 반환 만약 가운데 요소가 50이면 True를 반환 50이 가운데 요소보다 작으면 왼쪽 반을 탐색 50이 가운데 요소보다 크면 오른쪽 반을 탐색

2. 알고리즘 표기법

더 많은 데이터가 처리되고 작업이 더 복잡해짐에 따라 실행 시간이 더 중요해집니다.
알고리즘 실행 시간의 상한 및 하한을 지정할 수 있습니다.
빅 오, 빅 Ω

지속

프로그램이나 알고리즘이 실행되는 데 걸리는 시간

'추천 관련글,

몇 초 걸리는지
얼마나 많은 계산이 필요한지

빅오 빅오 표기법

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

O는 “~의 순서”를 의미합니다. ‘만큼 성장’
O(n): n의 순서로
대략적인 견적을 내다
계수 생략. 완료만 표시
문제가 충분히 크면 n의 차수가 같으면 곱한 계수는 거의 영향을 미치지 않습니다.

| Big-O |알고리즘|
|:-----:|:-----:|
|O(n^2)||
|O(nlogn)||
|O(n)|선형 검색|
|O(logn)|이진 검색|
|O(1)| |

빅Ω빅 오메가 표기

가장 좋은 경우입니다. 알고리즘 실행 시간의 하한

빅오의 반대

| 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) 버블 정렬

오(로그)

에) 선형 검색

오(로그) 이진 검색

오(1)
이진 검색이 선형 검색보다 낫다고 말하는 것은 옳지 않습니다.
이진 검색에는 정렬이 필요하기 때문입니다.
검색을 여러 번 반복해야 하는 경우에는 먼저 정렬하고 빠른 검색 방법을 사용하는 것이 장기적으로 유리할 수 있습니다.

빅 오	연산
오(n^2)	버블 정렬
오(로그)
에)	선형 검색
오(로그)	이진 검색
오(1)

버블 정렬 실행 시간의 하한

버블 정렬의 큰 오메가는 Ω(n^2)입니다.
이미 정렬된 입력이 있더라도 버블 정렬 알고리즘은 여전히 모든 입력을 확인해야 합니다.

| Big Ω | 알고리즘|
|:-----:|:-----:|
|Ω(n^2)|버블 정렬|
|Ω(nlogn)||
|Ω(n)||
|Ω(logn)||
|Ω(1)|선형 검색, 이진 검색|

5. 정렬 선택

선택 정렬의 원리와 실행 시간을 설명하고 구현합니다.

정렬 선택

배열의 데이터 중 가장 작은 수(또는 가장 큰 수)를 찾아 처음(또는 마지막) 위치의 수와 교체하는 방식

교환 수 최소화, 데이터 조정 수 증가
교환이 이루어지려면 정렬되지 않은 모든 숫자에 대해 비교를 수행해야 합니다.

i는 0부터 (n-1)까지
    i번째 항목부터 마지막 항목 사이에서 가장 작은 항목을 찾는다.
    가장 작은 항목을 i번째 항목과 바꾼다.

선택 정렬의 런타임 – Big O

n 항목을 확인합니다. 최소값을 찾아 이동한 다음 (n-1) 요소를 확인합니다…
n + (n – 1) + (n – 2) + … + 1 = n(n – 1)/2 -> O(n^2)

빅 오 연산

오(n^2) 버블 정렬, 선택 정렬

오(로그)

에) 선형 검색

오(로그) 이진 검색

오(1)

빅 오	연산
오(n^2)	버블 정렬, 선택 정렬
오(로그)
에)	선형 검색
오(로그)	이진 검색
오(1)

선택 기간 정렬 – Big Omega

정렬을 해도 최소값인지 알 수 없기 때문에 같은 확인 과정을 거친다.
Ω(n^2)

빅 Ω 연산

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

Ω(로그)

Ω(엔)

Ω(로그)

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

빅 Ω	연산
Ω(n^2)	버블 정렬, 선택 정렬
Ω(로그)
Ω(엔)
Ω(로그)
Ω(1)	선형 검색, 이진 검색

6. 정렬 알고리즘의 런타임

다양한 정렬 및 검색 알고리즘의 실행 시간은 Big O 및 Big Ω에서 정의할 수 있습니다.

향상된 버블 정렬

교환이 없을 때까지 반복
    i가 0에서 (n-2)까지
        만약 i번째와 (i+1)번째 요소의 순서가 잘못되었다면
            둘을 바꾼다

이미 정렬 중이고 스와핑이 없는 경우 반복을 중지하는 조건이 추가되었습니다.
-> 최상의 경우 n – 1이면 충분합니다. -> Ω(n)

빅 Ω 연산

Ω(n^2) 정렬 선택

Ω(로그)

Ω(엔) 향상된 버블 정렬

Ω(로그)

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

빅 Ω	연산
Ω(n^2)	정렬 선택
Ω(로그)
Ω(엔)	향상된 버블 정렬
Ω(로그)
Ω(1)	선형 검색, 이진 검색

7. 재귀

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

전화번호부에서 Mike Smith를 찾아보세요.

전화번호부를 집어들다
전화번호부 가운데를 엽니다.
페이지를 봐
스미스가 이쪽에 있다면
1. 전화 마이크
스미스가 그의 앞에 있다면
1. 책의 왼쪽 절반을 검색합니다.
스미스가 그의 뒤에 있을 때
1. 책의 오른쪽 절반을 찾으십시오.
끝까지 반복한 후에도 스미스가 없으면 검색이 중지됩니다.

기능 내에서 자기 자신을 호출 -> 재귀함수(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. 병합 정렬

병합 정렬은 재귀를 사용하여 구현할 수 있습니다.

병합, 정렬

요소가 존재할 때까지 계속 반으로 나눈 다음 다시 병합하는 정렬 방법

받은 입력에 항목이 하나라면
    그냥 반환
그렇지 않으면
    왼쪽 절반을 정렬
    오른쪽 절반을 정렬
    하나의 배열로 합침

분할 및 병합된 중간 수준 행렬을 임시로 저장하고 함수가 완료될 때까지 저장해야 하므로 메모리에 필요한 공간이 증가합니다.
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)
- 숫자가 이미 정렬되어 있는지 여부에 관계없이 나누고 결합해야 합니다.
  
  빅 오 연산
  
  오(n^2) 버블 정렬, 선택 정렬
  
  오(로그) 병합, 정렬
  
  에) 선형 검색
  
  오(로그) 이진 검색
  
  오(1)
  
  빅 Ω 연산
  
  Ω(n^2) 정렬 선택
  
  Ω(로그) 병합, 정렬
  
  Ω(엔) 향상된 버블 정렬
  
  Ω(로그)
  
  Ω(1) 선형 검색, 이진 검색
최악의 경우 다른 균주보다 훨씬 빠르지만 기껏해야 시간 낭비

빅 오	연산
오(n^2)	버블 정렬, 선택 정렬
오(로그)	병합, 정렬
에)	선형 검색
오(로그)	이진 검색
오(1)

빅 Ω	연산
Ω(n^2)	정렬 선택
Ω(로그)	병합, 정렬
Ω(엔)	향상된 버블 정렬
Ω(로그)
Ω(1)	선형 검색, 이진 검색

세타(Θ) 큰 세타 표기법

알고리즘의 상한과 하한이 동일한 경우 이 표기법을 사용합니다.

큰 Θ 연산

Θ(n^2) 정렬 선택

Θ(nlogn) 병합, 정렬

Θ(n)

Θ(로그)

Θ(1)

큰 Θ	연산
Θ(n^2)	정렬 선택
Θ(nlogn)	병합, 정렬
Θ(n)
Θ(로그)
Θ(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)
'''