Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

11장. 지도 앱은 어떻게 길을 찾는가

“GPS, 지도, 경로 탐색 알고리즘”

이번 장에서 알게 될 것

  • 스마트폰이 내 위치를 수 미터 오차로 아는 원리
  • 아인슈타인의 상대성이론이 GPS에 적용되고 있다는 사실
  • 지도 앱이 가장 빠른 길을 찾는 알고리즘
  • 배달 예상 시간 “35분“이 어떻게 계산되는지

치킨 주문 여정: 치킨이 출발했다

“주문이 접수되었습니다.” “배달원이 가게에서 출발했습니다.” 화면에 지도가 뜨고, 배달원의 위치가 실시간으로 움직입니다. 배달원의 위치를 어떻게 아는 걸까요?

하늘 위 20,200km에서 쏘는 시간 신호

배달원의 위치를 아는 것, 즉 GPS(Global Positioning System) 의 원리부터 알아보겠습니다.

지구 궤도 약 20,200km 높이에는 31개의 GPS 위성이 돌고 있습니다. 이 위성들은 끊임없이 하나의 메시지를 보냅니다 — “나는 지금 여기에 있고, 지금 시각은 이것이다.”

스마트폰은 이 신호를 받아서 자신의 위치를 계산합니다. 원리는 이렇습니다.

[그림 11-1] GPS 위치 결정 원리

  GPS 위치 결정 원리:

  위성 A: "내 위치는 여기, 시각은 12:00:00.000"
  위성 B: "내 위치는 여기, 시각은 12:00:00.000"
  위성 C: "내 위치는 여기, 시각은 12:00:00.000"

  스마트폰: "신호가 도착한 시각은 12:00:00.067"
  → 도착까지 0.067초 걸렸다
  → 전파 속도(빛의 속도) × 시간 = 거리
  → 위성 A로부터 약 20,100km 떨어져 있다

위성 하나로는 “위성에서 20,100km 떨어진 구(球) 위의 어딘가“까지만 알 수 있습니다. 위성 두 개면 두 구의 교차선, 세 개면 두 점, 네 개면 정확한 한 점이 됩니다. 이것을 삼변측량1 이라고 합니다.

[그림 11-2] 삼변측량의 원리

  삼변측량:

       위성 A            위성 B            위성 C
         ●                 ●                 ●
        / \               / \               / \
       /   \             /   \             /   \
      /     \           /     \           /     \
     /   ●   \         /   ●   \         /   ●   \
    (  내폰은  )       (  내폰은  )       (  내폰은  )
     \ 이 원 위/        \ 이 원 위/        \ 이 원 위/
      \_____/           \_____/           \_____/

  3개의 원이 교차하는 점 = 내 위치!

실제로는 위성 최소 4개가 필요합니다. 3개로 위치를 정하고, 4번째로 시간 오차를 보정합니다.

1나노초 = 30cm 오차

GPS에서 시간은 생명입니다. 전파는 빛의 속도(초속 약 30만 km)로 이동합니다. 1초에 30만 km를 가니까, 10억분의 1초(1나노초) 의 시간 오차는 약 30cm의 거리 오차가 됩니다.

이 정밀한 시간을 측정하기 위해 GPS 위성에는 원자시계가 탑재되어 있습니다. 원자시계는 10만 년에 1초 정도의 오차만 발생하는, 인류가 만든 가장 정확한 시계입니다.

아인슈타인이 GPS를 가능하게 했다

GPS 위성은 초속 약 3.9km로 움직이고, 지상 20,200km 높이에 있습니다. 여기서 아인슈타인의 상대성이론이 등장합니다.

[그림 11-3] 상대성이론과 GPS 시간 보정

  상대성이론과 GPS:

  특수 상대성이론:
    빠르게 움직이는 물체의 시간은 느리게 간다
    → 위성 시계가 하루에 약 7마이크로초 느려짐

  일반 상대성이론:
    중력이 약한 곳의 시간은 빠르게 간다
    → 높은 곳은 중력이 약함
    → 위성 시계가 하루에 약 45마이크로초 빨라짐

  합산: +45 - 7 = +38마이크로초/일 (하루에 38마이크로초 빨라짐)

  38마이크로초 × 빛의 속도 = 하루에 약 11km 오차!
  → 보정하지 않으면 GPS가 매일 11km씩 틀어짐

