[CS50] 알고리즘

알고리즘이란?

수학, 컴퓨터과학, 언어학 또는 역인 분야에서 어떠한 문제를 풀어 맺기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것이라고 합니다.(출처 : 위키백과)

 

컴퓨터가 자신이 입력받은 정보를 어떻게 가공해서 출력하는 방식에 대해 생각해보면

컴퓨터는 순서대로 필요한 동작을 하면서 문제를 처리하는데 이를 알고리즘이라고 컴퓨터과학에서는 말합니다.

 

그렇다면 이 알고리즘을 어떻게 정의가 가능하고, 그 정확성과 효율성은 어떨까요?

 

전에 2진법을 공부할때 input(입력) output(출력)에 대해 공부했었는데요

input에 해당하는 숫자, 글자, 색깔 등 컴퓨터가 이해할 수 있는 2진법으로 표현하는 것을 배웠습니다.

그렇다면 output은 어떻까요?

output은 input된 내용(자료)을 처리하고 그 내용을 출력합니다.

이때 알고리즘이 input에서 받은 내용을 output형태로 만드는 처리과정을 의미합니다.

이런그림이 나오는데 전에 CS라고 공부했던 부분입니다.

즉 알고리즘이란 쉽게 표현해보자면 입력값을 출력 값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열이라고 할 수 있습니다.

(위의 규칙을 어떻게 나열하는지에 따라서 알고리즘의 종류가 달라집니다.)

 

알고리즘을 평가할 땐 정확성도 중요하지만 효율성도 중요합니다.

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

 

예를 들어볼까요?

1000페이지의 전화번호부에서 Mike라는 사람을 찾는다고 가정해봅시다.

전화번호부에서 맨 처음부터 찾으려면 굉장히 오랜 시간이 걸리겠죠?

하지만 절반씩 나눠버린다면 어떻게 될까요? 처음엔 500페이지를 펴서 앞, 뒤페이지 중 Mike가 없는 페이지는 버립니다. 이렇게 절반씩 버리고 나면 마지막 페이지에는 Mike가 있거나 없거나 둘 중 하나일 겁니다.

이렇게 찾으면 앞에서부터 1000페이지의 전화번호부를 찾는 거보다 효율적으로 찾을 수 있게 됩니다.

 

이러한 알고리즘은 의사 코드라는 방식으로 보다 명료하게 정리할 수 있는데요

 

의사 코드란?

필요한 행동이나 조건들을 잘 설정하여 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있게 도와주는 걸 말합니다.

여기서 들여쓰기 부분은 종속관계를 설명합니다.

앞서 말한 알고리즘의 예시를 코드로 가져와봤는데요

여기서 보면 Pick up이나 Look 등 어떠한 행동을 해야 할지 알려주는 부분이 있죠?

이러한 부분들을 컴퓨터에서는 함수(function)이라고 부릅니다.

다음으론 IF나 Else if 같은 부분들은 여러 선택지 중 하나를 고른다고 할 수 있는데

이러한 부분들을 조건이라고 부릅니다.

또 조건이 나왔을 땐 결정을 내리기 위한 질문이 필요한데, 답이 참(true) 또는 거짓(false) (2진법에서 0 또는 1)이 나오는 질문들을 말합니다.

이것을 불리언(Boolean)이라고 합니다.

마지막으로  반복되는 부분은 똑같은 함수를 계속 써주는 건 너무 번거롭겠죠.. 코드가 깨끗하지도 않을 거고요...

그래서 루프(Loop)라는 것을 만들어 계속해서 순환하는 코드를 만들어줍니다.

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.