개발하는데 다 이유가 있겠지

검색 알고리즘

배열

• 한 자료형의 여러값들이 메모리상에 모여있는 구조
• 컴퓨터는 값에 접근할 때 인덱스( a[0]) 한개씩 확인

선형 검색(Linear Search)

배열의 인덱스 처음부터 하나씩 차례대로 검색하는 알고리즘

• 데이터의 개수가 늘어날수록 시간이 오래 걸리는 단점이 있음
• 최대 검색 횟수 : n회 (=데이터 수) → 끝까지 발견되지 않는 경우
• 평균 검색 횟수 : n / 2회
• 검색량 O(N)

이진 검색(Binary Search)

원하는 값을 찾을 때까지 검색할 데이터의 범위를 반씩 줄여가며 찾는 알고리즘

• 선형 검색과는 다르게 특정 기준에 따라 오름차순 또는 내림차순으로 정렬된 리스트를 받아야 함
• 최대 검색 횟수 : (log2n)+1
• 평균 검색 횟수 : log2n

---

알고리즘 표기법

Big-O 표기법 : 최악의 경우를 표시(최대 횟수, 실행시간의 상한)

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

Ω(Omega, 오메가) : 최상의 경우를 표시(최소 횟수, 실행시간의 하한)

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

Θ(Theta, 세타) : 최상과 최하가 같은 경우를 표시(상한선 == 하한선)

• Θ(n^2) - 선택 정렬
• Θ(n log n) - 병합 정렬

---

선형 검색(Linear Search)

원하는 값이 발견될 때까지 처음부터 끝까지 차례대로 검색하는 알고리즘(비효율적)

• 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용

#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;
        }
    }
    printf("Not found\n");
    return 1;
}

---

구조체(Structure Type)

• 여러 자료형을 가진 변수들을 하나로 묶어 자료형으로 사용할 수 있도록 정의하는 것

정의 및 선언

// 구조체의 정의와 typedef 선언을 동시에 할 때에는 구조체의 이름을 생략 가능
typedef struct (구조체 이름)
{
    멤버변수1의 타입 멤버변수1의 이름;
    멤버변수2의 타입 멤버변수2의 이름;
    ...
} 구조체의 새로운 이름;

//예시
typedef struct 
{
    string name;
    string number;
}
person;

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

//구조체를 캡슐화하여 정의
typedef struct
{
    string name;
    string number;
}
person;

int main()
{   
    // 자료형으로 구조체를 사용
    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;
}

---

버블 정렬(Bubble sort) : 인접값 비교하기

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

• 시간 복잡도 : O(n^2) / Ω(n^2)
• 정렬 여부와 상관없이 루프를 돌며 비교함(비효율적)

---

선택 정렬(Selection sort) : 최소값 or 최대값 골라내기

배열에서 최소값을 찾아 이 최소값을 배열의 첫 번째 요소와 교환하고 그 다음에는 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하여 두 번째 요소와 교환한다. 이 과정을 (배열의 크기-1) 만큼 반복하여 배열이 모두 정렬될 때까지 반복하는 정렬

• 시간 복잡도 : O(n^2) / Ω(n^2)
• 비교 횟수 : n(n+1)/2

---

정렬 알고리즘의 실행시간

• 실행시간의 상한
  • O(n^2): 선택 정렬, 버블 정렬
  • O(n log n): 병합 정렬
  • O(n): 선형 검색
  • O(log n): 이진 검색
  • O(1)
• 실행시간의 하한
  • Ω(n^2): 선택 정렬, 버블정렬
  • Ω(n log n): 병합 정렬
  • Ω(n) : 버블 정렬
  • Ω(log n)
  • Ω(1): 선형 검색, 이진 검색

❗️버블정렬의 경우 이미 정렬이 되어있는 숫자 리스트가 주어지면, ‘숫자간의 교환이 일어나지 않을때까지’로 조건을 수정해 실행시간 하한을 Ω(n)로 줄일 수 있음

---

재귀(Recursion) : 자기 자신을 호출하는 방법

함수가 자기 자신을 호출해서 다시 자신의 함수로 재진입하는 함수

• 첫 번째 함수는 끝나지 않고 계속 자신을 메모리 다른곳에 복사시켜 실행함
  • 함수가 호출될 때마다 사용되는 메모리(스택)
    • 함수가 종료되지 않고 계속 호출되는 경우, 스택공간이 초과되어 프로그램 충돌 발생
• 종료 조건 설정하여 무한 루프 방지(return)
• 중첩 루프를 사용하지 않아 코드가 간결해져서 가독성이 좋음

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

void draw(int h);

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

    draw(height);
}

void draw(int h)
{
    // 높이가 0이라면 (그릴 필요가 없다면)
        // 종료 조건 설정
    if (h == 0)
    {
        return;
    }

    // 높이가 h-1인 피라미드 그리기
        // 자기 자신 재호출
    draw(h - 1);

    // 피라미드에서 폭이 h인 한 층 그리기
    for (int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}

---

병합 정렬(Merge sort) : 분할 정복

원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합치면서 정렬하는 방법

• 예제 (7 4 5 2 6 3 8 1 오름차순 정렬)

• 시간 복잡도 : O(n log n) / Ω(n log n)
• 정렬 여부와 관계없이 나누고 병합을 진행