반응형 최댓값1 프로젝트 오일러 #67 최대 경로의 합 난이도는 5%로 별로 높지 않은 문제입니다. 그러나 A* 알고리즘 등 기초 알고리즘을 이용해서 짤 수 있는 문제이고, 또, 많은 게임 프로그램에서 활용 가능한 문제입니다. Maximum path sum II 어떤 한 곳에서 갈 수 있는 길은 2가지이므로, 높이가 10이면, 2의 9승인 512가지의 길이 존재합니다. 이 길 중 상당부분은 부분경로가 같기 때문에, 이러한 경로의 합을 구하는 방법으로는 동적프로그래밍(dynamic programming)이라는 알고리즘 기법을 이용해서 풀면 좋습니다. 동적 프로그래밍은 메모리를 추가로 사용해야 하지만, 저는 그냥 기존의 데이터 저장공간을 그대로 사용했습니다. 그렇게 하여도 큰 문제가 없겠죠. 중간에 한 지점에 대해서 올 수 있는 경로는 최대 2가지입니다. 그 2.. 2016. 6. 30. 이전 1 다음 728x90
