WEBVTT

00:00:31.587 --> 00:00:37.288
에틱과 헤지는
거대한 탑의 1층에 있습니다.

00:00:37.288 --> 00:00:41.945
에너지 장벽이 이들을
두 번째 목표물과 갈라놓습니다.

00:00:41.945 --> 00:00:43.945
바로 창조의 노드입니다.

00:00:52.667 --> 00:00:57.409
이에 가려면 에너지 흐름 세 개를
이용해 탑을 올라가야 합니다.

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

00:01:07.359 --> 00:01:11.659
방 뒤편에는 보이지 않는
통으로 된 벽이 서 있는데

00:01:11.659 --> 00:01:14.735
에너지를 담을 수 있습니다.

00:01:14.735 --> 00:01:18.865
1분 뒤에는 에너지가 쏟아져 내리고

00:01:18.865 --> 00:01:21.015
한 번에 1칸씩 채웁니다.

00:01:21.015 --> 00:01:25.495
장벽이 있어서 에너지가
앞뒤로는 흐르지 않게 합니다.

00:01:25.495 --> 00:01:27.625
평온한 이 60초 내에

00:01:27.625 --> 00:01:32.723
에틱과 헤지는 정확히 몇 개의
에너지가 떨어질지 판단해야 합니다.

00:01:32.723 --> 00:01:34.423
세 번의 과제 모두에서

00:01:34.423 --> 00:01:38.088
통에 채울 에너지의 양을
정확히 맞춰야 합니다.

00:01:38.088 --> 00:01:41.938
성공하면, 에너지를 이용해
위로 올라갈 수 있습니다.

00:01:41.938 --> 00:01:46.558
하지만 양을 맞추지 못하면,
에너지를 이용한 이동은 실패하고

00:01:46.558 --> 00:01:48.048
그들은 추락할 것입니다.

00:01:48.048 --> 00:01:51.348
벽면의 그림에 예시가 있습니다.

00:01:51.348 --> 00:01:55.618
이 배열은 정확히
두 개의 에너지를 담습니다.

00:01:55.618 --> 00:02:00.735
이 배열은 네 개를 담는데
세 개는 여기, 한 개는 여기요.

00:02:00.735 --> 00:02:03.275
이 배열도 역시 네 개를 담는데

00:02:03.275 --> 00:02:06.688
오른쪽에 있는 에너지는
넘쳐 흐를 테니까요.

00:02:06.688 --> 00:02:08.908
에너지가 쏟아져 내리고

00:02:08.908 --> 00:02:13.538
이 에너지를 받아 낼 공간이
없으면 넘쳐흐릅니다.

00:02:13.538 --> 00:02:18.865
헤지는 한 번에 한 줄씩을
확인하여 높이를 계산할 수 있지만

00:02:18.865 --> 00:02:22.725
전체 구조를 동시에 볼 수는 없습니다.

00:02:22.725 --> 00:02:25.140
에틱은 헤지를 어떻게 설정해야

00:02:25.140 --> 00:02:29.340
각각의 통이 에너지를 정확히
얼마나 담을는지 알 수 있을까요?

00:02:29.340 --> 00:02:32.935
잠시 멈춰서 스스로 생각해 보세요.

00:02:38.805 --> 00:02:41.635
한 가지 예를 들어 보겠습니다.

00:02:41.635 --> 00:02:44.550
비어 있는 각 칸이 에너지를 담으려면

00:02:44.550 --> 00:02:48.790
그 칸의 왼쪽에 벽이 있고

00:02:48.790 --> 00:02:51.517
오른쪽에도 벽이 있어야 합니다.

00:02:51.517 --> 00:02:56.322
하지만 헤지가 모든 칸을 하나씩
확인하는 것은 너무 오래 걸립니다.

00:02:56.322 --> 00:03:01.185
헤지가 한 번에 한 줄 전체를
살펴보게 하면 어떨까요?

00:03:01.185 --> 00:03:05.025
예를 들어 한 줄이 에너지를 얼마나
담을 수 있을지를 알아보는 거죠.

00:03:05.025 --> 00:03:10.389
잠시 멈춰서 스스로 생각해 보세요.

