💬 SOFTWARE 004

022 최단거리 여행 [외판원 문제]

---

복잡도(Complexity)

• 지수 알고리즘(exponential)

  • 모든 가능한 경우를 하나씩 시도해 봐야만 하는 상황에서 발생

  • 지수 복잡도, 실생활에서 자주 등장하지만 효율이 특히 낮고 중요

  • 적의 공격을 방지하는 암호기법에서 사용

---

P / NP

• P

  • 쉬운 문제는 복잡도 면에서 다항

  • 다항(Polynomial)을 의미하는 P

• NP

  • 실제로 발생하는 많은 문제나 그런 문제들의 근본이 되는 문제를 해결하려면 지수 알고리즘이 필요

  • 이러한 문제는 다항 알고리즘으로는 풀 수 없음

  • 비결정적 다항(Nondeterministic Polynomial)을 의미하는 NP

  • 대표적인 문제가 여행하는 외판원 문제(traveling salesman problem)

    • 각 도시를 중복 없이 정확히 1번씩만 방문하고, 전체 여행한 거리를 최소로 만드는게 목적

    • 가능한 모든 해법을 완전 탐색하는 것보다 더 효율적으로 풀 방법이 없음

  • 컴퓨터과학자가 말하는 복잡도란 대부분 최악의 경우(worst case)에 대한 것이지만 보통은 최악의 경우까지 가지 않음

  • 반면, 암호 시스템 같은 일부 중요한 응용 분야는 특정 문제는 정말로 풀기 어려울 것이라는 믿음에 기반하여 단기적으로는 실효성이 없어 보이는 공격이라도, 그 공격에 반격해 내는 건 대단히 중요함

---

023 📝요약

---

✔ 데이터의 양과 관련해서 실행 시간을 표현하는 아이디어는 얼마나 빨리 계산할 수 있는가에 대한 생각을 정제한 결과임 [$$O(N)$$, $$O(logN)$$, $$O(N^2)$$, $$O(NlogN)$$ 등]

✔ 알고리즘과 복잡도 연구는 컴퓨터과학의 주요 영역으로 근본적으로 새롭고 더 나은 계산 방법을 찾아냄

✔ 압축/오류 검출/수정 알고리즘, 암호 기법, 검색 엔진 알고리즘(수집/조직화/검색), 음성 이해/얼굴과 영상 인식/언어의 기계 번역 등의 많은 영역에서 알고리즘은 중요함

---