Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 3월 1일 목요일

[Project Euler] 18. 삼각형을 따라 내려가면서 합이 최대가 되는 경로 찾기

18. 삼각형을 따라 내려가면서 합이 최대가 되는 경로 찾기
다음과 같이 삼각형 모양으로 숫자를 배열했습니다.

3
7 4
2 4 6
8 5 9 3

삼각형의 꼭대기부터 아래쪽으로 인접한 숫자를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23 이 가장 큰 합을 갖는 경로가 됩니다.

다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

참고: 여기서는 경로가 16384개밖에 안되기 때문에, 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다.
하지만 67번 문제에는 100층짜리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.
Click

작은 값을 구하는 거였으면 중간에 가지를 칠 수 있는 깊이 우선 탐색도 괜찮을 듯 하지만 최대값을 구하는 것이므로 어차피 전 노드를 탐색해야 하여 넓이 우선탐색을 이용했습니다.

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.
더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

( i, 0 )까지의 합 = ( i, 0 )의 값 + ( i-1, 0 )까지의 합.
 ( i, i )까지의 합 = ( i, i )의 값 + ( i-1 ,i-1 )까지의 합.
( i, j )까지의 합 = ( i, j )의 값 + [ { (  i-1, j-1 )까지의 합 } 또는 { ( i-1, j ) 까지의 합 } 중 큰 수 ] 라는 원칙에 의해 간단 탐색 구현.
<script>
/* 삼각형을 탐색하며 최대 값을 구함.
 * @param {Object} n : 삼각형의 층수.
 * @param {Object} nums : 삼각형이 저장 된 배열.
 */
function maxTriangleCourse(n, nums){
 //탐색을 하며 더한 값을 저장할 배열.
 var sum = new Array();
 
 //탐색. 
 sum[0] = new Array();
 sum[0][0] = nums[0][0];
 for(var i=1; i<n; i++){
  sum[i] = new Array();
  //(i,0)까지의 합. = (i,0) + (i-1,0)까지의 합. 
  sum[i][0] = sum[i-1][0] + nums[i][0];
  //(i,i)까지의 합. = (i,i) + (i-1,i-1)까지의 합.
  sum[i][i] = sum[i-1][i-1] + nums[i][i];
  for(var j=1; j<i; j++)
   /*(i,j)까지의 합. = (i,j) + (((i-1,j-1)까지의 합),
    ((i-1,j)까지의 합) 중 큰 수.)*/
   sum[i][j] = nums[i][j] 
    + ((sum[i-1][j-1]>sum[i-1][j])?sum[i-1][j-1]:sum[i-1][j]);
 }
 //max 값 구함.
 var max = 0;
 for(var i in sum[n-1])
  max = (max>sum[n-1][i])?max:sum[n-1][i];
 
 return max;
}
</script>
그런데 구현을 하고나니 댓글을 다신 분들 중에 아래서 부터 탐색을 하신 분이 계시더군요.
해당 방법으로 하면 위에 방법에 비해 최종 max값을 비교하는 과정이 빠지게 되어 더 빠를 수 있겠네요.
그래서 이 방식도 구현해 봤습니다.
<script>
/* 삼각형을 역으로 탐색하며 최대 값을 구함.
 * @param {Object} n : 삼각형의 층수.
 * @param {Object} nums : 삼각형이 저장 된 배열.
 */
function maxTriangleCourseInverse(n, nums){
 //탐색을 하며 더한 값을 저장할 배열.
 var sum = new Array();
 
 //가장 아래 층 초기화.
 sum[n-1] = new Array();
 for(var i in nums[n-1])
  sum[n-1][i] = nums[n-1][i];
 
 //역탐색.
 for(var i=n-2; i>=0; i--){
  sum[i] = new Array();
  for(var j=0; j<=i; j++)
   /*(i,j)까지의 합. = (i,j) + (((i+1,j)까지의 합),
    ((i+1,j+1)까지의 합) 중 큰 수.)*/
   sum[i][j] = nums[i][j]
    + ((sum[i+1][j]>sum[i+1][j+1])?sum[i+1][j]:sum[i+1][j+1]);
 }
 return sum[0][0];
}
</script>

댓글 없음:

댓글 쓰기