주메뉴바로가기 본문바로가기
닫기

part 4. 무한히 많은 도시 여행하기

여기서 문득 방문하고 싶은 도시가 10만 개라면 어떻게 해야 할 지 궁금해졌습니다. 지금까지 최고 기록은 8만 5900개 도시를 방문하는 거였으니까요. n개의 도시를 여행하는 외판원 문제는 ‘NP-완전’이에요. 어쩌면 n의 다항식 꼴로 표현되는 특정 횟수(다항 시간) 안에 풀 수 있는 방법이 없을 수도 있지요...(계속)
글 : 조혜인 수학동아 heynism@donga.com
도움 : 이희상(성균관대학교 기술경영전문대학원장)
도움 : 이상호(이화여자대학교 컴퓨터공학과 교수)

수학동아 2018년 12호
이전
다음
1
수학동아 2018년 12호 다른추천기사
이 기사를 읽은 분이 본
다른 인기기사는?
수학자들이 병원에 간 이유는? “질병 문제 함께 풀어요”
Intro. 조선시대 최석정의 마방진
[수학뉴스] 상어 피부비늘의 비밀, 튜링의 방정식으로 풀었다
[전지적 수학 시점] 메이플스토리, 내분점으로 방어율을 뚫어라!
[엄상일 교수의 따끈따끈한 수학] 조르당 곡선에서 정사각형을 찾아라! 내접 사각형 문제
  • 동아사이언스 바로가기
  • 과학동아 사이언스보드 바로가기
  • 어린이과학동아 어린이수학동아 바로가기
  • 폴리매스 바로가기
  • DS스토어 바로가기
  • 디라이브러리 바로가기
  • 과학동아천문대 바로가기
  • ㈜동아사이언스 | 등록번호 : 서울 아04396 | 등록일자 : 2017년 3월 2일 | 제호 : 동아사이언스 | 발행인 : 장경애 | 편집인 : 김민수
  • ㈜동아사이언스 디라이브러리 | 대표 : 장경애 | 개인정보관리책임자 : 최수정(privacy@dongascience.com) | 청소년보호책임자 : 신한식
  • 서울시 용산구 청파로 109, 7층 (04370) ｜ 문의 : 02-6749-2000 ｜팩스 : 02-3148-0789 ｜사업자등록번호 : 101-81-62201 (사업자정보확인)
  • 통신판매업신고번호 : 제2013-서울용산-01101호 ｜온라인 결제를 위한 PG사의 구매안전서비스(가입사실 확인)
  • Copyright © Dongascience. All right reserved.

  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911