본문바로가기
[오일러 프로젝트] 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 100만 번째 사전식 순열은?
수학동아 2021.04.01 16:59 조회 456

코.알.못 홍 기자의 코딩 도전기

코딩(프로그래밍)의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갑니다. 오일러 프로젝트는 수학과 코딩 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트입니다. 홍 기자와 함께한다면 수학과 코딩 언어의 하나인 파이썬 모두 정복할 수 있지 않을까요?

 

 

예능 프로그램 ‘뭉쳐야 쏜다’는

다양한 스포츠 종목에서 국가대표로 활약했던 12명의 전설을 모아 농구대결을 합니다.

각자 분야에서는 금메달감이지만 모여서 농구를 하면 이상하게 패하기 일쑤라

“모이면 (겨우) 1승, 흩어지면 12승”이라 말할 정도죠.

그렇다면 만약 국가대표 대신 전설의 레전드 수학자 10명이 모여 농구 경기를 하면 어떨까요?

과연 ‘LEGEND IS BACK?’일지?

 

 

<오일러 프로젝트 24번>

어떤 대상에서 전부 혹은 일부를 골라 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 0, 1, 2로 만들 수 있는 순열에는 210, 021 등이 있습니다. 그리고 만든 순열을 숫자나 문자를 정렬하는 기준에 따라 늘어놓은 것을 ‘사전식 순열’이라고 하며 0, 1, 2로 만들 수 있는 모든 순열을 사전식으로 배열하면 012, 021, 102, 120, 201, 210과 같습니다.

그렇다면 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 100만 번째 순열은 무엇일까요?

 

지금 바로 떠올릴 수 있는 수학자 10명이 농구를 하는 모습은 어떨까요? 시간 순서대로 수학자들에 0번부터 9번까지 번호를 매기고, 오일러 프로젝트 24번 문제의 답에 따라 수학자들을 두 팀으로 나눠보려고 하는데요, 어떻게 해야 답을 구할 수 있을까요?

 

 

파이썬 완전정복! '362만 8800개의 모래알 사이에서 진주 찾기'

24번 문제를 해결하는 데 필요한 파이썬 명령어입니다.

꿀팁 중의 꿀팁, 밑줄 쫙! 핵심만 소개하니 꼭 익혀두세요!

 

1. 1부터 n까지 자연수를 곱하는 팩토리얼(!)로 경우의 수 나타내기

0부터 9까지의 수를 나열하는 방법은 362만 8800가지입니다. 이는 10개부터 1개까지 점차 줄어드는 경우의 수를 곱한 것으로 마지막 수인 10을 써서 10!로 나타내지요. 그렇다면 이중에서 0으로 시작하는 수는 몇 개일까요? 가장 앞의 숫자가 고정돼 있으니 0 다음으로 올 수 있는 숫자의 가짓수인 9에 8, 7, 6, 5, 4, 3, 2, 1을 곱한 9!입니다. 이렇게 앞에서부터 숫자를 하나씩 정할 때마다 가능한 순열의 가짓수는 팩토리얼에서 수를 하나씩 낮춘 값과 같습니다.

 

 

파이썬에서 팩토리얼은 math 모듈의 팩토리얼(factorial) 함수를 가져와 나타냅니다. 예를 들어 9!은 factorial(9)로 나타내죠.

 

 

2. 가능한 경우의 수를 고려해 100만 번째 순열 찾기

이제 팩토리얼 값을 이용해 100만 번째 순열을 찾습니다. 예를 들어 0으로 시작하는 순열은 36만 2880(=9!)개입니다. 1 또는 2로 시작하는 순열 역시 각각 36만 2880가지로 같죠. 첫 자리가 0 또는 1인 순열의 가짓수는 총 72만 5760(=36만 2880×2)가지이고, 첫 자리가 0 또는 1, 2인 순열의 가짓수는 총 108만 8640(=36만 2880×3)가지입니다. 따라서 100만 번째 순열은 이 사이에 있어야 하므로 2로 시작한다는 걸 예상할 수 있죠. 이렇게 자릿수를 구하는 방식은 아래와 같은 코드로 나타냅니다.

 

 

 

도전! 오일러 프로젝트 24번 문제 뽀개기

* 코딩 언어는 Python으로 두고 실행하세요!

 

 

#1, 2, 3, 4 math 모듈을 실행해 팩토리얼 함수를 불러온 뒤, 100만 번째 순열의 맨 앞자리 수를 구하는 코드를 실행합니다. 결과로 몫은 2, 나머지는 27만 4239가 나오므로 첫 번째 자릿수는 0번째 항부터 시작하는 리스트의 규칙에 따라 2번째 항인 2입니다.

#5, 6, 7 100만 번째 수열의 맨 앞 자릿수가 2이므로 리스트에서 2를 지우고, 앞서 구한 나머지인 27만 4239를 8!로 나눈 몫과 나머지를 구합니다. 몫은 6이므로 리스트에서 6번째 항인 7이 100만 번째 수열의 두 번째 자릿수입니다.

#8, 9, 10 두 번째 자릿수인 7을 리스트에서 지우고, 앞서 구한 나머지 3만 2319를 7!로 나눈 몫과 나머지를 구합니다. 몫은 6이므로 리스트에서 6번째 항인 8이 세 번째 자릿수입니다. 나머지가 0이 나올 때까지 반복해 100만 번째 수열을 구합니다.

 

★ 같은 방식으로 코드를 더 작성해 답을 구해보세요! ★

 

 

BONUS 오일러 퀴즈

오일러 프로젝트 24번 문제를 풀어보고, 다음 예제 문제에도 도전해보세요!

 

1. 위의 코드를 응용해 200만, 300만 번째 순열의 값을 구해보자.

 

2. 24번 문제는 몫과 나머지를 구하는 방식을 더 간결하게 표현한 코드로 해결할 수 있다. 어떤 것이 가능할지 생각해보자.

 

 

저는 피타고라스와 에우클레이데스(유클리드), 라이프니츠, 라그랑주, 가우스, 뫼비우스, 아벨, 갈루아, 푸앵카레, 힐베르트의 순으로 0~9번까지 번호를 매겼는데요, 24번 문제의 답을 따라 팀을 나눴더니 라이프니츠, 갈루아, 푸앵카레, 라그랑주, 힐베르트가 한 팀, 그리고 유클리드, 뫼비우스, 가우스, 아벨, 피타고라스 순으로 한 팀이 됐습니다. 그럼 24번의 답이 무엇인지 대충 예상할 수 있겠죠? 한번 맞혀보세요!

 

  •  
    julie Lv.3 2021.05.29 12:15 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911