통찰의 탑 | 프로그래머처럼 생각하기. 7편

전체 강의 보기: https://ed.ted.com/lessons/the-tower-of-epiphany-think-like-a-coder-ep-7

애니메이션 시리즈 '프로그래머처럼 생각하기'의 일곱 번째 편입니다. 10부작은 에틱과 로봇 친구 헤지가 세계를 구하기 위해 분투하는 이야기를 담고 있습니다. 에틱과 헤지는 3개의 물건을 모아야 하는 임무에 착수했고 프로그래밍 문제들을 풀어나가야 합니다.

강의: 알렉스 로젠탈(Alex Rosenthal)
제작: 코즈모노트 애니메이션 스튜디오(Kozmonot Animation Studio)

에틱과 헤지는
거대한 탑의 1층에 있습니다.

에너지 장벽이 이들을
두 번째 목표물과 갈라놓습니다.

바로 창조의 노드입니다.

이에 가려면 에너지 흐름 세 개를
이용해 탑을 올라가야 합니다.

에틱이 앞으로 한 발짝 내딛는 순간
시계가 60초부터 세어 내려갑니다.

방 뒤편에는 보이지 않는
통으로 된 벽이 서 있는데

에너지를 담을 수 있습니다.

1분 뒤에는 에너지가 쏟아져 내리고

한 번에 1칸씩 채웁니다.

장벽이 있어서 에너지가
앞뒤로는 흐르지 않게 합니다.

평온한 이 60초 내에

에틱과 헤지는 정확히 몇 개의
에너지가 떨어질지 판단해야 합니다.

세 번의 과제 모두에서

통에 채울 에너지의 양을
정확히 맞춰야 합니다.

성공하면, 에너지를 이용해
위로 올라갈 수 있습니다.

하지만 양을 맞추지 못하면,
에너지를 이용한 이동은 실패하고

그들은 추락할 것입니다.

벽면의 그림에 예시가 있습니다.

이 배열은 정확히
두 개의 에너지를 담습니다.

이 배열은 네 개를 담는데
세 개는 여기, 한 개는 여기요.

이 배열도 역시 네 개를 담는데

오른쪽에 있는 에너지는
넘쳐 흐를 테니까요.

에너지가 쏟아져 내리고

이 에너지를 받아 낼 공간이
없으면 넘쳐흐릅니다.

헤지는 한 번에 한 줄씩을
확인하여 높이를 계산할 수 있지만

전체 구조를 동시에 볼 수는 없습니다.

에틱은 헤지를 어떻게 설정해야

각각의 통이 에너지를 정확히
얼마나 담을는지 알 수 있을까요?

잠시 멈춰서 스스로 생각해 보세요.

한 가지 예를 들어 보겠습니다.

비어 있는 각 칸이 에너지를 담으려면

그 칸의 왼쪽에 벽이 있고

오른쪽에도 벽이 있어야 합니다.

하지만 헤지가 모든 칸을 하나씩
확인하는 것은 너무 오래 걸립니다.

헤지가 한 번에 한 줄 전체를
살펴보게 하면 어떨까요?

예를 들어 한 줄이 에너지를 얼마나
담을 수 있을지를 알아보는 거죠.

잠시 멈춰서 스스로 생각해 보세요.

예제를 보고 문제를 분석해 봅시다.

블록이 다섯 줄 있습니다.

가장 왼쪽 줄은 제일 높아서
에너지를 담을 수 없습니다.

두 번째 줄은 세 단위를
담을 수 있습니다.

4개짜리 줄들 사이에 있기 때문이죠.

세 단위의 에너지를 얻게 되는데
에너지가 평평하게 쌓이는 높이 4에서

줄의 높이를 빼면
4 빼기 1이 되기 때문이죠.

세 번째 줄도 비슷하게 왼쪽 4개,
오른쪽 4개, 줄 높이 3이죠.

따라서 4에서 3을 뺀
1단위가 담깁니다.

네 번째, 다섯 번째 줄은
오른쪽에 더 높은 줄이 없으므로

에너지를 담지 못합니다.

이 개념을 알고리즘에
적용할 수 있습니다.

한 번에 한 개의 줄을
기준으로 삼는 방법입니다.

