1. 우리가 일상 생활에서 하는 일들을 컴퓨터가 이해할 수 있는 알고리즘으로 표현할 수 있습니다.
2. 효율적인 알고리즘에 대해 설명할 수 있습니다.
3. 스크래치를 이용하여 간단한 알고리즘을 구현할 수 있습니다.

boostcourse의 모두를 위한 컴퓨터 과학 (CS50 2019) 강의를 듣고 정리한 필기입니다. 😀

1. 알고리즘

1.1 알고리즘이란,

입력으로부터 출력을 어떻게 얻을 수 있을까. 이런 과정을 설명하는데에는 다른 무엇보다 고등학교 때 배웠던 함수를 이용하면 쉽다. 입력값이 함수를 거치고 나면 고정된 값을 출력한다. 함수는 입력(input)→함수→출력(output)의 과정으로 이루어져 있다.

컴퓨터에서는 함수 대신 알고리즘이라는 말을 사용할 뿐, 원리는 완전히 똑같이 보면 된다. 문제 해결 관점에서 보면 알고리즘은 문제를 해결하는 단계적인 방법에 불과하다. 즉, 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열이라는 것이다.

알고리즘은 정확도와 효율성을 가지고 평가할 수 있다. (효율성이란, 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것 ) 그렇다면 우리는 문제를 해결하기 위해서는 어떤 알고리즘을 활용해야 할까?

예를 들어 스마트폰에 저장된 번호를 찾을 때 우리는 이름을 입력하거나 스크롤을 내린다. 그렇다면 스마트폰 내부에서는 어떻게 사용자가 원하는 번호를 찾을까? 이것을 이해하기 위해서 우리에게 전화번호부가 있다고 하자. A부터 Z까지 순차적으로 정리된 전화번호부 말이다.

• 첫 번째 방법 : River라는 이름을 찾기 위해서는 한 장 한 장 넘기면서 해당 페이지에 이름이 있는지 없는지를 확인할 것이다. 이것이 알고리즘이다. 이 방법은 비효율적인 알고리즘이다.
• 두 번째 방법 : 우리는 어떤 알고리즘을 활용해야 할까? 두 장씩 넘기는 방법? 이 방법도 River를 그냥 지나칠 수 있기 때문에 효율적인 방법은 아니다.
• 세 번째 방법 : 페이지를 절반씩 넘겨서 확인하는 방법이다. 예를 들어 전화번호부의 페이지가 200페이지라고 하자. 먼저 100페이지를 펴서 R보다 뒤로 있는 알파벳 이름인지, 앞에 있는 이름인지를 확인한다. 뒤에 있는 알파벳 이름이면 앞장은 더는 볼 필요가 없다. 그럼 우리에게는 100페이지가 남는다. 다시 50페이지를 펴서 R보다 뒤에 있는 이름인지, 아닌지를 확인한다. 이것을 반복하다 보면 첫 번째, 두 번째 방법보다 빠르게 찾을 수 있을 것이다.

1.2 의사코드(pseudocode)

의사코드는 컴퓨터가 수행해야하는 프로그램을 작성할 때 각 행동이 작동하는 논리를 표현하기 위한 언어이다. 세 번째 방법에 대한 의사코드는 아래와 같다.

여기서 C, Python, Javascript 등과 같은 언어에서 볼 수 있는 공통점이 있다. 밑에 노랗게 칠한 부분이 함수이다. 함수를 행동을 정의한 동사와 같다.

이번에 칠해진 부분은 조건이라고 부른다. 선택지라고 보면 된다.

이것은 불리언(Boolean)이라고 부른다. True 혹은 False로 나오는 부분이다. (이 페이지에 Smith가 있어? 응 혹은 아닝으로 답)

여기서 강조된 부분은 루프라고 한다. 적혀있는 문장을 반복하는 것이다.

2. 스크레치 : 기초

스크레치는 그래픽 프로그래밍 언어의 일환으로 긴 줄글보다는 강의를 듣는 것이 더 유용하기 때문에 링크를 두고 오늘의 TIL을 끝내겠다.