What's an algorithm? - David J. Malan

여러분의 뇌는 알고리즘을 풀 수 있습니다 - 데이비드 J. 말란 (David J. Malan)

Translator: Andrea McDonough Reviewer: Jessica Ruby

번역: Junbum Lee 검토: Jungmin Naomi Lee

What's an algorithm?

알고리즘이란 무엇일까요?

In computer science,

컴퓨터공학에서

an algorithm is a set of instructions

알고리즘이란 순서대로 문제를 풀기 위한

for solving some problem, step-by-step.

지시 절차의 모음입니다.

Typically, algorithms are executed by computers,

일반적으로 알고리즘은 컴퓨터에 의해 실행됩니다.

but we humans have algorithms as well.

하지만 우리 인간도 알고리즘을 갖고 있습니다.

For instance, how would you go about counting

예를 들어,

the number of people in a room?

방에 있는 사람들의 수를 어떻게 세나요?

Well, if you're like me,

음, 만약에 여러분이 저와 같다면

you probably point at each person,

여러분은 아마도 각각의 사람들 가리키며

one at a time,

한 번에 한 명씩,

and count up from 0:

0부터 세기 시작할 것입니다.

1, 2, 3, 4 and so forth.

1,2,3,4...처럼요.

Well, that's an algorithm.

음, 이게 바로 알고리즘입니다.

In fact, let's try to express it

자, 이제 조금 더 공식적으로

a bit more formally in pseudocode,

유사 부호에 관해 이야기 해볼게요.

English-like syntax

that resembles a programming language.

유사 부호는 프로그래밍 언어와 유사한

영어와 같은 문법 언어입니다.

Let n equal 0.

n을 0과 같다고 둬봅시다.

For each person in room, set n = n + 1.

방 안에 있는 각각의 사람에 대해 n=n+1이라 설정합니다.

How to interpret this pseudocode?

어떻게 이 기호를 해석할까요?

Well, line 1 declares, so to speak,

첫 줄이 나타내는 것을 보면

a variable called n

n이라 불리는 변수를 정하고

and initializes its value to zero.

그 초기값을 0으로 설정합니다.

This just means that at the beginning of our algorithm,

이는 이 알고리즘에서

the thing with which we're counting

우리가 처음으로 셀 것은

has a value of zero.

0의 값을 갖고 있다는 겁니다.

After all, before we start counting,

결국, 숫자를 세기 전에는

we haven't counted anything yet.

아직 아무것도 세지 않은 셈이지요.

Calling this variable n is just a convention.

이 변수를 n이라 부르는 것은 관례일 뿐입니다.

I could have called it almost anything.

이것은 어떤 다른 것으로도 부를 수 있습니다.

Now, line 2 demarks the start of loop,

두 번째 줄은 루프(순환)의 시작을 나타내는데

a sequence of steps that will repeat some number of times.

루프(순환)란 연속적인 절차를 여러 번 반복하는 것입니다.

So, in our example, the step we're taking

그래서, 위의 예시에서, 우리가 택하는 단계는

is counting people in the room.

방 안의 사람을 세는 것이지요.

Beneath line 2 is line 3,

둘 째 줄 밑에 세 번째 줄이 있는데

which describes exactly how we'll go about counting.

이것이 우리가 수를 어떻게 세어 나갈 것인지 정확히 설명해줍니다.

The indentation implies that it's line 3

이 들여쓰기는 세 번째 줄이

that will repeat.

반복될 것임을 의미하지요.

So, what the pseudocode is saying

따라서 이 유사 부호가 의미하는 바는

is that after starting at zero,

0에서 시작하여

for each person in the room,

방 안에 있는 각각의 사람들에 대하여

we'll increase n by 1.

n을 1씩 증가시킨다는 것이지요.

Now, is this algorithm correct?

이 알고리즘은 정확한가요?

Well, let's bang on it a bit.

자, 계속 탐구해 봅시다.

Does it work if there are 2 people in the room?

방에 두 사람이 있을 때에도 이 알고리즘이 적용될까요?

Let's see.

한 번 봅시다.

In line 1, we initialize n to zero.

첫 줄에서 n을 0으로 두고

For each of these two people,

두 사람 각각에 대해

we then increment n by 1.

n을 1씩 증가시킵니다.

So, in the first trip through the loop,

순환 고리의 첫 번째 과정에서

we update n from zero to 1,

우리는 n을 0에서 1로 업데이트 하지요.

on the second trip through that same loop,

같은 순환의 두 번째 과정에서

we update n from 1 to 2.

우리는 n을 1에서 2로 업데이트합니다.

And so, by this algorithm's end, n is 2,

그래서 이 알고리즘의 마지막 값은 n=2가 됩니다.

which indeed matches the number of people in the room.

이 숫자 2는 방 안의 사람의 수와 일치합니다.

So far, so good.

지금까지는 괜찮지요.

How about a corner case, though?

그렇다면 특이한 경우라면 어떤가요?

Suppose that there are zero people in the room,

방 안에 한 사람도 없다고 가정해봅시다.

besides me, who's doing the counting.

수를 세는 저를 제외하고요.

In line 1, we again initialize n to zero.

첫 줄에서 n을 역시 0으로 시작합니다.

This time, though, line 3 doesn't execute at all

이번에는, 세 번째 줄이 전혀 실행되지 않아요.

since there isn't a person in the room,

이는 방 안에 사람이 아무도 없어서

and so, n remains zero,

n은 여전히 0으로 남아있기 때문이지요.

which indeed matches the number of people in the room.

0은 방 안의 사람 수와 여전히 정확히 일치합니다.

Pretty simple, right?

꽤 간단합니다. 그렇죠?

But counting people one a time is pretty inefficient, too, no?

