The Chasm | Think Like A Coder, Ep 6

번역: Soyun Cho 검토: Eunice Yunjung Nam

Ethic, Hedge, and Octavia stand on the edge of a bottomless ravine.

에틱, 헤지와 옥타비아는 끝이 보이지 않는 협곡에 서 있습니다.

It’s the only thing between them and the tower

타워에 가기 전에 이곳만 지나면

that houses the second of three powerful artifacts.

세 가지 유물 중 두 번째 유물이 완성됩니다.

They’ve got a brief window of time to get across before the guards return.

경비 로봇이 돌아오기 전까지 빠르게 길을 건너야 합니다.

With Hedge’s fuel gauge on empty he won’t be able to fly Ethic across,

헤지의 연료가 바닥나서 에틱을 비행시켜줄 수 없습니다.

so the only option is to make a bridge.

다리 건설이 유일한 해결책입니다.

Fortunately, the floating stacks of stones nearby are bridge components—

다행히, 주변에 떠 있는 돌무더기로 다리를 지을 수 있습니다.

invented by Octavia herself— called hover-blocks.

옥타비아가 개발한 호버블록이죠.

Activate a pile with a burst of energy,

에너지를 방출해 블록 더미를 활성화하면,

and they’ll self-assemble to span the ravine as Ethic walks across.

자동으로 조립되어 에틱이 건널 수 있게 협곡을 이어줍니다.

But there is, of course, a catch.

하지만 물론 문제점도 있습니다.

The hover-blocks are only stable when they’re perfectly palindromic.

호버블록은 완벽한 회문형일 때만 안정적인 상태를 유지합니다.

Meaning they have to form a sequence

즉, 동일한 배열 순서로 이뤄져야 합니다.

that’s the same when viewed forwards and backwards.

앞이나 뒤 어느 쪽에서 보아도요.

The stacks start in random orders,

이 더미는 처음에는 무작위로 놓이지만

but will always put themselves into a palindromic configuration

항상 회문형으로 재배치됩니다.

if they can.

가능할 때만요.

If they get to a point where a palindrome isn’t possible,

회문형 배열이 불가능할 때에는

the bridge will collapse,

다리가 붕괴합니다.

and whoever’s on it will fall into the ravine.

다리 위를 건너던 모든 이들이 협곡 아래로 추락할 것입니다.

Let’s look at an example.

예를 살펴볼까요.

This stack would make itself stable.

안정적인 상태를 유지하는 더미입니다.

First the A blocks hold themselves in place.

A블록이 먼저 양 끝에 위치합니다.

Then the B’s.

그 옆에 B블록이 붙습니다.

And finally the C would nestle right between the B’s.

마지막으로 그 사이에 C블록이 쏙 들어갑니다.

However, suppose there was one more A.

하지만, A블록이 한 개 더 있다고 가정해봅시다.

First two A blocks form up, then two B’s,

일단 양쪽에 A블록과 B블록이 차례로 하나씩 자리합니다.

but now the remaining C and A have nowhere to go,

하지만 남은 C블록과 A블록이 위치할 곳을 찾지 못하므로,

so the whole thing falls apart.

모든 블록이 무너집니다.

The Node of Power enables Hedge to energize a single stack of blocks.

헤지는 노드의 힘으로 블록 한더미를 활성화할 수 있습니다.

What instructions can Ethic give Hedge to allow him to efficiently find

에틱이 헤지에게 어떤 조언을 해서

and power a stable palindromic stack?

안정적인 회문형 구조를 알아내고 유지하도록 하게 할까요?

Pause now to figure it out for yourself.

잠시 멈추고 스스로 해결해보세요.

Examples of palindromes include ANNA, RACECAR, and MADAM IM ADAM.

예로는 ANNA, RACECAR, MADAM IM ADAM가 있습니다.

Counting the number of times a given letter appears in a palindrome

각각의 알파벳의 수를 세보면

will reveal a helpful pattern.

힌트가 되는 패턴을 알 수 있습니다.

Pause now to figure it out for yourself.

잠시 멈추고 스스로 해결해보세요.

Let’s first look at a naïve solution to this problem.

일단 단순한 해결법을 살펴봅니다.

A naïve solution is a simple, brute-force approach that isn’t optimized—

단순한 해결책은 간단하지만 비효율적인 억지스러운 접근법입니다.

but will get the job done.

하지만 해결이 되긴 합니다.

Naïve solutions are helpful ways to analyze problems,

단순한 해결책들은 문제를 분석하기에 용이한 방식이며

and work as stepping stones to better solutions.

더 좋은 해결책을 찾을 수 있는 초석이 되어줍니다.

In this case, a naïve solution is to approach a pile of blocks,

이 문제의 단순한 해결법은 블록 더미에 가서

try all the arrangements,

모든 조합을 구성한 후에

and see if one is a palindrome by reading it forward and then backwards.

그대로 혹은 역순으로 읽어보고 회문형인지 일일이 살펴보는 것입니다.