헤지는 줄을 왼쪽으로 하나씩 살펴서
가장 긴 것의 높이를 찾고

우측으로도 하나씩 살펴서
가장 긴 것의 높이를 찾습니다.

둘 중 짧은 것의 높이가 에너지를
담을 수 있는 높이입니다.

결과가 원래 줄보다 크면

원래 줄 높이를 빼고

그 값이 그 줄에
담을 수 있는 단위입니다.

값이 그 줄의 높이와 같거나 더 적다면

에너지는 흘러 넘칠 거예요.

헤지는 통 전체를 가장 왼쪽부터

오른쪽으로 한 칸씩
돌아가면서 적용할 수 있어요.

각 줄에서 헤지는 같은 일을 하는데
왼쪽 끝까지 가장 높은 걸 찾고

오른쪽으로도 그렇게 한 다음
둘 중 낮은 걸 찾고

원래 줄의 높이를 빼서

값이 양수이면 총합을 증가시키죠.

헤지는 줄을 다 살펴볼 때까지
계속 반복할 거예요.

되긴 하겠지만 통이 커지면
시간이 오래 걸리겠죠.

한 칸을 움직일 때마다 헤지는
왼쪽과 오른쪽을 보는 걸 반복합니다.

N개의 줄이 있다면
N개의 줄을 N번씩 보게 되죠.

더 빠른 방법은 없을까요?

시간을 아끼는 방법이 있습니다.

헤지는 제일 처음에
일단 왼쪽에서 시작해서

현재 가장 높은 줄의 높이를
적어 둘 수 있죠.

여기선 2이고 첫 번째 스택이
더 높으니까 또 2입니다.

그다음은 4, 4, 4입니다.

그리고 오른쪽에서 가장 높은 걸
같은 방법으로 찾습니다.

오른쪽에서 왼쪽으로 똑같이 하면
1, 3, 4, 4, 4가 되네요.

마지막엔 헤지의 메모리에
이런 표가 있겠죠.

이제 한 단계만 더 하면
에너지가 얼마나 쌓일 수 있는지를

위와 같은 방식을 써서
각 줄별로 알 수 있습니다.

왼쪽과 오른쪽에서 저장한 값 중에
더 작은 것을 선택하고

현재 줄의 높이를 빼는 거죠.

N개의 줄을 N번씩 보는 대신에
N개의 줄을 3번만 봅니다.

선형 증가라는 것이죠.

이 방법을 더 개선할 수도 있겠지만

우리 주인공들에겐
이 정도로 충분하겠군요.

둘은 한몸처럼 움직입니다.

첫 번째 벽은 쉬웠고
두 사람은 탑을 올라갑니다.

두 번째는 조금 더 어렵습니다.

수십 개의 블록이 있는
세 번째 벽은 거대합니다.

타이머는 다 되어 가지만
에틱의 프로그램은 빠릅니다.

에틱은 딱 맞는 시간에
핸들을 바른 위치에 두었고

에너지가 두 사람을
창조의 노드에 데려다 줍니다.

처음에 그랬던 것처럼 노드는
몇 년 전 과거의 기억을 보여 줍니다.

월드 머신은 모든 걸 변화시켰고

에틱은 최고 로봇 공학자로서

그녀가 목격한 장면에 괴로워했죠.

모두를 안에 두려고
브래드 장벽이 가동되었을 때

그녀는 뭔가 크게 틀어졌다는
것을 알아차렸습니다.

그래서 그녀는 세 개의 물건을 만들어

사람들의 힘과 창조성,
기억을 회복시킬 능력을 넣어서

세 지역에 몰래 숨겨 놨습니다.

그녀가 사람들에게
사용법을 알려 주기 전에

정부가 그 일을 알아 차렸고
로봇들을 보내서

그녀와 다른 프로그래머들을
체포했습니다.

에틱이 월드 머신으로
마지막으로 만든 것은

고대 장치를 보호하기 위한 로봇입니다.

무지의 힘에 맞서
거대한 미로에 숨긴 거죠.

에틱은 그 로봇을 헤지라고
이름붙였습니다.

에틱과 헤지를 올려주던 에너지가 갑자기
깜박거리더니 스르륵 사라집니다.