파이썬_실전 프로젝트

프로젝트 오일러 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?

 

방법 1 : 조합(combination)

고등학교 수학 조합(combination)을 알고계신분은, 코딩도 필요없이, nCr 공식한줄이면 끝납니다. 예제에서 보면 가로로 2번, 세로방향 화살표가 2개씩 총 4개가 있다고 가정할때, 4개 화살표의 자리를 배치하는 경우의 수와 같습니다. 4개중에 2개의 자리를 정하는 문제이므로, 4C2 가 됩니다.

문제도 마찬가지로, 20x20 의 격자는, 세로이동 20번, 가로이동 20번이므로, 총 40개의 이동단위를 순서대로 자리배치하는 경우의 수와 같으므로 40C20 이 됩니다.

 

방법 2 : 사각형 분해

조합을 모르더라도 격자를 작은 사각형으로 차례차례 분해해 가면 계산을 할수 있습니다.

예제의 2x2를 예로 들면, 마지막2,2점의 바로 직전 점은 2,1 과 1,2 점(또는 직사각형) 두개입니다.  2,1 사각형의 경로의 갯수는 3이고, 1,2 사각형의 경로도 3입니다. 그러므로 전체경로는 6입니다.

즉 사각형을 분해해가다가, 가장자리 긴 사각형에 닿았을때 n,1 사각형이나 혹은 1,n 사각형일때 경로의 갯수는 n+1개로 정해집니다.

마찬가지로 3x3 사각형을 예로 들면, 마지막 바로 앞의 두점은 3,2와 2,3 두개이고, 3,2는 다시 3,1과 2,2 의 합입니다.

그러면 3,1은 값이 4이고, 2,2는 앞에서 계산한대로 6입니다.  2,3도 마찬가지로, 2,2와 1,3의 합이고, 각각 6과 4, 합은 10이고, 전체합은 20입니다.

같은 방법으로 문제에 적용하면 20x20 사각형은 20x19 사각형 두개의 경우의 수의 합과 같고, 20x19 는 다시 19x19와 20x18로 분해가 됩니다. 분해를 계속 해가다 보면, 결국은 모두 가장자리에 닿게 되므로, 20x1,19x1,18x1,,, 가장자리 사각형에 도달하게 되고, 각 가장자리 사각형의 경우의 수는 20x1은 21, 19x1은 20 으로 nx1 사각형은 n+1로 정해져 있습니다. 이것을 코드로 표현하면 아래와 같습니다.

 

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

print(grid(2,2))
6

2x2 경로의 갯수는 6입니다.

 

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

print(grid(3,3))
20

3x3 경로의 갯수는 20입니다.

 

이런식으로 20x20을 계산할수 있을것 같긴하나,  한가지 문제점은, 격자의 크기가 늘어날수록 계산량(재귀호출) 기하급수적으로 늘어납니다. 시간을 측정해 봤더니,

grid: 11x11 result:705432 calculation time: 0.4375312328338623
grid: 12x12 result:2704156 calculation time: 1.6407384872436523
grid: 13x13 result:10400600 calculation time: 6.0629260540008545
grid: 14x14 result:40116600 calculation time: 23.345405101776123
grid: 15x15 result:155117520 calculation time: 86.33425712585449

15x15까지 계산을 해봤을때는 약 4배씩 증가하고, 20x20은 대략 88000초,,, 하루가 86400 초니깐,, 24시간이 넘게걸린다는 예상이 나오네요;;,, 물론 제pc가 좀 느리긴 합니다만,,  

속도개선

그래서 약간의 트릭을 써야됩니다. 정방형이기때문에, 대각선(/)을 기준으로 양쪽의 경로가 대칭입니다. 즉 전체 20x20을 다 계산할 필요없이, 각 대각선상의 점들의 경로의 수를 제곱을 해주어서 합산을 하면 전체 경로의 수가 됩니다. 이렇게 하면 24시간이 넘게 걸리던 계산을 1초도 안되서 끝낼수 있습니다.

import time
start_time = time.time()

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
while i<=dim:
    total = total + grid(i,dim-i)**2
    i+=1

print(total)
print("calculation time:",time.time()-start_time)
137846528820
calculation time: 0.5625407695770264

if문에 c==0, r==0 의 조건은 대각선의 가장 끝점에서의 경우의 수를 반환해주기 위해서입니다. 대각선의 가장끝점엔 사각형이 없고, 단 하나의 가장자리 경로만 있기때문에, 반환값은 1입니다.

속도개선 2

앞서 약간의 트릭을 써서 속도를 올리긴 했지만, 문제는 여전히 있습니다. 사각형 격자가 더 커질경우, 결국 또 시간이 늘어납니다. 그 원인은 14번 문제에서도 나왔듯이 중복계산에 있습니다. 14번이나 15번 같은 문제의 해결방법을 알고리즘상으로는 분할정복법(Divide and Conquer)이라고 합니다. 전체문제를 작은단위로 나누어서 반복적으로 계산하면서 문제를 해결하는거죠. 그런데 이 분할정복법의 가장 큰문제가 중복계산에 있습니다. 그래서 이를 해결하는것이 14번 문제에서 썼었던 다이나믹 프로그래밍(Dynamic Programming)입니다.

이 다이나믹 프로그래밍을 15번 문제에도 적용시켜 보도록 하죠.

import time
start_time = time.time()

def grid(r,c):
    if c==0 or r==0:
        return 1
    elif r==1:
        return c+1
    elif c==1:
        return r+1
    elif (r,c) in cache: # 저장된 값이 있는지 확인해서,
        return cache[r,c] # 있으면 그값을 불러내서 리턴함.
    else:
        cache[r,c]=grid(r,c-1)+grid(r-1,c) # 없으면,계산해서 값을 cache에 저장한후
        return cache[r,c] # 저장한 값 리턴.

cache={}  # 중복된 값을 저장하기 위한 변수. 딕셔너리 타입.
grid(20,20)
print(cache[20,20])
print("calculation time:",time.time()-start_time)
137846528820
calculation time: 0.0

요렇게 몇줄만 추가하면, 사각형격자가 100x100을 넘어가도 시간이 거의 1초도 안걸리는것을 볼수 있습니다. 

댓글

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