반응형 경로 구하기1 18. 프로젝트 오일러 #18 : 삼각형 수들의 최대값 경로 구하기 이번 프로그램은 개인적으로도 재미있을 것 같았습니다. 가장 중요한 알고리즘은 바로 동적 프로그래밍(Dynamic Programming)입니다. 실제 경로 문제 중 최적값 찾기에는 동적 프로그래밍 기법을 자주 사용하게 되는데, 이 프로그램 역시 마찬가지입니다. 해당 사이트 문제에서도 그런 점을 언급하기는 했지만, 동적 프로그래밍을 사용하지 않는다면, 경로의 수가 많은 경우에는 매우 많은 연산을 하게 됩니다. 이번 문제는 경로의 수가 16,384가지가 나옵니다. 왜냐하면 각 층의 숫자마다 경로가 2가지씩 나오니까요. 총 15층이므로, 총 경로의 수는 가 됩니다. 그러나 동적 프로그래밍을 이용하면, 실제 경로의 수 계산은 총 숫자의 갯수인 120가지밖에 안 됩니다. #67 문제에 100층짜리 문제가 나온다고 .. 2015. 1. 14. 이전 1 다음 728x90
