[CS50 2019] (컴퓨팅 사고) 알고리즘

이전 강의에서는 이진법으로 컴퓨터에 정보를 표현하는 방식을 배웠다. 그 중에서도 문자나 색상을 표현하는 방식을 알아 보았다. 이번에는 이러한 정보를 어떠한 논리적인 과정을 통해 필요한 정보로 가공되는지 알아 보자.

[CS50 2019] (컴퓨팅 사고) 정보의 표현

 

📌 알고리즘(Algorithm)

알고리즘은 문제를 해결하기 위해 설계한 논리 과정이다.

In a concept of problem solving, algorithm is just a step by step instructions for solving some problem.
문제 해결의 관점에서 바라 보면, 알고리즘은 그저 문제를 해결하는 단계적 방법일 뿐이다.

알고리즘은 문제를 해결하는 단계적 방법이다

What Is An Algorithm? Characteristics, Types and How to write it | Simplilearn

 

A lot of problem solving really, as we will find, is just about harnessing your existing intuition and comfort with ideas  that now you just need to translate in such a way that machines and other humans can understand.
곧 알아 보겠지만, 수많은 문제 해결은 여러분이 갖고 있는 직관이나 생각을 이용해서 기계나 다른 사람들이 이해할 수 있는 방식으로 번역하는 것에 불과하다.

 

📌 효율성: 선형 탐색 vs 이진 탐색

그렇다면 어떠한 방식의 알고리즘이 가장 효율적일까? 효율적이라는 것을 어떻게 객관적으로 설명할 수 있을까? 전화번호부에서 한글 ‘앤디’를 찾는 것을 떠올려 보자. 

전화번호부에서 원하는 단어를 어떻게 찾을까?

 

여러 방법이 있겠지만 크게 가나다순으로 찾거나 절반씩 펼쳐가면서 찾는 방식이 있을 것이다. 전자를 선형 탐색(linear search), 후자를 이진 탐색(binary search)라 한다.

• 전화번호부 이름의 개수 $n$이라 해 보자.
• 선형 탐색은 최악의 경우에 처음부터 끝까지 한 쪽씩 $n$을 찾아가야 하지만,
• 이진 탐색은 최악의 경우에 $\log_2{n}$으로 점차 줄어든다.
• 선형 탐색을 두 쪽씩으로 찾아 $2n$으로 개선해도 이진 탐색과의 격차를 줄이기에는 턱없이 부족하다.
• 데이터가 많아질수록 둘의 격차는 기하급수적으로 늘어날 것이다.

선형 탐색과 이진 탐색의 효율성에 대한 그래프

 

📌 의사 코드(Pseudo Code)

'의사 코드(疑似 code)'란 어떠한 알고리즘의 단계를 쉽게 이해할 수 있도록 사람의 언어로 표현한 코드이다.

 

다시 전화번호부에서 ‘앤디’를 찾아 보자. 앤디를 찾는 이진 탐색에 대한 의사코드 알고리즘은 아래와 같다.

전화번호부를 손으로 쥔다
전화번호부의 가운데를 펼친다
해당 페이지를 본다
첫 경우로 앤디가 페이지에 있으면
    앤디한테 전화를 건다
다른 경우로 앤디가 책 앞쪽에 있으면
    책의 왼쪽 절반의 가운데를 펼친다
    3번 줄로 돌아간다
다른 경우로 앤디가 책 뒤쪽에 있으면
    책의 오른쪽 절반의 가운데를 펼친다
    3번 줄로 돌아간다
마지막 경우로
    끝낸다

1. 함수(function)

여기서 함수는 어떠한 논리적 행위를 하는 것을 의미한다. 위의 코드 블럭에서 ‘~ㄴ다’로 끝나는 것들이 함수에 해당한다.

• 쥔다
• 펼친다
• 본다
• 전화를 건다
• 끝낸다

2. 조건(condition)

‘~ 경우로’로 시작하는 것들은 조건이다.

• 첫 경우로
• 다른 경우로
• 마지막 경우로

3. 불리언(boolean)

불리언은 조건에서 참 또는 거짓에 해당하는 논리적인 사실을 의미한다. 또는 참과 거짓을 이진법으로 각각 1과 0으로 나타낼 수도 있다.

• 앤디가 페이지에 있으면
• 앤디가 책 앞쪽에 있으면
• 앤디가 책 뒤쪽에 있으면

4. 반복문(loop)

루프는 어떠한 조건으로 되돌아가서 특정 함수나 조건을 반복하는 것을 의미한다.

• 3번 줄로 돌아간다.