본문바로가기
[오일러 프로젝트] ★심화문제에 도전!★ 20×20 격자의 왼쪽 위에서 오른쪽 아래로 가는 경로의 수는 몇 가지일까?
수학동아 2021.02.01 07:57

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

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

 

 

까치 까치 설날은 어저께고요~♬ 우리 우리 설날은 오늘~인데도!

코로나19 때문에 집 안에만 있어야 하는 상황이 얄궂습니다.

그나마 ‘윤식당’ 대신 돌아온 예능 프로그램 ‘윤스테이’를 시청하며 여행하는 기분을 느끼는데요,

자, 한번 눈을 감고 우리도 윤스테이에 가는 상상을 해볼까요?

윤스테이가 아니라 가고 싶은 어디든 좋아요! 저는 홍스테이로~♬

 

 

<오일러 프로젝트 15번>

가로세로 모두 2칸인 격자를 생각해 봅시다. 격자 위 선을 따라 왼쪽 위 모서리에서 출발해 오른쪽 아래 모서리까지 가는 길은 모두 6가지가 있습니다. 그렇다면 가로세로 20칸인 격자에는 모두 몇 가지의 경로가 있을까요?

 

격자 안에서 어떤 교차점에 이르는 경로의 수는 그 교차점으로 들어오는 경로들이 가진 숫자를 모두 더한 것과 같습니다. 따라서 격자의 맨 위와 왼쪽 모서리에서 이동하는 가짓수는 모두 1가지이므로 1을 모두 써두고, 두 번째 줄부터 각 점까지 이동하는 횟수를 더해가다 보면 가로 4칸, 세로 3칸의 격자에서 이동하는 경로는 총 35가지라는 것을 알 수 있죠.

 

 

같은 방법으로 20×20 격자에서 경로의 수도 찾을 수 있습니다. 

이 방법을 코딩으로 나타내 문제를 한 번 풀어보겠습니다!

 

 

파이썬 완전정복! '가능한 경로의 수 세기'

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

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

 

1. 파이썬 세상에서 20×20 격자 그리기

아쉽게도 파이썬에서는 가로(행)와 세로(열)가 일정한 길이를 갖는 2차원 배열을 나타낼 방법이 없습니다. 따라서 1차원에서 숫자를 나타내는 방식인 ‘리스트’ 안에 또 다른 리스트를 넣어 나타내볼게요. 예를 들어 가로(행)가 1, 세로(열)가 4인 경우는 아래와 같이 원소 하나짜리 리스트 [0]에 곱셈기호(*)를 써서 나타냅니다.

 

 

다음으로는 가로(행)를 3줄로 늘려보겠습니다. 이때 [0]*4*3으로 하면 될 것으로 생각할 수 있지만, 이 경우에는 [0, 0, 0, 0]이 3개가 될 뿐 각자 다른 원소로 지정되지는 않습니다. 따라서 각각 다른 가로(행)를 만들어주는 아래 명령어를 사용합니다.

 

 

2. 교차점까지 가는 경로의 가짓수 구하기

앞서 보았던 3행 4열짜리 격자를 예로 들어 경로의 수를 구하는 공식을 찾아보겠습니다. 먼저 3행 4열 격자는 교차점의 개수를 생각하면 4행 5열로 늘어납니다.

 

 

그리고 앞서 경로의 가짓수를 구했던 것처럼 맨 위와 왼쪽 가장자리의 교차점 값을 1로 두고, 위에서부터 차례대로 왼쪽 숫자와 위 숫자를 더해 교차점까지 가는 경로의 수를 구해야 합니다. 따라서 맨 왼쪽 위 교차점이 0행, 0열이라고 할 때 r번째 행, c번째 열의 교차점까지 가는 경로의 수는 r번째 행, c-1번째 열의 값과 r-1번째 행, c번째 열의 값을 더한 것과 같으므로 아래와 같은 코드로 나타냅니다.

 

 

 

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

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

 

 