위성의 시계가 하루에 38마이크로초씩 빨라지는 것을 보정하지 않으면, GPS 위치가 하루에 약 11km씩 틀어집니다. 내비게이션이 한강을 가리키고 있을 수 있다는 뜻입니다. 100년 전 이론물리학자가 쓴 공식이 오늘날 배달 추적에 사용되고 있는 셈입니다.

최단 경로: 네비게이션은 어떻게 길을 찾는가

배달원의 위치를 알았으니, 이제 가게에서 우리 집까지의 최적 경로를 찾아야 합니다.

지도를 컴퓨터가 이해할 수 있는 형태로 바꾸면, 교차로는 점(노드), 도로는 선(간선), 도로의 거리나 시간은 가중치가 됩니다.

[그림 11-4] 지도에서 그래프로의 변환

  지도를 그래프로 변환:

  실제 지도:                    컴퓨터의 그래프[^2]:

  치킨집 ─── 사거리A            치킨집 ──3분── A
    │          │                │            │
    │          │                5분           4분
    │          │                │            │
  사거리B ── 사거리C            B ──2분── C
    │                           │
    │                           7분
    │                           │
  우리집                        우리집

  치킨집 → 우리집 최단 경로는?
  경로1: 치킨집 → A → C → 우리집?  (3+4+?)
  경로2: 치킨집 → B → 우리집?     (5+7=12분)
  경로3: 치킨집 → B → C → ...?

이 문제를 푸는 가장 유명한 알고리즘이 다익스트라(Dijkstra) 알고리즘입니다. 1956년 네덜란드 컴퓨터 과학자 에츠허르 다익스트라가 카페에서 종이 위에 20분 만에 고안했다고 합니다.

다익스트라 알고리즘의 아이디어는 간단합니다.

[그림 11-5] 다익스트라 알고리즘의 개념

  다익스트라 알고리즘 (개념):

  "가장 가까운 곳부터 확정하고, 점점 넓혀간다"

  1. 출발점(치킨집)에서 시작
  2. 바로 갈 수 있는 곳 중 가장 가까운 곳을 "확정"
  3. 확정된 곳에서 갈 수 있는 새로운 곳의 거리를 계산
  4. 아직 확정 안 된 곳 중 가장 가까운 곳을 다시 "확정"
  5. 목적지가 확정될 때까지 반복

  마치 물이 퍼져나가듯,
  출발점에서 가장 가까운 곳부터 차례로 확정합니다.

구글 맵, 카카오맵, 네이버 지도 모두 이 알고리즘의 변형을 사용합니다. 물론 실제로는 도로의 수가 수백만 개이므로, 더 빠르게 계산하기 위한 다양한 최적화 기법이 추가됩니다.

실시간 교통: 지금 이 도로가 막히는지 어떻게 아는가

최단 거리가 항상 최단 시간은 아닙니다. 가장 짧은 도로가 교통 체증으로 막혀 있다면, 돌아가는 게 더 빠를 수 있습니다.

지도 앱은 실시간 교통 정보를 어디서 얻을까요? 답은 여러분의 폰입니다.

[그림 11-6] 실시간 교통 정보 수집

  실시간 교통 정보 수집:

  도로 위의 모든 스마트폰:
  ┌──────────────────────────────────┐
  │ 📱 📱 📱 📱 📱 📱 📱             │
  │     느리게 이동 중 (시속 10km)      │ → "이 도로 정체"
  │ ─────────────────── 도로 A ───── │
  └──────────────────────────────────┘

  ┌──────────────────────────────────┐
  │ 📱    📱    📱    📱             │
  │     빠르게 이동 중 (시속 60km)      │ → "이 도로 원활"
  │ ─────────────────── 도로 B ───── │
  └──────────────────────────────────┘

  수백만 대의 폰이 익명의 교통 센서 역할