00:03:10.389 --> 00:03:13.759
예제를 보고 문제를 분석해 봅시다.

00:03:13.759 --> 00:03:15.914
블록이 다섯 줄 있습니다.

00:03:15.914 --> 00:03:20.484
가장 왼쪽 줄은 제일 높아서
에너지를 담을 수 없습니다.

00:03:20.484 --> 00:03:23.118
두 번째 줄은 세 단위를
담을 수 있습니다.

00:03:23.118 --> 00:03:27.244
4개짜리 줄들 사이에 있기 때문이죠.

00:03:27.244 --> 00:03:32.186
세 단위의 에너지를 얻게 되는데
에너지가 평평하게 쌓이는 높이 4에서

00:03:32.186 --> 00:03:36.346
줄의 높이를 빼면
4 빼기 1이 되기 때문이죠.

00:03:36.346 --> 00:03:41.808
세 번째 줄도 비슷하게 왼쪽 4개,
오른쪽 4개, 줄 높이 3이죠.

00:03:41.808 --> 00:03:46.537
따라서 4에서 3을 뺀
1단위가 담깁니다.

00:03:46.537 --> 00:03:50.957
네 번째, 다섯 번째 줄은
오른쪽에 더 높은 줄이 없으므로

00:03:50.957 --> 00:03:53.427
에너지를 담지 못합니다.

00:03:53.427 --> 00:03:57.245
이 개념을 알고리즘에
적용할 수 있습니다.

00:03:57.245 --> 00:04:01.171
한 번에 한 개의 줄을
기준으로 삼는 방법입니다.

00:04:01.171 --> 00:04:05.455
헤지는 줄을 왼쪽으로 하나씩 살펴서
가장 긴 것의 높이를 찾고

00:04:05.455 --> 00:04:08.156
우측으로도 하나씩 살펴서
가장 긴 것의 높이를 찾습니다.

00:04:08.156 --> 00:04:12.833
둘 중 짧은 것의 높이가 에너지를
담을 수 있는 높이입니다.

00:04:12.833 --> 00:04:15.963
결과가 원래 줄보다 크면

00:04:15.963 --> 00:04:18.537
원래 줄 높이를 빼고

00:04:18.537 --> 00:04:23.634
그 값이 그 줄에
담을 수 있는 단위입니다.

00:04:23.634 --> 00:04:27.194
값이 그 줄의 높이와 같거나 더 적다면

00:04:27.194 --> 00:04:29.397
에너지는 흘러 넘칠 거예요.

00:04:29.397 --> 00:04:32.917
헤지는 통 전체를 가장 왼쪽부터

00:04:32.917 --> 00:04:38.662
오른쪽으로 한 칸씩
돌아가면서 적용할 수 있어요.

00:04:38.662 --> 00:04:43.671
각 줄에서 헤지는 같은 일을 하는데
왼쪽 끝까지 가장 높은 걸 찾고

00:04:43.671 --> 00:04:47.231
오른쪽으로도 그렇게 한 다음
둘 중 낮은 걸 찾고

00:04:47.231 --> 00:04:49.318
원래 줄의 높이를 빼서

00:04:49.318 --> 00:04:53.178
값이 양수이면 총합을 증가시키죠.

00:04:53.178 --> 00:04:56.848
헤지는 줄을 다 살펴볼 때까지
계속 반복할 거예요.

00:04:56.848 --> 00:05:00.798
되긴 하겠지만 통이 커지면
시간이 오래 걸리겠죠.

00:05:00.798 --> 00:05:05.328
한 칸을 움직일 때마다 헤지는
왼쪽과 오른쪽을 보는 걸 반복합니다.

00:05:05.328 --> 00:05:10.280
N개의 줄이 있다면
N개의 줄을 N번씩 보게 되죠.

00:05:10.280 --> 00:05:12.260
더 빠른 방법은 없을까요?

00:05:12.260 --> 00:05:14.048
시간을 아끼는 방법이 있습니다.

00:05:14.048 --> 00:05:17.468
헤지는 제일 처음에
일단 왼쪽에서 시작해서

00:05:17.468 --> 00:05:21.338
현재 가장 높은 줄의 높이를
적어 둘 수 있죠.

