명동 스터디_컴퓨터 과학 기초_4

명동 스터디 : 기초를 숙련한지 너무 오래되어 컴퓨터공학부 커리큘럼의 필수 과목과 관련된 공부를 통해 기초를 숙련하고 숙련된 기초를 통해 프로젝트 진행을 하기 위한 4명의 스터디 모임

 

기원 : ki-w0n.tistory.com

백범 : https://long-shift-6b9.notion.site/dbf9ea3ec9fd49379e43c127e470123a

찬형 : https://memo.chanhyung.kim/407d7b36c9204fb3813a42eac8674897

병묵 : https://manso98.notion.site/23723aa1c0bb44828b52fc57efa6639e

 

명동 스터디 첫번째 커리큘럼 일정(2024.07.29 ~2024.11.16)

- 컴퓨터 과학 기초(07.09 ~ 07.21)
- 이산수학(07.29 ~ 08.17)

- 자료 구조(08.19 ~ 09.07)

- 컴퓨터 구조(09.09 ~ 10.12)

- DB(10.07 ~ 10.26)
- 네트워크(10.28 ~ 11.16)

 

목차

 

---

 

---

 

알고리즘

선형검색

배열의 인덱스를 처음부터 끝까지 하나씩 증가

 

이진검색

만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복

---

 

알고리즘  표기

BIg-O 표기법

 

상수검색은 인풋의 크기와 상관 없이 항상 일정한 시간을 소요합니다.

로그검색은 상수시간 다음으로 빠른 시간 복잡도 입니다.

 

선형검색에서 사이즈가 n이면 n번의 검색이 필요 합니다. 인풋의 증가 시 같은 비율로 증가합니다.

이차검색은 인풋의 증가 시 n의 제곱 비율로 증가합니다.

팩토리얼검색은 가장느리고 비효율적입니다.

---

 

정렬

버블 정렬

버블 정렬은 시간 복잡도가 느리지만 코드가 매우 단순합니다.

서로 인접한 배열을 검사하여 정렬하는 알고리즘 입니다.

 

#include <stdio.h>
# define MAX 10

int* bubble_sort(int arr[], int n) {
    int i, j, temp;
    for (i=n-1; i>0; i--) {
        for (j=0; j<i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;

}

int main() {
    int arr[MAX] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
    int* arr_new = bubble_sort(arr, MAX);
    for (int i = 0; i < MAX; i++) {
        printf("%d\n", *(arr_new+i));
    }
    return 0;
}

 

선택 정렬

선택 정렬은 주어진 리스트에서 최소값을 찾고 그 값을 맨 앞으로 위차한 값과 교체합니다. 이런식으로 한 칸에 하나씩 선택하여 교체하는 과정으로 배열을 맞춰갑니다.

 

void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

 

병합 정렬

폰 노이만이라는 수학자가 제안한 정렬 방법입니다.

배열을 쪼개고 다시 합치는 과정을 통해서 정열해나가는 방식입니다.