< Return to Video

깊은 협곡 l 암호 프로그래머처럼 생각하라, 6화

  • 0:22 - 0:27
    에틱, 헤지와 옥타비아는 끝이
    보이지 않는 협곡에 서 있습니다.
  • 0:27 - 0:29
    타워에 가기 전에 이곳만 지나면
  • 0:29 - 0:33
    세 가지 유물 중 두 번째 유물이
    완성됩니다.
  • 0:33 - 0:38
    경비 로봇이 돌아오기 전까지
    빠르게 길을 건너야 합니다.
  • 0:38 - 0:43
    헤지의 연료가 바닥나서
    에틱을 비행시켜줄 수 없습니다.
  • 0:43 - 0:46
    다리 건설이 유일한 해결책입니다.
  • 0:46 - 0:51
    다행히, 주변에 떠 있는 돌무더기로
    다리를 지을 수 있습니다.
  • 0:51 - 0:55
    옥타비아가 개발한 호버블록이죠.
  • 0:55 - 0:57
    에너지를 방출해
    블록 더미를 활성화하면,
  • 0:57 - 1:02
    자동으로 조립되어 에틱이
    건널 수 있게 협곡을 이어줍니다.
  • 1:02 - 1:06
    하지만 물론 문제점도 있습니다.
  • 1:06 - 1:10
    호버블록은 완벽한 회문형일 때만
    안정적인 상태를 유지합니다.
  • 1:10 - 1:14
    즉, 동일한 배열 순서로
    이뤄져야 합니다.
  • 1:14 - 1:17
    앞이나 뒤 어느 쪽에서 보아도요.
  • 1:17 - 1:19
    이 더미는 처음에는 무작위로 놓이지만
  • 1:19 - 1:23
    항상 회문형으로 재배치됩니다.
  • 1:23 - 1:24
    가능할 때만요.
  • 1:24 - 1:27
    회문형 배열이 불가능할 때에는
  • 1:27 - 1:28
    다리가 붕괴합니다.
  • 1:28 - 1:32
    다리 위를 건너던 모든 이들이
    협곡 아래로 추락할 것입니다.
  • 1:32 - 1:33
    예를 살펴볼까요.
  • 1:33 - 1:36
    안정적인 상태를 유지하는 더미입니다.
  • 1:36 - 1:39
    A블록이 먼저 양 끝에 위치합니다.
  • 1:39 - 1:40
    그 옆에 B블록이 붙습니다.
  • 1:40 - 1:44
    마지막으로 그 사이에
    C블록이 쏙 들어갑니다.
  • 1:44 - 1:47
    하지만, A블록이 한 개
    더 있다고 가정해봅시다.
  • 1:47 - 1:50
    일단 양쪽에 A블록과 B블록이
    차례로 하나씩 자리합니다.
  • 1:50 - 1:54
    하지만 남은 C블록과 A블록이
    위치할 곳을 찾지 못하므로,
  • 1:54 - 1:56
    모든 블록이 무너집니다.
  • 1:56 - 2:01
    헤지는 노드의 힘으로
    블록 한더미를 활성화할 수 있습니다.
  • 2:01 - 2:05
    에틱이 헤지에게 어떤 조언을 해서
  • 2:05 - 2:08
    안정적인 회문형 구조를 알아내고
    유지하도록 하게 할까요?
  • 2:08 - 2:18
    잠시 멈추고 스스로 해결해보세요.
  • 2:18 - 2:24
    예로는 ANNA, RACECAR,
    MADAM IM ADAM가 있습니다.
  • 2:24 - 2:27
    각각의 알파벳의 수를 세보면
  • 2:27 - 2:30
    힌트가 되는 패턴을 알 수 있습니다.
  • 2:30 - 2:35
    잠시 멈추고 스스로 해결해보세요.
  • 2:35 - 2:38
    일단 단순한 해결법을 살펴봅니다.
  • 2:38 - 2:43
    단순한 해결책은 간단하지만
    비효율적인 억지스러운 접근법입니다.
  • 2:43 - 2:45
    하지만 해결이 되긴 합니다.
  • 2:45 - 2:48
    단순한 해결책들은 문제를
    분석하기에 용이한 방식이며
  • 2:48 - 2:52
    더 좋은 해결책을 찾을 수
    있는 초석이 되어줍니다.
  • 2:52 - 2:56
    이 문제의 단순한 해결법은
    블록 더미에 가서
  • 2:56 - 2:57
    모든 조합을 구성한 후에
  • 2:57 - 3:02
    그대로 혹은 역순으로 읽어보고
    회문형인지 일일이 살펴보는 것입니다.
  • 3:02 - 3:03
    이 방식의 문제점은
  • 3:03 - 3:06
    시간이 너무 오래 걸린다는 점입니다.
  • 3:06 - 3:09
    헤지가 1초마다 1개의 조합을
    구성한다고 가정하면,
  • 3:09 - 3:14
    10개의 블록 더미를 조합해 보는데
    꼬박 42일이 걸립니다.
  • 3:14 - 3:18
    전체 시간은 블록 개수의
  • 3:18 - 3:20
    계승 값과 동일하기 때문입니다.
  • 3:20 - 3:23
    10개의 블록으로 3백만 개
    이상의 조합법이 가능합니다.
  • 3:23 - 3:28
    이 단순한 해결책을 보니
    훨씬 빠른 다른 방식으로
  • 3:28 - 3:31
    회문형 여부를 판단해야
    한다는 것을 알 수 있습니다.
  • 3:31 - 3:36
    일단은, 겹치는 알파벳이 없는
    블록 더미는 답이 아니라는 것을
  • 3:36 - 3:38
    본능적으로 알 수 있습니다. 왜일까요?
  • 3:38 - 3:43
    첫 블록과 마지막 블록은
    무조건 같은 알파벳이어야 합니다.
  • 3:43 - 3:48
    그렇다면 어떤 조합이
    회문형 구조를 이룰까요?
  • 3:48 - 3:53
    몇몇 회문형 단어를
    분석해서 알아내 봅시다.
  • 3:53 - 3:56
    ANNA라는 단어에는
    A와 N이 모두 2개씩 존재합니다.
  • 3:56 - 3:59
    RACECAR에는
    R이 2개, A가 2개, C가 2개
  • 3:59 - 4:01
    그리고 E가 1개 존재합니다.
  • 4:01 - 4:06
    MADAM IM ADAM에는
    M이 4개, A가 4개, D가 2개,
  • 4:06 - 4:08
    I가 1개 존재합니다.
  • 4:08 - 4:11
    이 패턴으로 대부분의 알파벳이
  • 4:11 - 4:13
    짝수 번으로 존재하며
  • 4:13 - 4:16
    한 번 등장하는 알파벳은
    꼭 1개라는 걸 알 수 있습니다.
  • 4:16 - 4:17
    과연 그럴까요?
  • 4:17 - 4:20
    만약에 RACECAR에 E가 1개가
    아닌 3개 있다면 어떨까요?
  • 4:20 - 4:24
    추가된 E로 양 끝에 놓아도
    여전히 회문형 구조를 유지합니다.
  • 4:24 - 4:26
    그러니 3개는 괜찮습니다.
  • 4:26 - 4:32
    하지만 E와 C가 각각 3개씩이라면,
    추가된 C는 자리할 곳이 없습니다.
  • 4:32 - 4:35
    결과적으로 가장 일반화된 접근법은
  • 4:35 - 4:39
    최대 1개의 알파벳은
    홀수 번으로 나올 수 있지만
  • 4:39 - 4:42
    나머지 알파벳은 짝수개여야
    한다는 것입니다.
  • 4:42 - 4:46
    헤지는 각각의 더미의 글자 개수를 세고
    알파벳 순으로 정렬할 수 있습니다.
  • 4:46 - 4:49
    정보를 저장하는 간편한 방식이죠.
  • 4:49 - 4:53
    루프를 이용해 홀수가
    몇 번 등장하는지 셀 수 있습니다.
  • 4:53 - 4:59
    홀수 문자가 2개 이하라면,
    이 더미는 회문형이 될 수 있습니다.
  • 4:59 - 5:03
    이 방식은 단순한 해결책보다
    훨씬 더 빠릅니다.
  • 5:03 - 5:06
    계승 시간이 아닌,
    선형 시간이기 때문입니다.
  • 5:06 - 5:08
    존재하는 블록 수에 비례해서
  • 5:08 - 5:10
    소요 시간이 늘어나는 이유입니다.
  • 5:10 - 5:14
    이제 헤지가 더미에 접근하도록
    루프를 써보겠습니다.
  • 5:14 - 5:19
    헤지가 적절한 블록을 찾으면
    출발할 준비가 완료된 것입니다.
  • 5:19 - 5:20
    어떤 일이 일어날지 살펴봅시다.
  • 5:20 - 5:24
    헤지는 빠르지만, 더미가 너무 많아
    시간이 오래 걸립니다.
  • 5:24 - 5:25
    엄청나게 멀군요.
  • 6:18 - 6:20
    에틱과 헤지는 안전합니다.
  • 6:20 - 6:22
    그러나 옥타비아는 운이
    썩 좋지 못했습니다.
Title:
깊은 협곡 l 암호 프로그래머처럼 생각하라, 6화
Speaker:
알렉스 로젠탈 (Alex Rosenthal)
Description:

전체 강의 보기: https://ed.ted.com/lessons/the-chasm-think-like-a-coder-ep-6

애니메이션 "암호 프로그래머처럼 생각하라" 에피소드 6화입니다. 10개 에피소드로 이루어진 이 시리즈에서 에틱이라는 소녀와 로봇 친구인 헤지는 세상을 구하려 노력합니다. 이들은 세가지 유물을 모으는 도전을 마주하고 퍼즐을 프로그래밍해서 길을 찾아내야합니다.

강의: 알렉스 로젠탈(Alex Rosenthal) 제작: 코즈모노 애니메이션 스튜디오(Kozmonot Animation Studio)
more » « less
Video Language:
English
Team:
closed TED
Project:
TED-Ed
Duration:
06:24

Korean subtitles

Revisions

Our website uses cookies for analysis purposes.