CS50 2019 (8)검색, Big-O, Omega, 선형 검색, 구조체

===

www.boostcourse.org/cs112

모두를 위한 컴퓨터 과학 (CS50 2019)

1.컴퓨팅사고

2.C언어

3.배열

4.알고리즘

5.메모리

6.자료구조

 

===============================================================

이진 검색의 오메가가 1인 경우는 우연히 가운데에 찾는 값이 있는 경우, 버블은 조건이 있는 버블인듯

1)검색 알고리즘

▽내 기억에 알고리즘은 학자들이 문제 해결을 위해 고안해낸 쩌는 방법들을 검증하고 검증해서 모아놓은 것이라고 알고있음

 

이번에 알고리즘을 경험해보고 나머지 학기 동안 계속 같은 개념을 적용할 것.

 

메모리 = 임의 접근 기억장치 = RAM

이걸 byte단위로 나누면, 바둑판처럼 메모리를 보기시작하면 개념적으로나 물리적으로나 매우 편리하다는 것을 깨달았음

 

왼쪽에서 오른쪽, 그리고 위에서 아래 자료구조를 사용할 수 있었습니다.

지난시간에 배운 배열을 예시로 메모리를 바이트의 격자 배열로 취급하면 우리가 원하는 대로 사용할 수 있습니다

 

===

실생활에서 보면 배열이라는 개념은 집단의 사물함 같다

사물함에 숫자가 들어있다고 했을 때

사람은 한눈에 사물함의 내용을 전반적으로 파악할 수 있지만 컴퓨터는 그럴 수 없다

여러분과 저처럼 빠르게 한눈에 훑고 전체를 파악하는 감지 능력이 없다

컴퓨터는 배열 속 내용물을 하나하나 봐야한다(▽그래서 사물함 문을 닫아놓은듯, 열어야 숫자를 아는)

알고리즘과 비슷하다

컴퓨터는 모든 숫자를 한 순간에 파악할 수 없고

여기 서랍을 한 번에 한 개씩만 열어볼 수 있다

 

===

그런 의미에서 제가 7개의 서랍 속에 미리 숫자 7개를 넣어둠

그리고 학생들에게 7개 중에 어떤 하나의 숫자 찾기를 시킨다

 

이 문제를 컴퓨터과학적으로 설명하면 입력값은 7개의 서랍이며

결과값은 불리언 값 즉 참 혹은 거짓으로 

찾는 숫자가 이 7개의 서랍 중에 있는지를 나타냅니다

 

어떤 알고리즘으로 숫자를 찾는것인가!

그리고 맞고 틀린 지 뿐만 아니라

알고리즘은 정확했나, 가장 효율적이었나 를 따짐

 

학생1 : 숫자가 정렬됐는지 아닌지를 물어봤고, 답할 수 없다고 들었을 때 직접 하나하나 확인하는 수밖에 없다고 말함

학생2 : 이진탐색 알고리즘을 썼다

 

===

선형 탐색 : 처음부터 순서대로

이진 탐색 알고리즘(binary search) : 문제를 계속해서 두 갈래로 나눠 가는것이 이진 탐색을 반복적으로 하는것

 

이진 : 2

전화번호부 가운데부터 확인한뒤 나머지 가운데 찍는 분할정복기법도 이진 탐색

 

===

각 알고리즘이 어떻게 정확하게 문제를 풀었는지, 개선점은 없는지에 대해 살펴보자

 

일단 의사코드를 이렇게 적어볼 수 있습니다

 

선형탐색

For i from 0 to n-1

  If i'th element is 50

    Return true --이 알고리즘이 반환하는 불리언 값

Return false --모두 다 뒤졌는데도 없다면, 이 알고리즘에서 루프가 끝난 후 마지막에는 나머지 상황을 처리하기 위해 거짓을 반환해야 합니다.루프를 다 돌았는데 false가 나오면 50이 없다는 의미일 것

 

이진 탐색

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)알고리즘 표기법

(▽여러 알고리즘 마다 성능이 다르다는 것 먼저)

첫 주에 봤던 그림이야

알고리즘은 직선으로 그려지는 선형의 형태이거나

아니면 좀 더 굴곡이 있거나

로그 형태일 수도 있다

▽log는 사이즈가 커지는것보다 해결하는 시간이 덜 증가하네, n애들은 더 증가하고

 

이 모양은 각 알고리즘이 최악의 경우에 필요한 계산 수를 나타낸다

전화번호부나 서랍의 개수를 n으로 나타내면