The problem with this approach

이 방식의 문제점은

is that it would take a tremendous amount of time.

시간이 너무 오래 걸린다는 점입니다.

If Hedge tried one combination every second,

헤지가 1초마다 1개의 조합을 구성한다고 가정하면,

a stack of just 10 different blocks would take him 42 days to exhaust.

10개의 블록 더미를 조합해 보는데 꼬박 42일이 걸립니다.

That’s because the total time is a function of the factorial

전체 시간은 블록 개수의

of the number of blocks there are.

계승 값과 동일하기 때문입니다.

10 blocks have over 3 million combinations.

10개의 블록으로 3백만 개 이상의 조합법이 가능합니다.

What this naïve solution shows is that we need a much faster way

이 단순한 해결책을 보니 훨씬 빠른 다른 방식으로

to tell whether a pile of blocks can form a palindrome.

회문형 여부를 판단해야 한다는 것을 알 수 있습니다.

To start, it may be intuitively clear that a pile of all different blocks

일단은, 겹치는 알파벳이 없는 블록 더미는 답이 아니라는 것을

will never form one.

본능적으로 알 수 있습니다. 왜일까요?

Why?

The first and last blocks can’t be the same if there are no repeats.

첫 블록과 마지막 블록은 무조건 같은 알파벳이어야 합니다.

So when can a given sequence become a palindrome?

그렇다면 어떤 조합이 회문형 구조를 이룰까요?

One way to figure that out is to analyze a few existing palindromes.

몇몇 회문형 단어를 분석해서 알아내 봅시다.

In ANNA, there are 2 A’s and 2 N’s.

ANNA라는 단어에는 A와 N이 모두 2개씩 존재합니다.

RACECAR has 2 R’s, 2 A’s, 2 C’s, and 1 E.

RACECAR에는 R이 2개, A가 2개, C가 2개

그리고 E가 1개 존재합니다.

And MADAM IM ADAM has 4 M’s, 4 A’s, 2 D’s, and 1 I.

MADAM IM ADAM에는 M이 4개, A가 4개, D가 2개,

I가 1개 존재합니다.

The pattern here is that most of the letters occur

이 패턴으로 대부분의 알파벳이

an even number of times,

짝수 번으로 존재하며

and there’s at most 1 that occurs just once.

한 번 등장하는 알파벳은 꼭 1개라는 걸 알 수 있습니다.

Is that it?

과연 그럴까요?

What if RACECAR had 3 E’s instead of 1?

만약에 RACECAR에 E가 1개가 아닌 3개 있다면 어떨까요?

We could tack the new E’s onto the ends and still get a palindrome,

추가된 E로 양 끝에 놓아도 여전히 회문형 구조를 유지합니다.

so 3 is ok.

그러니 3개는 괜찮습니다.

But make that 3 E’s and 3 C’s, and there’s nowhere for the last C to go.

하지만 E와 C가 각각 3개씩이라면, 추가된 C는 자리할 곳이 없습니다.

So the most generalized insight is that

결과적으로 가장 일반화된 접근법은

at most one letter can appear an odd number of times,

최대 1개의 알파벳은 홀수 번으로 나올 수 있지만

but the rest have to be even.

나머지 알파벳은 짝수개여야 한다는 것입니다.

Hedge can count the letters in each stack and organize them into a dictionary,

헤지는 각각의 더미의 글자 개수를 세고 알파벳 순으로 정렬할 수 있습니다.

which is a tidy way of storing information.

정보를 저장하는 간편한 방식이죠.

A loop could then go through and count how many times odd numbers appear.

루프를 이용해 홀수가 몇 번 등장하는지 셀 수 있습니다.

If there are less than 2 odd characters, the stack can be made into a palindrome.

홀수 문자가 2개 이하라면, 이 더미는 회문형이 될 수 있습니다.

This approach is much, much faster than the naïve solution.

이 방식은 단순한 해결책보다 훨씬 더 빠릅니다.

Instead of factorial time, it takes linear time.

계승 시간이 아닌, 선형 시간이기 때문입니다.

That’s where the time increases

존재하는 블록 수에 비례해서

in proportion to the number of blocks there are.

소요 시간이 늘어나는 이유입니다.

Now write a loop for Hedge to approach the piles individually,

이제 헤지가 더미에 접근하도록 루프를 써보겠습니다.

and stop when he finds a good one, and you’ll be ready to go.

헤지가 적절한 블록을 찾으면 출발할 준비가 완료된 것입니다.

Here’s what happens:

어떤 일이 일어날지 살펴봅시다.

Hedge is fast, but there are so many piles it takes a long time.

헤지는 빠르지만, 더미가 너무 많아 시간이 오래 걸립니다.

Too long.

엄청나게 멀군요.

Ethic and Hedge are safe.

에틱과 헤지는 안전합니다.

But Octavia is not so lucky.

그러나 옥타비아는 운이 썩 좋지 못했습니다.