#1 MN열의 격자에 대해 15번 문제를 해결하는 함수를 정의합니다.

#2 MN열의 격자에 있는 교차점은 (M+1)행, (N+1)열의 크기를 갖습니다. 이때 만들어진 교차점의 행렬을 만들고 ‘arr’이라고 둡니다.

#3, 4 리스트의 정보는 0번부터 시작하기 때문에 격자의 맨 위와 왼쪽 가장자리를 0번째 원소라고 합니다. 앞에서 경로의 가짓수를 구한 것처럼 각 행의 0번째 원소와 각 열의 0번째 원소의 교차점 값을 모두 1로 둡니다.

#5, 6, 7 바로 위와 왼쪽의 숫자를 더해가면서 각 행과 열의 교차점까지 가는 경로의 수를 구합니다. 이때 맨 위와 왼쪽 가장자리의 값은 모두 1로 정해져 있기 때문에, ‘for문’의 시작은 0번째 행, 열이 아니라 1번째 행, 열부터 시작합니다.

#8 M+1행 N+1열에 있는 오른쪽 아래 교차점까지 가는 경로의 수를 구합니다.

#9 MN이 20일 경우에 대해 실행해 15번 문제의 답을 얻습니다.

 

 

BONUS 오일러 퀴즈

오일러 프로젝트 15번 문제를 폴리매스 홈페이지에서 풀어보고, 다음 예제 문제에도 도전해보세요!

 

1. 20×20 격자에서 10×10 위치의 교차점을 반드시 지나는 최단 경로의 가짓수를 구해보자.

Hint. 10×10 교차점까지 가는 경로의 수와 10×10 교차점에서 20×20 교차점까지 가는 경로의 수를 곱한다.

 

 

☆★폴리매스에서만 공개되는 심화 문제★☆

3×4 격자에서 최단 경로를 구하려면 오른쪽으로 4번, 아래쪽으로 3번을 꼭 이동해야 한다.

‘→’ 4개와 ‘↓’ 3개를 늘어놓는 가짓수를 구해 가능한 최단 경로의 수를 구해보자.

Hint. 같은 것들을 나열하는 방법의 가짓수를 구하는 순열을 이용한다.

 

심화 문제를 풀어 답을 남겨주신 분들께는 특별한 선물을 드려요!

과연 스페셜~한 선물의 주인공은 누구?!

 

  •  
    원형파이 Lv.9 2021.02.01 23:32 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      홍아름 기자 Lv.3 2021.02.24 17:20

       

      원형파이 친구! 심화 문제를 풀어줘서 고마워요~^^

      비밀댓글로 이름과 연락처, 주소를 남겨주면 선물 보내드릴게요~! 고마워요~~

       

      좋아요0
  •  
    빅수비 Lv.11 2021.02.08 12:54

    기자님 혹시 muse님이 주최하는 pmcc 참가할 생각은 없으신가요?

    http://www.polymath.co.kr/contents/view/29280?page=2

    댓글 작성하기 좋아요0 댓글수1
    •  
      홍아름 기자 Lv.3 2021.02.24 17:19

       

      빅수비 친구! 답이 너무 늦었죠ㅠㅠ

      제 코딩 실력이 아직 많이 부족해서 열심히 배워보고 다음 기회에 참가해볼게요!

      늦게 답 줘서 미안해요ㅠㅠ

       

       

      좋아요0
  •  
    빅수비 Lv.11 2021.02.08 13:00 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      홍아름 기자 Lv.3 2021.02.24 17:20

       

      빅수비 친구! 짝짝짝~ 정답이에요~!

      비밀 댓글로 이름과 연락처, 주소를 남겨주면 제가 준비한 선물 보내드릴게요! 고마워요~~

       

      좋아요0
    •  
      빅수비 Lv.11 2021.02.24 17:53 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    원형파이 Lv.9 2021.02.24 19:14 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911