강좌 : 부스트캠프 모두를 위한 컴퓨터과학(cs50 2019)

4. 알고리즘

• ide.cs50.io 사이트 이용

✍검색 알고리즘

배열

• 한 자료형의 여러 값들이 메모리상에 모여 있는 구조
• 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근한다

선형검색

• 만약 배열이 정렬되어있지 않다면, 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사

이진검색

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

---

✍알고리즘 표기법

• Big-O : 알고리즘을 수행하는데 필요한 시간의 상한선을 의미 - 최악의 경우
• Omega : 알고리즘을 수행하는데 필요한 시간의 하한선을 의미 - 최상의 경우

---

✍선형검색

효율성 그리고 비효율성

• 선형검색 알고리즘은 정확하지만 아주 효율적이지 못한 방법
• 자료가 정렬되어 있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에 유용

완성

// 주어진 배열에서 숫자를 찾을때
#include<cs50.h>
#include<stdio.h>

int main(void)
{
    int numbers[] = {4,7,9,34,54,40};  // 배열 정의 및 값 입력

    for (int i=0;i<sizeof(numbers);i++)  // 배열의 크기만큼 반복
    {
        if(numbers[i]==50)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

// 주어진 배열에서 문자열을 찾을때
#include<cs50.h>
#include<stdio.h>
#include<string.h>

int main(void)
{
    string names[]={"홍길동", "김철수","김영희","임꺽정"};
    string numbers[]={"123-456","123-457","123-458","123-459"};

    for (int i=0;i<sizeof(numbers);i++)
    {
        if(strcmp(names[i],"홍길동")==0)  // strcmp : 두 문자열이 같다면 0을 반환
        {
            printf("Found %s\n",numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

++ 문자열을 비교하기 위해서는 == 를 사용할 수 없으므로 strcmp 사용한다 양수를 반환하면 첫번째 문자열이 알파벳기준으로 큰거이고 음수를 반환하면 반대

구조체(struct)

typedef : 새로운 타입을 정의한다의 의미
struct : C에 미리 정의된 키워드로 마치 그릇처럼 여러가지 자료형을 담을 수 있다

완성

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

typedef struct
{
    string name;
    string number;
}
person;  // person 이라는 이름의 구조체를 자료형으로 정의

int main(void)
{
    string n = get_string("name: ");  // 사용자에게 이름값을 받는다
    
    person people[4];

    people[0].name ="홍길동";
    people[0].number ="123-456";
    people[1].name ="김철수";
    people[1].number ="123-457";
    people[2].name ="김영희";
    people[2].number ="123-458";
    people[3].name ="임꺽정";
    people[3].number ="123-459";

    for (int i=0;i<sizeof(people);i++)
    {
        if(strcmp(people[i].name,n)==0)  // 두 문자열이 같은지 확인
        {
            printf("Found %s\n",people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}