[컴퓨팅 사고] 알고리즘

CS50 - David J. Malan (데이비드 J. 말란)

 

학습 목표

1. 우리가 일상 생활에서 하는 일들을 컴퓨터가 이해할 수 있는 알고리즘으로 표현할 수 있다.
2. 효율적인 알고리즘에 대해 설명할 수 있다.

 

1. 알고리즘?

컴퓨터는 2진법으로 데이터를 표현한다.
0과 1을 가지고 숫자, 문자, 사진, 영상, 음악 등을 표현하고 저장하는데, 이것은 input에 해당한다.

컴퓨터 과학을 설명하면서 컴퓨터 과학은 문제 해결에 대한 학문이라고 했다.

input -> 컴퓨터 과학 -> output

• input을 전달받아 output을 만들어내는 것에 대한 학문

그렇다면 전달받은 input을 어떻게 처리해서 output을 낼까?
알고리즘은 input에서 받은 데이터를 output 형태로 만드는 처리 과정을 뜻한다.

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

같은 input을 전달받아 output으로 만드는 데 사용한 알고리즘의 종류에 따라 ouput으로 나오기까지의 시간이 달라진다.

 

2. 알고리즘 종류

2.1. 정확한 알고리즘

예를 들어, 전화번호부에서 Jane 을 찾아야 한다고 가정하자.
전화번호부를 첫 장부터 마지막 장까지 한 페이지씩 넘기면서 찾아보자.
Jane을 찾을 때까지 페이지를 넘긴다. 만약 이 전화번호부에 Jane의 연락처가 있다면 마지막 페이지까지 넘겼을 때 Jane을 찾을 수 있다. 시간이 얼마가 걸릴지는 모르지만 그래도 언젠가는 찾을 수 있다.

이런 알고리즘은 정확하긴 하겠지만 효율이 너무 떨어진다.
정확하면서 효율적인 알고리즘을 살펴보자.

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

다시 Jane을 찾아보자.
이번에는 전화번호부를 딱 반으로 나눠서 그 페이지에 Jane이 있는지 보자. 운 좋게도 Jane이 있다면 알고리즘은 끝이 난다.
Jane이 그 페이지에 없다해도 전화번호부는 알파벳 순이라 우리는 전화번호부에서 Jane을 앞페이지에서 찾을지 뒷페이지에서 찾을지 판단 할 수 있다.
앞/뒤를 결정했으면 이제 쓸모없는 페이지 절반은 버린다.
이런 식으로 계속 절반을 나눠서 찾고 필요 없는 쪽은 버리는 걸 반복하다보면 한 페이지가 남게 된다.
그 페이지에는 Jane이 있거나 없거나 둘 중 하나이다.