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?
[출처 - projecteuler.net/]
이번 문제는 start 부터 end까지 가는 길의 경우의 가지 수를 구하는 문제가 되겠습니다. 그래도 중구난방에 장애물도 있고 그런 문제는 아니고... 그냥 정사각형의 grid에서 왼쪽꼭대기에서 오른쪽 바닥까지 이동하는 길의 가지 수 입니다. 다만 모든 길은 우/하 (즉 오른쪽 or 아래)로만 이동이 가능한 제약이 있습니다.
예시에서는 2 x 2라서 금방 확인이 가능하지만... 진정으로 원하는 문제는 20 x 20에 대한 결과를 도출하는 문제가 되겠습니다. 아무래도 알고리즘을 접해보신 분들은 바로 Dynamic Programming을 생각하셨을 것 같습니다. 왜냐하면 줄줄이 타고 내려오면서 현재 자신의 위치에서 내려갈 수 있는 방법은 동일하기 때문에 해당 위치에서의 길을 찾아갈 수 있는 방법을 memoization을 해 놓는다면 연산이 획기적으로 줄어들 수 있기 때문입니다.
뭐 이것도 결국은 Dynamic Programming 이겠죠....^ ^
이렇게 3가지의 경우... start점에서 우/하 방향으로 계속내려오다가 빨간색 점에 도착했을때는... 더이상 진행하지 않고 2가지가 있다고 인지하면 계산을 종료하면 됩니다. 이게 20 x 20이 된다해도 로직은 똑같습니다. End지점부터 역으로 각 위치의 가지수가 구해진다면 아무리 커져도 연산은 크지 않게 되는 것이지요.
저는 Memoization을 사용하고, 그냥 loop로 구현을 해보겠습니다. 자세한 내용은 아래 Basic으로 확인해 보겠습니다. 아무래도 해당 로직이 최선이라고 생각되어 Advance는 없습니다.
1. Basic
위에서 간단히 알아본 Dynamic Programming의 방식을 잘 살펴보면 아래의 로직을 발견할 수 있습니다. 결국 해당 지점에서 End로 가기위한 방법은... 해당 지점에서 이동할 수 있는 위치인 오른쪽의 위치와, 아래쪽의 위치에서 End 지점으로 가기위한 방법의 합과 같다.
그림으로 보면...
다음과 같습니다. 해당 위치에 해당하는 빨간점은... 내가 이동이 가능한 위치에 해당하는 파란점들의 합으로 구할 수 있는 것입니다. 그렇다면 어떻게 최적화하여 구할 수 있을까요?? 제가 생각한 방법은 간단합니다.
단순히 End부터 시작하여 Start방향으로, 즉 역방향으로 순희를 진행하고 그 위치에서 이동이 가능한 우/하 방향의 결과 값을 더하는 방식입니다. 그리고 최종적으로 start의 결과를 확인하면 그것이 Start부터 End로 이동할 수 있는 모든 경우의 가지 수라고 보면 되는 것입니다.
그럼 코드로 확인해 보면 아래와 같습니다.
[소스코드]
import time
if __name__ == '__main__':
size = int(input())
start = time.time()
# 실제 Grid 크기와 길의 개수는 1개가 차이가 남
size += 1
# Memoizaation을 위한 변수 생성
mem = []
for i in range(size):
mem.append([0]*size)
# End Point의 결과 Memoization 초기화
mem[size-1][size-1] = 1
# Grid를 거꾸로 돌려서 생각하면 구현이 편하겠지만, 시각화를 위해서 역으로 돌리겠습니다.
for i in range(size):
for j in range(size):
if i == 0 and j == 0: continue
temp = 0
if size-j != size: temp += mem[size-i-1][size-j]
if size-i != size: temp += mem[size-i][size-j-1]
mem[size-i-1][size-j-1] = temp
# 결과 mem 출력
for i in range(size):
print(mem[i])
print("정답 : ", mem[0][0])
end = time.time()
print("소요시간 : ", end - start)
주의할 점은... mem의 End위치에 해당하는 값에 대해서 1로 초기화가 필요하고, 연산 loop를 구현시 mem의 위치를 벗어나는 값이 들어올 경우 이를 무시하고 진행하는 부분도 주의하면 결과는 무난히 도출이 됩니다.
[결과]
[137846528820, 68923264410, 33578000610, 15905368710, 7307872110, 3247943160, 1391975640, 573166440, 225792840, 84672315, 30045015, 10015005, 3108105, 888030, 230230, 53130, 10626, 1771, 231, 21, 1]
[68923264410, 35345263800, 17672631900, 8597496600, 4059928950, 1855967520, 818809200, 347373600, 141120525, 54627300, 20030010, 6906900, 2220075, 657800, 177100, 42504, 8855, 1540, 210, 20, 1]
[33578000610, 17672631900, 9075135300, 4537567650, 2203961430, 1037158320, 471435600, 206253075, 86493225, 34597290, 13123110, 4686825, 1562275, 480700, 134596, 33649, 7315, 1330, 190, 19, 1]
[15905368710, 8597496600, 4537567650, 2333606220, 1166803110, 565722720, 265182525, 119759850, 51895935, 21474180, 8436285, 3124550, 1081575, 346104, 100947, 26334, 5985, 1140, 171, 18, 1]
[7307872110, 4059928950, 2203961430, 1166803110, 601080390, 300540195, 145422675, 67863915, 30421755, 13037895, 5311735, 2042975, 735471, 245157, 74613, 20349, 4845, 969, 153, 17, 1]
[3247943160, 1855967520, 1037158320, 565722720, 300540195, 155117520, 77558760, 37442160, 17383860, 7726160, 3268760, 1307504, 490314, 170544, 54264, 15504, 3876, 816, 136, 16, 1]
[1391975640, 818809200, 471435600, 265182525, 145422675, 77558760, 40116600, 20058300, 9657700, 4457400, 1961256, 817190, 319770, 116280, 38760, 11628, 3060, 680, 120, 15, 1]
[573166440, 347373600, 206253075, 119759850, 67863915, 37442160, 20058300, 10400600, 5200300, 2496144, 1144066, 497420, 203490, 77520, 27132, 8568, 2380, 560, 105, 14, 1]
[225792840, 141120525, 86493225, 51895935, 30421755, 17383860, 9657700, 5200300, 2704156, 1352078, 646646, 293930, 125970, 50388, 18564, 6188, 1820, 455, 91, 13, 1]
[84672315, 54627300, 34597290, 21474180, 13037895, 7726160, 4457400, 2496144, 1352078, 705432, 352716, 167960, 75582, 31824, 12376, 4368, 1365, 364, 78, 12, 1]
[30045015, 20030010, 13123110, 8436285, 5311735, 3268760, 1961256, 1144066, 646646, 352716, 184756, 92378, 43758, 19448, 8008, 3003, 1001, 286, 66, 11, 1]
[10015005, 6906900, 4686825, 3124550, 2042975, 1307504, 817190, 497420, 293930, 167960, 92378, 48620, 24310, 11440, 5005, 2002, 715, 220, 55, 10, 1]
[3108105, 2220075, 1562275, 1081575, 735471, 490314, 319770, 203490, 125970, 75582, 43758, 24310, 12870, 6435, 3003, 1287, 495, 165, 45, 9, 1]
[888030, 657800, 480700, 346104, 245157, 170544, 116280, 77520, 50388, 31824, 19448, 11440, 6435, 3432, 1716, 792, 330, 120, 36, 8, 1]
[230230, 177100, 134596, 100947, 74613, 54264, 38760, 27132, 18564, 12376, 8008, 5005, 3003, 1716, 924, 462, 210, 84, 28, 7, 1]
[53130, 42504, 33649, 26334, 20349, 15504, 11628, 8568, 6188, 4368, 3003, 2002, 1287, 792, 462, 252, 126, 56, 21, 6, 1]
[10626, 8855, 7315, 5985, 4845, 3876, 3060, 2380, 1820, 1365, 1001, 715, 495, 330, 210, 126, 70, 35, 15, 5, 1]
[1771, 1540, 1330, 1140, 969, 816, 680, 560, 455, 364, 286, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1]
[231, 210, 190, 171, 153, 136, 120, 105, 91, 78, 66, 55, 45, 36, 28, 21, 15, 10, 6, 3, 1]
[21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
정답 : 137846528820
소요시간 : 0.0019998550415039062소요시간은 0.002초 정도로 매우 빠르게 연산이 됩니다. 아무래도 가혹한 상황을 고려한다고 하더라도... 무난히 해결되지 않을까 생각됩니다.
- Ayotera Lab -
댓글