00:05:21.338 --> 00:05:25.098
여기선 2이고 첫 번째 스택이
더 높으니까 또 2입니다.

00:05:25.098 --> 00:05:27.848
그다음은 4, 4, 4입니다.

00:05:27.848 --> 00:05:30.628
그리고 오른쪽에서 가장 높은 걸
같은 방법으로 찾습니다.

00:05:30.628 --> 00:05:36.882
오른쪽에서 왼쪽으로 똑같이 하면
1, 3, 4, 4, 4가 되네요.

00:05:36.882 --> 00:05:40.722
마지막엔 헤지의 메모리에
이런 표가 있겠죠.

00:05:40.722 --> 00:05:45.961
이제 한 단계만 더 하면
에너지가 얼마나 쌓일 수 있는지를

00:05:45.961 --> 00:05:50.001
위와 같은 방식을 써서
각 줄별로 알 수 있습니다.

00:05:50.001 --> 00:05:53.638
왼쪽과 오른쪽에서 저장한 값 중에
더 작은 것을 선택하고

00:05:53.638 --> 00:05:56.708
현재 줄의 높이를 빼는 거죠.

00:05:56.708 --> 00:06:02.293
N개의 줄을 N번씩 보는 대신에
N개의 줄을 3번만 봅니다.

00:06:02.293 --> 00:06:04.573
선형 증가라는 것이죠.

00:06:04.573 --> 00:06:07.814
이 방법을 더 개선할 수도 있겠지만

00:06:07.814 --> 00:06:10.564
우리 주인공들에겐
이 정도로 충분하겠군요.

00:06:10.564 --> 00:06:12.524
둘은 한몸처럼 움직입니다.

00:06:14.992 --> 00:06:18.836
첫 번째 벽은 쉬웠고
두 사람은 탑을 올라갑니다.

00:06:21.573 --> 00:06:23.583
두 번째는 조금 더 어렵습니다.

00:06:33.051 --> 00:06:36.911
수십 개의 블록이 있는
세 번째 벽은 거대합니다.

00:06:36.911 --> 00:06:41.344
타이머는 다 되어 가지만
에틱의 프로그램은 빠릅니다.

00:06:41.344 --> 00:06:44.308
에틱은 딱 맞는 시간에
핸들을 바른 위치에 두었고

00:06:49.015 --> 00:06:51.935
에너지가 두 사람을
창조의 노드에 데려다 줍니다.

00:06:55.640 --> 00:07:01.067
처음에 그랬던 것처럼 노드는
몇 년 전 과거의 기억을 보여 줍니다.

00:07:01.067 --> 00:07:03.187
월드 머신은 모든 걸 변화시켰고

00:07:03.187 --> 00:07:06.856
에틱은 최고 로봇 공학자로서

00:07:06.856 --> 00:07:08.906
그녀가 목격한 장면에 괴로워했죠.

00:07:08.906 --> 00:07:11.946
모두를 안에 두려고
브래드 장벽이 가동되었을 때

00:07:11.946 --> 00:07:14.586
그녀는 뭔가 크게 틀어졌다는
것을 알아차렸습니다.

00:07:14.586 --> 00:07:16.676
그래서 그녀는 세 개의 물건을 만들어

00:07:16.676 --> 00:07:21.221
사람들의 힘과 창조성,
기억을 회복시킬 능력을 넣어서

00:07:21.221 --> 00:07:24.131
세 지역에 몰래 숨겨 놨습니다.

00:07:24.131 --> 00:07:26.449
그녀가 사람들에게
사용법을 알려 주기 전에

00:07:26.449 --> 00:07:29.507
정부가 그 일을 알아 차렸고
로봇들을 보내서

00:07:29.507 --> 00:07:31.889
그녀와 다른 프로그래머들을
체포했습니다.

00:07:31.889 --> 00:07:35.209
에틱이 월드 머신으로
마지막으로 만든 것은

00:07:35.209 --> 00:07:37.999
고대 장치를 보호하기 위한 로봇입니다.

00:07:37.999 --> 00:07:42.329
무지의 힘에 맞서
거대한 미로에 숨긴 거죠.

00:07:42.329 --> 00:07:44.743
에틱은 그 로봇을 헤지라고
이름붙였습니다.

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