n은 선형탐색

n/2는 전화번호부를 2페이지씩 보거나 서랍을 두 손으로 여는것, 선형탐색과 이진탐색의 중간쯤이다.

로그 함수는 좀 더 완만한 형태

 

===

(▽그 성능을 다르다는걸 말할 때, Big-O)

컴퓨터 과학자들은 알고리즘을 설명하기 위해 특정 용어를 사용합니다

알고리즘이 얼마나 잘 설계되어 있는지 또 코드가 얼마나 잘 구현되었는지 말해줍니다

가장 일반적으로 Big-O 표기법을 사용합니다

이름 그대로 대문자 O로 나타냄

 

누군가 당신의 알고리즘이 얼마나 효율적인지 물어본다면 (코드의 효율성을 묻는다면)

손짓 몸짓으로 휘적대며 코드의 속도를 대략 알려줄 수 있을텐데, Big-O도 대략적인 추정값을 표현하는 것이다

 

n번, n/2번, log n번이라 말하지 않고 컴퓨터 과학자들은 그 알고리즘은 O(n) 또는 O(n/2) 또는 O(log2n) 라고 말함

▽on the order of N 이라고 읽는다

수학에서의 함수 표기와 비슷하게 생김  ▽f(x) 이거?

 

위와 같은 그림을 공식으로 표기한 것이 Big O 표기법입니다.

여기서 O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것이라고 볼 수 있습니다.

 

Big-O 표기법을 사용하면, 손짓으로 말하는것처럼 대략적인 추정값을 표현하는것임

n과 n/2는 비슷하게 생겼기 때문에 /2를 없애버려도 

log2n의 밑 2도 큰 의미 없으니 없다고 생각하기 로그 함수 끼리는 대부분 비슷한 모양이니까

 

왜?

만약 우리가 푸는 문제가 충분히 크다면

즉 문제가 계속 커져서 이 정도 크기의 화면에 담기도록 축소해서 보기 위해 x축과 y축을 늘려본다면 둘이 가까워질것, 더욱 더 크기가 큰 문제를 본다면?

따라서 컴퓨터 과학자는 알고리즘의 효율성을 설명할 때 정확히는 O(n/2)일지라도 그냥 O(n)이라고 말합니다

로그의 경우도 그냥 O(log n)이라고 말합니다 매우 수학적인 것 같으면서도 손짓과 같이 대략 표현하는 셈

 

---

O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있습니다.

주로 아래 목록과 같은 Big O 표기가 실행 시간을 나타내기 위해 많이 사용됩니다.

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

 

Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것입니다.

예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 됩니다.  ▽이진 탐색도 우연히 가운데에 찾는값이 있는 경우 1

역시 아래 목록과 같은 Big Ω 표기가 많이 사용됩니다.

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

---

 

세상에는 다양한 알고리즘이 있는데 여기 가장 대표적인 실행 시간을 요약해봤습니다

실행 시간이란 프로그램이나 알고리즘이 동작하는 데 걸리는 시간을 말함. 몇초가 걸리는지 몇 번의 계산 과정이 필요한지

 

이렇게 정리해놓고 보면

각각에 해당하는게 어떤 알고리즘인지 살피기. 나머지는 어떤것인지 곧 배울 것

 

리니어 서치(선형검색) : O(n). 최악의 경우에 모든 서랍을 열어본다  ▽왜 최악을 생각해야하는지도 저 아래 학생질문에 답

이진 탐색 : log n

 

목록 아래쪽에 있다는 것은 위쪽에 있는 것보다 빠른것

 

===

Big Ω

컴퓨터 과학자에게 사실 또 다른 도구가 있는데

그리스어 대문자 Omega입니다

 

*네이버 : 그리스 자모의 맨 끝 글자. 대문자는 Ω, 소문자는 ω로 표기

 

Big-O의 반대라고 할 수 있습니다

Big-O는 알고리즘을 수행하는 데 필요한 시간의 상한선을 의미

서랍열기 선형 탐색의 경우 7개의 서랍 중 50을 찾기 위해 n번이 필요한 선형 탐색을 했다 O(n)이라고 표현

 = 최악의 경우에 필요한 상한선을 말함

 

Omega를 사용하면 최상의 경우를 나타낼 수 있다

서랍열기 선형 탐색의 경우 7개의 서랍 중 50을 찾기 위해 최악의 경우 n번 또는 7번의 과정이 필요함

최선의 경우는 한 번!

 

