[모두를 위한 컴퓨터 과학(CS50 2019)] 알고리즘

1) 검색알고리즘 

- 선형검색(linear)
ㄴ 배열을 하나씩 순회하면서 찾아봄 

For i from 0 to n–1

    If i'th element is 50

        Return true

Return false

---

- 이진검색(binary)
ㄴ배열이 정렬되어있다는 것을 전제로, 배열 중간부터 찾아서 찾고자 하는 값과 비교함
ㄴ찾고자 하는 값이 찾은 값보다 크면 오른쪽, 찾고자 하는 값이 찾은 값보다 작으면 왼쪽으로 이동함

If no items

    Return false

If middle item is 50

    Return true

Else if 50 < middle item

    Search left half

Else if 50 > middle item

    Search right half

 

2) 알고리즘 표기법

- Big O 표기법
ㄴO는“on the order of(~만큼의 정도로 커지는)”의 약자
ㄴ알고리즘실행 시간의 상한을 나타낸 것
ㄴ예시) 선형검색은 n개의 항목이 있을 때 최대 n번의 검색을 해야함 => O(n)

• O(n^2)
• O(n log n)
• O(n) - 선형 검색
• O(log n) - 이진 검색
• O(1)

---

- Big Ω 표기법
ㄴ오메가는 best case를 나타냄 
ㄴ알고리즘실행 시간의 하한을 나타낸 것 
ㄴ예시) 선형검색은 n개의 항목이 있을 때 최소 1번의 검색을 해야함 = > Ω(1)

• Ω(n^2)
• Ω(n log n)
• Ω(n) - 배열 안에 존재하는 값의 개수 세기
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

---

3) 선형검색

ㄴ정렬되지 않은 자료 검색시 유용 

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

int main(void)
{
    int numbers[] = {4, 8, 15, 16, 23, 42};

    for (int i = 0; i < 6; i++)  //순서대로 하나씩 찾음 = 선형검색
    {
        if (numbers[i] == 50)  //50이 있으면
        {
            printf("Found\n"); //찾았다 출력후
            return 0;		   //exit
        }
    }
    printf("Not found\n");     //루프를 모두 순회 했는데도 없으면
    return 1;
}

 

문자열로 이루어진 배열 검색 

#include <cs50.h>
#include <stdio.h>
#include <string.h> //strcmp()포함된 라이브러리

int main(void)
{
    string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    string numbers[] = {"617–555–0100", "617–555–0101", "617–555–0102", "617–555–0103"};

    for (int i = 0; i < 4; i++)
    {
        if (strcmp(names[i], "EMMA") == 0) //C에서는 문자열자체가 배열이기 때문에 
	//문자열에서 하나씩 꺼내서 비교하거나(바로 비교 안됨), strcmp()라는 문자열비교함수 사용 ()안의 문자열이 같으면 0리턴
   	 //strcmp(문자열1, 문자열2)
   	 //양수반환하면 문자열 1이 알파벳 기준으로 큰 경우 , 음수반환하면 반대의 경우
        {
            printf("Found %s\n", numbers[i]);
            return 0;  //값을 찾았을 때 찾았다고 알려줘야함
        }
    }
    printf("Not found\n");
    return 1;
}

 위와 같은 자료구조에는 1사람의 이름과 전화번호가 다른 인덱스를 가질수도 있어 아래와 같이 구조체를 정의해서 사용가능
ㄴ위코드 보다 아래 코드가 훨씬 더 디자인상 좋음 

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

typedef struct  
{
    string name;
    string number;
}
person;  //정의한 구조체의 이름 정의 

int main(void)
{
    person people[4];  //내가 정의한 person타입으로 people배열 만듦

    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";

    // EMMA 검색
    for (int i = 0; i < 4; i++)
    {
        if (strcmp(people[i].name, "EMMA") == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

---

4) 버블정렬

ㄴ데이터 양 적고, 정렬 안되어있을 때 좋음
ㄴ두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법
ㄴn개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복 
ㄴ(n-1)*(n-2) = n^2-3n+2(n−1)∗(n−2)=n​2​​−3n+2  번의 비교 및 교환이 필요
ㄴ실행시간 상한, 하한 모두 n^2 (O(n^2), Ω(n^2))
ㄴ맨뒤 부터 정렬됨

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

---

5) 선택정렬

ㄴ배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬
ㄴ교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가
ㄴ실행시간 상한, 하한 모두 n^2 (O(n^2), Ω(n^2))
ㄴ맨앞 수부터 정렬이 됨

For i from 0 to n–1

    Find smallest item between i'th item and last item

    Swap smallest item with i'th item

---

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

실행시간의 상한

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

 

실행시간의 하한

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

---

7) 재귀 

//높이를 입력받아 중첩루프를 통해 입력한 높이만큼의 피라미드 출력
#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
    // 사용자로부터 피라미드의 높이를 입력 받아 저장
    int height = get_int("Height: ");

    // 피라미드 그리기
    draw(height);
}

void draw(int h)
{
    // 높이가 h인 피라미드 그리기
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

위함수 중 draw함수를 아래와 같이 재귀함수로 수정할수 있음 

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");
}

---

8)병합 정렬  (merge sort)

ㄴ원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식
ㄴ정렬실행시간의 상항도 하한도 n log n (O(log n), Ω(n log n) 

7 4 5 2 6 3 8 1
4 7 2 5 3 6 1 8 
2 4 5 7 1 3 6 8 
1 2 3 4 5 6 7 8