구글 맵은 안드로이드 폰의 위치 데이터를 (익명으로) 수집합니다. 카카오맵은 카카오 택시와 카카오 내비 사용자의 GPS 데이터를 활용합니다. 특정 도로에서 여러 대의 폰이 느리게 이동하면 “정체”, 빠르게 이동하면 “원활“로 판단합니다.

이것을 크라우드소싱(Crowdsourcing)2 이라고 합니다. 지도 앱을 사용하는 사람이 많을수록 교통 정보가 정확해집니다. 여러분이 내비게이션을 켜고 운전하는 것만으로도, 다른 사람의 내비게이션에 기여하고 있는 겁니다.

배달 예상 시간: “35분“은 어떻게 계산되나

“배달 예상 시간: 35분.” 이 숫자는 어떻게 나올까요?

[그림 11-7] 배달 예상 시간 계산 요소

  배달 예상 시간 계산:

  ┌─────────────────────────────────┐
  │ 조리 시간                        │
  │  → 가게별 평균 조리 시간          │
  │  → 현재 주문 밀림 정도            │
  │  → 메뉴 복잡도                   │
  │                                 │
  │           +                     │
  │                                 │
  │ 이동 시간                        │
  │  → 가게 ~ 우리 집 최적 경로       │
  │  → 실시간 교통 상황               │
  │  → 시간대별 평균 소요 시간         │
  │                                 │
  │           +                     │
  │                                 │
  │ 보정                            │
  │  → 날씨 (비 오면 느려짐)          │
  │  → 요일/시간대 (금요일 저녁 피크)   │
  │  → 배달원 현재 위치               │
  │  → 과거 실제 배달 시간 데이터      │
  │                                 │
  │ = 예상 35분                      │
  └─────────────────────────────────┘

단순히 “거리 ÷ 속도“로 계산하는 것이 아닙니다. 가게의 현재 주문량, 실시간 교통, 날씨, 요일, 시간대, 과거 배달 데이터까지 종합합니다. 이 모든 변수를 인간이 직접 계산하는 것은 불가능하므로, 머신러닝(Machine Learning)3 모델이 과거 수백만 건의 배달 데이터를 학습해서 예측합니다.

그래서 배달 예상 시간은 때로 정확하고, 때로 틀립니다. 예측 모델이 경험하지 못한 상황(갑작스러운 폭우, 사고로 인한 도로 차단)이 발생하면 오차가 커집니다.

사건: 대한항공 007편 — GPS가 민간에 개방된 계기

1983년 9월 1일, 뉴욕발 서울행 대한항공 007편이 소련 영공을 침범해 격추됩니다.4 탑승자 269명 전원이 사망했습니다.

사고 원인은 항법 장치의 설정 오류였습니다. 항로에서 수백 킬로미터 벗어나 소련 영공으로 진입한 것입니다. 소련은 이를 스파이 비행기로 판단하고 미사일을 발사했습니다.

[그림 11-8] 대한항공 007편 항로 비교

  대한항공 007편 항로:

  예정 항로:     뉴욕 ─── 앵커리지 ─── (북태평양) ─── 서울
  실제 항로:     뉴욕 ─── 앵커리지 ─── (소련 영공) ─── ✕ 격추

  → 항법 장치 설정 오류로 수백 km 이탈
  → 소련 영공 침범 → 격추

이 사건 이후, 미국의 레이건 대통령은 군사용으로만 사용되던 GPS를 민간에 개방하겠다고 발표합니다.5 이런 비극이 다시 일어나지 않도록, 전 세계 민간 항공기가 정확한 위치를 알 수 있게 하겠다는 결정이었습니다.