가운데 열고 나머지 중간찾기의 경우도 최소 1번 : 우연히 가운데에 찾는값이 있는 경우 1

 

알고리즘의 상한선도 있지만 운이 좋을 수도 있다

최선의 경우가 어디냐, 1이다. 그래서 그림에 나와있는 것처럼 리니어서치, 바이너리서치 둘다 1

 

이제 우리는 어떤 알고리즘이나 코드가 주어지는 입력값에 따라 얼마나 좋은지 파악할 수 있는 척도가 생겼다

 = Big-O와 Omega다.

 

학생질문1) Ω(n)의 예?

 : 서랍의 개수 세기

 

학생질문2) Big-O와 Omega 둘 중 어느 것이 좋아야 좋은 알고리즘?

 : Big-O

컴퓨터과학자가 가장 걱정하는 부분은 최악의 경우에 프로그램이 어떻게 동작할 지, 또는 평균적으로 어떻게 동작하는지 입니다.

Omega가 좋아서 좋은 경우도 있지만 그저그런 경우도 있다 : 이미 정렬된 입력값을 받아 이걸 매우 빠르게 정렬하는게 제일 빠른 경우일텐데 이게 뭐가 좋겠어 정렬된걸 정렬하는건데

 

Big-O와 상한선이 우리가 조금 더 신경 써볼 부분

 

=====================

3)선형 검색

찾고자 하는 자료를 검색하는 데 사용되는 다양한 알고리즘이 있습니다. 그 중 하나가 선형 검색입니다.

선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색합니다.

이렇게 하여 선형 검색은 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 합니다.

 

선형 검색 알고리즘은 정확하지만 아주 효율적이지 못한 방법입니다.

리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행됩니다.

여기서 최악의 상황은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우를 말합니다.

만약 100만 개의 원소가 있는 리스트라고 가정해본다면 효율성이 매우 떨어짐을 느낄 수 있습니다.

반대로 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우입니다.

평균적으로 선형 검색이 최악의 상황에서 종료되는 것에 가깝다고 가정할 수 있습니다.

선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용합니다.

이러한 경우 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적입니다.

  ▽왜?내가 어디쯤 했는지 쉽게 파악하니까?말곤 없는 것 같은데

이제 여러분은 왜 검색 이전에 정렬해줘야 하는지 알 수 있을 것입니다.

정렬은 시간이 오래 걸리고 공간을 더 차지합니다. 하지만 이 추가적인 과정을 진행하면 여러분이 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시간을 단축할 수 있을 것입니다.

 

===

직접해보자 numbers.c

#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;
}

이게 선형 탐색

 

*return 0과 return 1은 수업에선 안 썼고 네이버설명엔 있다

https://www.inflearn.com/questions/101423

꼭 return 0;을 써야하나요? - 인프런 | 질문 & 답변

∴ C99부턴 main에 return 0 안써도 된다

 

C에는 배열에 넣고 싶은 값을 미리 안다면 

int numbers[6] = { 4, 8, 15, 16, 23, 42 }; 이렇게 중괄호 안에 적으면 코드가 줄어든다

□배열을 정적으로 초기화 했다고 한다

https://92bluemoon.netlify.app/posts/dynamic-static/

동적 정적 프로그래밍 언어에서의 정리 - 푸른달 열나흘

동적 : 실행 시점 --아마 dynamic, 동적 테스트는 실행중인 상태에서의 테스트, 동적 웹페이지는 요청에 의해 데이터를 가공한 후 생성되는 웹페이지

정적 : 컴파일 시점 --아마 static, 정적 테스트는 실행되지 않은 상태에서 수행하는 것, 정적 웹페이지는 미리 저장된 파일이 그대로 전달됨

 

이제 배열을 순환해보자(for문 작성중)

찾으면 발견과

못찾으면 발견되지 않음이 있어야함 이 순서대로 찾는게 선형 탐색

 

===

이제 새로운거, 숫자가 아니라 이름 찾아보기 names.c

이렇게 만들면 제대로 동작안함. 왜일까요?

관계 연산자 ==는 문자열에 사용할 수 없다.

문자열은 // 문자, bool, 소수 혹은 정수와는 다릅니다

문자열 자체가 배열로, 여러개의 문자로 구성됨

 > 두 문자열을 비교하고 싶다면 문자열 속에 문자 하나씩을 비교해야함, 전체를 한번에 비교 못함

 

파이썬이나 자바같은 다른 프로그래밍 언어에서는 한줄로 비교가 가능

 

