[모두를 위한 컴퓨터 과학 CS50 2019] 1.컴퓨팅 사고 - 3)알고리즘

boostcourse의

모두를 위한 컴퓨터 과학(CS50 2019) - David J. Malan (데이비드 J. 말란)

 

이번 강의에서는 생활코딩님의 WEB2-JavaScript 강의에서 배운 내용들이 많이 포함되어 있네요.

추가적으로 알고리즘을 공부해야 할 필요성을 느끼게 해주셨습니드아...

---

www.boostcourse.org/cs112

---

1. 컴퓨팅 사고 Computational Thinking, Scratch

3)알고리즘

 

알고리즘 algorithms

 

저번 강의에서 숫자, 글자, 색깔, 사진 등을 컴퓨터가 이해할 수 있는 2진법으로 표현한다는 것을 배웠다.

이것이 입력 input 에 해당한다.

그렇다면 이번 강의에서는 출력 output 에 대해 알려주셨다.

어떻게 입력 input 에서 출력 output 을 얻을 수 있을까?

컴퓨팅은 입력을 받아 그 입력을 처리한 후 출력하는 과정이다. 

알고리즘은 입력 input 에서 받은 자료를 출력 output 형태로 만드는 처리 과정을 뜻한다.

알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열이다. 이러한 일련의 순서적 규칙들을 어떻게 나열하는지에 따라 알고리즘의 종류가 달라진다. 같은 출력값이라도 알고리즘에 따라 출력을 하기까지의 시간이 다를 수 있다. 

 

정확하기만한 알고리즘

 

강의에서 교수님이 예시를 들어주셨다. 전화번호부에서 한 사람을 찾는 것이다. 

예를 들어 한 전화번호부에서 livebyfaith117을 찾는 것이다. 

가장 단순한 방법은 전화번호부를 들어 첫 페이지부터 한장 씩 넘기며 livebyfaith117가 해당 페이지에 있는지 찾는다. 없으면 그 다음 페이지에서 찾는다. livebyfaith117을 찾을 때까지 혹은 전화번호부가 끝날 때까지 이것을 반복할 것이다. 하지만 언젠가는 livebyfaith117이 전화번호부에 있다면 찾을 수 있을 것이다. 

 

알고리즘을 평가할 때는 정확성도 중요하지만, 효율성도 중요하다.

효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것이다. 

위의 작업을 완료하기까지 한 번에 한 페이지씩 보는 정확하지만 매우 오래걸리고 비효율적인 알고리즘이다. 

그렇다고 두장씩 넘길 수는 없지 않은가? 효율성을 따진다고 정확성을 놓칠 수도 없는 법.

 

정확하고 효율적인 알고리즘

 

직관적이고 효율적인 알고리즘을 적용하여 livebyfaith117을 찾아보자. 

먼저, 전화번호부 가운데를 편다. 만약 livebyfaith117이 해당 페이지에 있다면 알고리즘은 끝난다. 없다면 가운데를 편 앞부분이나 뒷부분에 있는지 이름순 정렬에 따라 알 수 있다. 이렇게 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 똑같은 알고리즘을 또 수행한다. 이 알고리즘을 전화번호부 한 페이지가 남을 때까지 계속 수행한다. 

이 알고리즘은 정확하기만한 알고리즘보다 더 효율적이다.

 

1024장짜리 전화번호부를 한장한장씩 넘기는 알고리즘,

단 한번의 동작으로 512장, 256장, 128장 ... 사라지는 알고리즘.

 

위에서본 알고리즘 정의를 다시 보자.

알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열.

 

의사코드

 

위와 같은 알고리즘은 의사코드 라는 방식으로 보다 명료하게 정리 할 수 있다.

의사코드는 필요한 행동이나 조건을 잘 설정하여 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있게 도와준다.

    Pick up phone book
    Open to middle of phone book
    Look at page
    If Smith is on page
    	Call Mike
    Else if Smith is earlier in book
    	Open to middle of left half of book
        Go back to line 3
    Else if Smith is later in book
    	Open to middle of right half of book
        Go back to line 3
    Else
    	Quit

1.전화번호부를 집어 든다

2.전화번호부의 중간을 편다

3.페이지를 본다

4.만약 Mike Smith가 페이지에 있으면

5.    Mike Smith에게 전화한다.

6.그렇지 않고 만약 Mike Smith가 앞 페이지에 있으면

7.    앞 페이지의 절반을 편다

8.    3번째 줄부터 다시 실행한다

9.그렇지 않고 만약 Mike Smith가 뒷 페이지에 있으면

10.   뒷 페이지의 절반을 편다

11.   3번째 줄부터 다시 실행한다

12.그러지 않으면

13.   그만둔다

---

    Pick up phone book
    Open to middle of phone book
    Look at page
    If Smith is on page
     Call Mike
    Else if Smith is earlier in book
     Open to middle of left half of book
        Go back to line 3
    Else if Smith is later in book
     Open to middle of right half of book
        Go back to line 3
    Else
     Quit

 

빨간색으로 강조된 부분들은 함수(functions)라고 부른다.

함수는 컴퓨터에게 이 경우에는 사람에게 무엇을 할지 알려주는 동사와 같다.

---

    Pick up phone book
    Open to middle of phone book
    Look at page
    If Smith is on page
     Call Mike
    Else if Smith is earlier in book
     Open to middle of left half of book
        Go back to line 3
    Else if Smith is later in book
     Open to middle of right half of book
        Go back to line 3
    Else
     Quit

 

주황색으로 강조된 부분들은 조건이라고 부른다.

이것은 여러 선택지 중 하나를 고르는 것이다.

---

    Pick up phone book
    Open to middle of phone book
    Look at page
    If Smith is on page
     Call Mike
    Else if Smith is earlier in book
     Open to middle of left half of book
        Go back to line 3
    Else if Smith is later in book
     Open to middle of right half of book
        Go back to line 3
    Else
     Quit

 

앞서 말한 결정을 내리기 위한 질문이 필요하다. 이것을 불리언(boolean)이라고 한다.

(생활코딩에서 조건문)

답이 yes 또는 no, true 또는 false 로 나오며 2진법에서 0 또는 1로 나오는 질문을 뜻한다.

---

   Pick up phone book
    Open to middle of phone book
    Look at page
    If Smith is on page
     Call Mike
    Else if Smith is earlier in book
     Open to middle of left half of book
        Go back to line 3
    Else if Smith is later in book
     Open to middle of right half of book
        Go back to line 3
    Else
     Quit

마지막으로 강조된 부분은 루프(loop)라고 한다.
(생활코딩에서 반복문)

이것은 뭔가를 계속해서 반복하는 순환이다.