에틱과 헤지는 거대한 탑의 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번만 봅니다.
선형 증가라는 것이죠.
이 방법을 더 개선할 수도 있겠지만
우리 주인공들에겐 이 정도로 충분하겠군요.
둘은 한몸처럼 움직입니다.
첫 번째 벽은 쉬웠고 두 사람은 탑을 올라갑니다.
두 번째는 조금 더 어렵습니다.
수십 개의 블록이 있는 세 번째 벽은 거대합니다.
타이머는 다 되어 가지만 에틱의 프로그램은 빠릅니다.
에틱은 딱 맞는 시간에 핸들을 바른 위치에 두었고
에너지가 두 사람을 창조의 노드에 데려다 줍니다.
처음에 그랬던 것처럼 노드는 몇 년 전 과거의 기억을 보여 줍니다.
월드 머신은 모든 걸 변화시켰고
에틱은 최고 로봇 공학자로서
그녀가 목격한 장면에 괴로워했죠.
모두를 안에 두려고 브래드 장벽이 가동되었을 때
그녀는 뭔가 크게 틀어졌다는 것을 알아차렸습니다.
그래서 그녀는 세 개의 물건을 만들어
사람들의 힘과 창조성, 기억을 회복시킬 능력을 넣어서
세 지역에 몰래 숨겨 놨습니다.
그녀가 사람들에게 사용법을 알려 주기 전에
정부가 그 일을 알아 차렸고 로봇들을 보내서
그녀와 다른 프로그래머들을 체포했습니다.
에틱이 월드 머신으로 마지막으로 만든 것은
고대 장치를 보호하기 위한 로봇입니다.
무지의 힘에 맞서 거대한 미로에 숨긴 거죠.
에틱은 그 로봇을 헤지라고 이름붙였습니다.
에틱과 헤지를 올려주던 에너지가 갑자기 깜박거리더니 스르륵 사라집니다.