다만 민간용 GPS에는 의도적으로 오차를 넣었습니다(SA: Selective Availability). 군사적 이유로 민간용 GPS의 정확도를 100m 수준으로 제한한 것입니다. 이 제한은 2000년 클린턴 대통령이 해제하면서, GPS 정확도가 약 10m 이내로 향상됩니다. 현재 스마트폰의 GPS가 이 정도 정확도를 가지는 이유입니다. 여기에 스마트폰은 GPS만 쓰는 것이 아니라 WiFi 신호, 기지국 위치, 가속도 센서까지 조합해서 위치를 보정합니다. 실내에서 GPS 신호가 약해져도 주변 WiFi 공유기의 위치 정보로 대략적 위치를 파악할 수 있는 것은 이 때문입니다.

알쓸신잡

  • GPS는 미국 것이다: GPS는 미국 국방부가 운영하는 시스템입니다. 미국이 마음먹으면 특정 지역의 GPS 신호를 의도적으로 교란하거나 끌 수 있습니다. 그래서 다른 나라들도 자체 위성 항법 시스템을 운영합니다. 러시아의 GLONASS, 유럽의 Galileo, 중국의 BeiDou(북두), 일본의 QZSS. 스마트폰은 보통 이 중 여러 개를 동시에 사용해서 정확도를 높입니다.

  • 포켓몬 GO와 GPS 스푸핑: 2016년 포켓몬 GO가 출시되자, 집에서 편하게 포켓몬을 잡기 위해 GPS 스푸핑(Spoofing) — 가짜 GPS 신호를 보내서 위치를 속이는 것 — 이 유행합니다. 하지만 GPS 스푸핑은 게임에서만 쓰이는 것이 아닙니다. 2017년 흑해에서 약 20척의 선박이 동시에 GPS 위치가 내륙으로 표시되는 사건이 발생했는데, 러시아의 GPS 교란 실험으로 추정됩니다. 군사적 GPS 교란은 실제로 일어나고 있는 현실입니다.

  • 구글 스트리트뷰 WiFi 스캔들: 2010년, 구글 스트리트뷰 촬영 차량이 거리 사진을 찍는 동시에 주변 WiFi 네트워크의 데이터를 수집하고 있었다는 사실이 밝혀집니다. 이메일, 비밀번호, 웹 기록 등 개인 정보가 포함되어 있었습니다. 구글은 “실수“라고 해명했지만, 여러 나라에서 벌금을 부과받았습니다. WiFi 위치 정보 자체는 GPS를 보완하는 유용한 기술이지만(실내에서 GPS가 안 될 때 WiFi로 대략적 위치 파악 가능), 이 사건은 데이터 수집의 경계가 어디인지에 대한 논란을 촉발했습니다.

치킨이 오고 있습니다. 지도에서 배달원의 파란 점이 점점 가까워집니다. 그런데 다음에 배달앱을 열면, 앱이 “이 치킨집 어떠세요?“라고 추천할 겁니다. 내가 치킨을 좋아한다는 걸 어떻게 아는 걸까요? 내 취향을 어떻게 파악하는 걸까요?

  1. 삼변측량(Trilateration): 3개 이상의 기준점으로부터의 거리를 이용해 위치를 결정하는 방법. “삼각측량(Triangulation)“은 각도를 이용하는 것이고, GPS는 거리를 이용하므로 삼변측량이 정확한 표현이다. ↩

  2. 크라우드소싱(Crowdsourcing): 대중(Crowd)에게서 정보나 서비스를 얻는(Sourcing) 것. 위키피디아(대중이 만드는 백과사전), 교통 정보(운전자가 만드는 교통 데이터) 등이 대표적. ↩

  3. 머신러닝(Machine Learning): 기계 학습. 컴퓨터가 데이터에서 패턴을 스스로 학습하여 예측하는 기술. 명시적으로 프로그래밍하지 않아도, 데이터를 많이 줄수록 예측이 정확해진다. ↩

  4. 1983년 9월 1일, 탑승자 269명 전원 사망. — Smithsonian National Air and Space Museum ↩

  5. 사건 2주 후 발표. — Reagan Presidential Library ↩