격자의 끝에서 끝으로 이동하는 경로의 갯수를 구하는 문제입니다. (모바일에서, 그림이 안보이시면 새로고침 한번 해주시면 됩니다.)
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: # row값이 1인, 위쪽 사각형에 닿았을때
return c+1 # 그때의 column+1 을 반환
elif c==1: # 마찬가지로 가장왼쪽 사각형에 도달했을때
return r+1 # row+1 을 반환
else:
return grid(r,c-1)+grid(r-1,c) # 가장자리 사각형이 아니면 재귀호출
print(grid(2,2))
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))
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까지 계산을 해봤을때는 격자크기가 1씩 들어날때마다 약 4배씩 증가하고, 대충 예상을 해보면, 20x20은 88000초 정도,,, 하루가 86400 초니깐,, 24시간이 넘게걸린다는 예상이 나오네요;;,, 물론 제pc가 좀 느리긴 합니다만,, ㅎㅎ
속도개선1
그래서 일단은 눈에 보이는 중복계산을 제거해서 속도를 좀 올려보죠. 정방형이기때문에, 대각선(/)을 기준으로 양쪽의 경로가 대칭입니다. 즉 전체 20x20을 다 계산할 필요없이, 각 대각선상의 점들의 경로의 수를 제곱을 해주어서 합산을 하면 전체 경로의 수가 됩니다. 이렇게 하면 제 pc로 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)
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초도 안걸리는것을 볼수 있습니다.
