[CS50 코칭스터디] 4주차_알고리즘

 

[4주차 개념]

✔️ 검색 알고리즘 - 선형 검색, 이진 검색

선형 검색 : 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사이진 검색 : 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은 값이 저장되어 있는 인덱스 또는 큰 값이 저장되어 있는 인덱스로 이동을 반복

 

✔️ 알고리즘 표기법 - Big O, Big Ω

Big O : 알고리즘 실행 시간의 상한

Big Ω : 알고리즘 실행 시간의 하한

-> 실행시간의 상한이 낮은 알고리즘이 좋다

 

✔️ 선행 검색 - 선형 검색, 구조체

선형 검색 : 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색 -> 정확하지만 아주 효율적이지 못한 방법 -> 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용

구조체 : 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용 -> 새로운 자료형으로 구조체를 정의해서 이름과 번호를 묶어줌

 

✔️ 버블 정렬

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

(단점 : 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생)

버블 정렬 실행 시간의 상한은 O(n^2)

버블 정렬의 실행 시간의 하한도 Ω(n^2)

 

✔️ 선택 정렬

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

(장점 : 교환 횟수를 최소화, 단점 : 각 자료를 비교하는 횟수는 증가)

소요 시간의 상한과 하한은 버블 정렬과 동일

 

✔️ 정렬 알고리즘의 실행시간 - Big O, Big Ω

실행시간의 상한(Big O)

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

  O(n log n)

  O(n): 선형 검색

  O(log n): 이진 검색

  O(1)

실행시간의 하한(Big Ω)

  Ω(n^2): 선택 정렬

  Ω(n log n)

  Ω(n): 버블 정렬

  Ω(log n)

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

 

✔️ 재귀

재귀 : 함수가 본인 스스로를 호출해서 사용할 수 있음, 함수를 함수 내에서 재사용 -> 코드 길이가 짧아져 효율적인 코딩 가능

 

✔️ 병합 정렬

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

병합 정렬 실행 시간의 상한은 O(n log n)

실행 시간의 하한도 Ω(n log n) 

 

[4주차 팀별미션]

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

int* SelectionSort(int a[], int size){ // 선택 정렬 함수
    int min;
    int temp; // 서로 교환하는 과정에서 필요한 임시 변수
    
    for(int i=0; i<size-1; i++){ // 첫번째 원소부터 시작하여 선택 정렬을 (n-1)번 반복하여 수행
        min = i; // 기준 위치 원소의 인덱스 i를 변수 min에 설정
        for(int j=i; j<size; j++){ // i번 원소로부터 마지막 원소까지 비교하면서 가장 작은 원소의 인덱스를 변수 min에 저장
            if(a[j] < a[min]) // 만약 min보다 작은 j번째 원소가 존재한다면
                min = j; // j를 변수 min에 설정
        }
        
        temp = a[i]; // 가장 작은 값 a[min]과 기준 원소 a[i]를 서로 교환하는 과정
        a[i] = a[min]; // "
        a[min] = temp; // "

    }
    
    return a; // 배열 리턴
}

int main(){
    
   printf("입력값 : ");
   int size = 5; // 배열의 크기 변수 출력
   
   int list1[5] = {1,1,1,3,2};
   for(int i=0; i<size; i++){ // list1 출력
        printf("%d", list1[i]);
    }
   SelectionSort(list1, size);
   int* num1 = SelectionSort(list1, size); // SelectionSort 함수에서 정렬된 배열을 num1에 반환
   
   printf(", ");
   
   int list2[5] = {2,1,1,3,1}; 
   for(int i=0; i<size; i++){ // list2 출력
        printf("%d", list2[i]);
    }
    SelectionSort(list2, size);
   int* num2 = SelectionSort(list2, size); // SelectionSort 함수에서 정렬된 배열을 num2에 반환
   
    printf("\n");
   
   if (num1[0] == num2[0] && num1[1] == num2[1] && num1[2] == num2[2] && num1[3] == num2[3] && num1[4] == num2[4]){ // 정렬된 list1과 list2가 같은 경우에
       printf("출력값 : True"); // true를 출력
   } else { // 만약 하나의 조건이라도 다르다면
       printf("출력값 : False"); // false 출력
   }
}