하지만 C는 모든 것이 로우 레벨로 진행됨, 문자열을 비교하기 위해 등호를 사용할 수 없다.

 

그냥 CS50에서 만들어준 함수 strcmp로 비교함, string.h에 있음,

같으면 0을 반환, 양수를 반환하면 첫번째 문자열이 알파벳 기준 큼, 음수면 반대의 경우

 

그렇게해서 이름과 번호를 둘다 해서 전화번호부 프로그램 phonebook.c을 만듦

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

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)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

저기 printf "Found 밑에 return 0; 을 해주면 찾으면 밑에 안하고 바로 나가서 printf Not found를 출력 안한다

□뭔가 일이 끝나면 반환을 해주면 된다.

에서의 '반환'을 직관에 새기기, ▽함수를 나가는거지 return이니까?

 

일반적으로 성공적이면 return 0, 아니면 return 1; 숫자에 의미 없고 관습임

 

전화번호는 어떤 자료형을 사용할까? -나 괄호도 있고 해외번호는 + 도 있으니 얘네는 숫자가 아니고 문자인데??

사실 숫자가 아니라 숫자처럼 보이는 문자열로 나타내는 것이 적합.

게다가 0부터 누르는 번호도 있는데 수학에서 맨 앞의 0은 생략됨

숫자처럼 보이지만 다른 요소들이 많다면 정수형으로 나타내는 것은 좋지 않다

 

찾으면 번호를 출력하게 한 것, %s와 numbers[i], 다른 배열이지만 같은 위치에 정보가 있다

 

▽numbers[i] 이거 문자열 배열중에 하나의 원소일 뿐인것 알지

 

분명 잘 작동해! 근데 개선할 부분이 있는지 찾아보기

거슬리는 부분은?

이름을 올바른 순서로 나열하고, 번호도 맞는 순서대로 나열했다고 가정하고 있습니다 이건 저만의 규칙에 불과

▽실수할 여지가 있는 부분이 있는게, 내가 신경 써서 정해줘야 한다 싶은게 개선할 여지네

 

- 4개보다 더 많이 있다면 모든 게 빠르게 엇나가기 시작함.

- 이름을 사전순으로 한다면 번호는 어떻게 정렬해야 할까?

 

===

C의 새로운 기능을 배울 기회, 다른 언어에서도 적용됨.

사람의 이름과 번호를 같이 저장하는 상황을 보기.

오늘 우리는 우리만의 자료형을 만들어 볼 것

 

typedef라는 새로운 키워드가 나옴. 새로운 타입을 정의한다는 말

구조체(struct)를 만드는데 이건 C에 미리 정의된 키워드로 마치 그릇처럼 여러 가지 자료형을 담을 수 있음.

여러가지 자료형을 위한 그릇(▽변수)임

 

typedef struct

{

    string name;

    string number;

}

person -- 구조체의 이름(자료형)을 정의하는 부분

 

그럼 이제 저걸로 배열을 만들면

자료형 변수명[] 니까

person people[4];가 됨

배열의 내용을 채우기 위해서는 이제

people[0].name = "EMMA"

people[0].number = "617-555-0100";

 

적어야 하는 양이 늘어날 지 모르지만 이제 모든 정보를 한 번에 묶어서 표현할 수 있다!

이제 이름순으로 정렬해도 이름과 번호의 관계(를 생기게 만든 것이니까)는 그대로 유지됨

 

===

저기 people[4].number때문에 에러남(그냥 잘못 쓴것임 1, 2, 3계속 늘리다보니 33 일 자리에 34를 쓴 것)

[]안에 들어가는 숫자가 배열의 인덱스, 예시문장)배열 인덱스로 주어진 4는 배열의 크기인 4를 초과한다

선생님이 [4]로 써놓음 0~3까지만 있는데 그래서 나온 문장, 인덱스 직관 세우라고

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

typedef struct
{
    string name;
    string number;
}
person;

int main(void)
{
    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";

    // 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;
}

 

===

이렇게 많은 관련 정보를 캡슐화하여 관리할 일이 많다! 

이것도 캡슐화구나 묶는것, 많은 관련 정보를 한 번에 관리하는 것

 

똑같이 중괄호를 쓸 수 있지만 이 경우에는 코드가 더 지저분해져서 굳이 하지 않았음, 가능!

 

내가 직접 적은 목록에서 EMMA를 찾는 프로그램인데, 동적이지 않다. 실제로는 GetString과 같은 함수를 사용해서 쓸모있는 프로그램이었을것(동적으로)