파이썬_실전 프로젝트

프로젝트 오일러 15번문제 - 경로의 갯수

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

 

격자의 끝에서 끝으로 이동하는 경로의 갯수를 구하는 문제입니다. (모바일에서, 그림이 안보이시면 새로고침 한번 해주시면 됩니다.)

해결 방법은, 조합(combination)을 알고계신분은, 코딩도 필요없이, nCr(40C20) 공식한줄이면 끝납니다.

또는 같은 조합문제라도, nCr 계산을 공식이 아니라, 프로그래밍로 계산할수도 있습니다. nC0=1, nC1=n 이라는 성질을 이용해서, 함수의 재귀호출이나 무한루프를 이용해서 계산하는 방법입니다.

def combination(n1,n2):
    if n2==0:
        return 1
    elif n2==1:
        return n1
    elif n1==n2*2:
        return combination(n1-1,n2-1)*2
    else:
        return combination(n1-1,n2)+combination(n1-1,n2-1)

print(combination(40,20))

위의 재귀호출 형식의 코드로 20x20 격자를 계산하는데 제 느린컴퓨터로 20분정도 걸렸습니다. 최신 컴퓨터로는 좀더 빠를지는 몰라도, 썩 좋은 코드는 아닌거 같습니다.

좀더 빠르게 계산하는 방법은, 격자 전체를 다 계산할 필요없이, 대각선(/)을 기준으로 양쪽의 경로의 갯수가 같기 때문에, 시작점에서 대각선의 점까지만 계산해서 제곱을 한후에, 합산을 하면 됩니다.

def grid(r,c):
    if c==0 or r==0:
        return 1
    elif r==1:
        return c+1
    elif c==1:
        return r+1
    else:
        return grid(r,c-1)+grid(r-1,c)

i=0;dim=20;total=0  #20x20 이라는 의미로, dim값ㅇ르 20으로 설정.
while i<=dim:
    grid_sum=0
    print('grid:',i,dim-i)  
    grid_sum=grid(i,dim-i)**2  #함수리턴값을 제곱해서 합산.
    print(grid_sum)
    total = total + grid_sum
    i+=1

print(total)

결국, 조합문제를 몰라도, 격자를 끝에서부터(혹은 대각선상의 점에서부터) 역으로 분해해 가면, 삼각수열(12번문제)과 비슷한 패턴이 나오기 때문에, 반복적인 계산이나 재귀호출을 통해서 풀수 있습니다.

댓글

댓글 본문
작성자
비밀번호
버전 관리
노마드
현재 버전
선택 버전
graphittie 자세히 보기