하지만, 한 번에 한 명씩 세어나가는 것은 꽤 비효율적이지요?

Surely, we can do better!

물론, 좀 더 나은 방법이 있습니다!

Why not count two people at a time?

한 번에 두 명씩 세어 보는건 어떤가요?

Instead of counting 1, 2, 3, 4, 5, 6, 7, 8, and so forth,

1,2,3,4,5,6,7.8.... 이렇게 세는 것 대신에

why not count

이렇게는 어때요?

2, 4, 6, 8, and so on?

2,4,6,8...등 으로요.

It even sounds faster, and it surely is.

언뜻 보기에도 훨씬 빨라보이는데, 확실히 빠릅니다.

Let's express this optimization in pseudocode.

그럼 이 최적화를 유사 부호로 나타내 볼까요?

Let n equal zero.

n을 0이라 둡시다.

For each pair of people in room,

방 안에 있는 사람들 각각의 쌍에 대하여

set n = n + 2.

n = n+2로 설정합니다.

Pretty simple change, right?

꽤 단순한 변화네요. 그렇죠?

Rather than count people one at a time,

한 번에 한 명을 세는 것 대신에

we instead count them two at a time.

한 번에 두 명씩 세어 보겠습니다.

This algorithm's thus twice as fast as the last.

따라서 이 알고리즘은 이전 것보다 두 배나 빠르네요.

But is it correct?

하지만, 이게 정확할까요?

Let's see.

한 번 봅시다.

Does it work if there are 2 people in the room?

만약 방 안에 두 사람이 있다면 이 알고리즘이 적용될까요?

In line 1, we initialize n to zero.

첫 줄에서 n을 0이라 둡시다.

For that one pair of people, we then increment n by 2.

한 쌍(두 명)의 사람들이므로 n을 2씩 증가시켰습니다.

And so, by this algorithm's end, n is 2,

결과적으로 이 알고리즘의 마지막 값은

which indeed matches the number of people in the room.

n=2가 되고 이것은 방 안의 사람 수와 일치하네요.

Suppose next that there are zero people in the room.

다음으로 방 안에 사람이 한 명도 없다고 가정해 봅시다.

In line 1, we initialize n to zero.

첫 줄에서 n을 0으로 둡시다.

As before, line 3 doesn't execute at all

그래서 세 번째 줄은 전혀 실행되지 않습니다.

since there aren't any pairs of people in the room,

방 안에 남은 사람이 없어서

and so, n remains zero,

n은 여전히 0으로 남기 때문이지요.

which indeed matches the number of people in the room.

여전히 방 안의 사람 수와 같군요.

But what if there are 3 people in the room?

그런데 방 안에 3명의 사람이 있으면 어떻게 될까요?

How does this algorithm fair?

이 알고리즘은 적용될까요?

Let's see.

살펴 봅시다.

In line 1, we initialize n to zero.

첫 줄을 n을 0으로 시작합니다.

For a pair of those people,

한 쌍의 사람들에 대해

we then increment n by 2,

n을 2만큼 증가시킵니다.

but then what?

하지만 그 다음은요?

There isn't another full pair of people in the room,

방 안에 또 다른 한 쌍(두 명)의 사람이 없기 때문에,

so line 2 no longer applies.

더이상 두 번째 줄은 적용될 수 없지요.

And so, by this algorithm's end,

그래서 이 알고리즘의 마지막 값인

n is still 2, which isn't correct.

n은 여전히 2가 됩니다. 즉, 방 안의 사람 수와는 같지 않게 되네요.

Indeed this algorithm is said to be buggy

사실, 이 알고리즘에는 결함이 있습니다.

because it has a mistake.

왜냐하면 실수가 있었기 때문이지요.

Let's redress with some new pseudocode.

그럼, 새로운 유사 코드로 바로 잡아봅시다.

Let n equal zero.

n을 0으로 놓고

For each pair of people in room,

방 안에 있는 사람 한 쌍에 대해

set n = n + 2.

n = n+2로 둡시다.

If 1 person remains unpaired,

만약에 쌍을 이루지 못한 한 사람이 남으면,

set n = n + 1.

n을 n+1로 설정합니다.

To solve this particular problem,

이 특정한 문제를 해결하기 위해

we've introduced in line 4 a condition,

네 번째 줄에 하나의 조건을 도입했습니다.

otherwise known as a branch,

다른 표현으로 곁가지(branch)라고 하는데,

that only executes if there is one person

쌍을 이루지 못한 한 사람이 있을 때에만 실행되는

we could not pair with another.

조건이지요.

So now, whether there's 1 or 3

그럼 이제, 1명이 있든 3명이 있든,

or any odd number of people in the room,

혹은 다른 홀수의 사람들이 있든,

this algorithm will now count them.

이 알고리즘은 그 사람들을 셀 수 있을 것입니다.

Can we do even better?

좀 더 낫게 만들 수 있을까요?

Well, we could count in 3's or 4's or even 5's and 10's,

글쎄요, 우리는 3, 4, 5, 10의 배수로 셀 수 있을 것입니다.

but beyond that it's going to get

하지만, 그 이상의 수로는

a little bit difficult to point.

숫자를 세기에 약간 힘든 점이 있지요.

At the end of the day,

결국 가장 중요한 것은

whether executed by computers or humans,

컴퓨터나 사람에 의해 알고리즘이 실행되면

algorithms are just a set of instructions

알고리즘은 단지

with which to solve problems.

문제를 풀기 위한 지시의 모임이라는 것입니다.

These were just three.

이는 단지 세 가지 뿐이지요.

What problem would you solve with an algorithm?

여러분은 알고리즘으로 어떤 문제를 해결하고 싶으신가요?