🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- DP 없이 풀었다
코드
function solution(triangle) { if(triangle.length === 1) return triangle[0][0]; for(let i = triangle.length - 1; i >= 0; i--) { for (let j = 0; j < triangle[i].length - 1; j++) { const temp = Math.max(triangle[i][j], triangle[i][j + 1]); triangle[i - 1][j] += temp; } } return triangle[0][0]; }
정은
구현
코드
function solution(triangle) { let answer = [[triangle[0][0]]]; for (let level=1; level<triangle.length; level++) { answer[level] = []; for (let j=0; j<=level; j++) { if (j === 0) { //맨 왼쪽 원소는 부모 하나 answer[level].push(triangle[level][j]+answer[level-1][0]) } else if (j === level) { //맨 오른쪽 원소는 부모 하나 answer[level].push(triangle[level][j]+answer[level-1][level-1]) } else { //중간에 있는 원소는 위에 부모 두개 중 큰 것이 진짜 부모 answer[level].push(triangle[level][j]+Math.max(answer[level-1][j-1],answer[level-1][j])) } } } return Math.max(...answer[answer.length-1]); }
- 시행착오 2
종혁
구현
- 대각선 왼쪽 - 오른쪽으로밖에 이동하지 못함
dp[i][j]- i 높이에 있는 j번째 원소를 선택했을 경우 이 원소까지 오는 여러 경로중에서 가장 큰 값- -
dp[i-1][j-1]/dp[i-1][j]중에서 더 큰 값 +[i][j]원소 값 더하기 - 7 - 3 - 8 - 7 - 5 순서로 오는 것이 정답
- 두번째 줄의 8의 경우에는 3에서 내려오는 경우밖에 없음 - 3의 경우 7에서 내려오는 경우밖에 없음
- 8을 거치는 최적의 경로는 7 - 3 - 8 : 18
- 두번째 줄의 1의 경우에는 7 - 3 - 1 or 7 - 8 - 1 밖에 없음
- 그렇다면 두번째 줄의 1을 거치는 최적의 경로는 7 - 8 - 1 이 됨 : 16
- 두번째 줄의 0을 거치는 경우는 7 - 8 -0 밖에 없음 : 15
- 굳이 dp 배열을 다시 만들지 않고 원본 배열을 변경하는 것이 더 효율적
높이가 3이었다면 → 정답은 저 셋중 가장 큰값인 18이 됨
높이가 4였다면 → 높이가 3일때 구해놓은 최적의 경로로 왔을 때의 누적합 + 3일때의 마지막 도착지에서 이동할 수 있는 원소로 간 결과 중 가장 큰 값
Ex) 7 - 3 - 8이 3번째 높이까지의 최적의 경로인데 → 8이 갈 수 있는 곳은 2 , 7밖에 없음 → 2로 이동하면
dp[4][0] = 7 + 3 + 8 + 2 코드
function solution(triangle) { for(let i = 1 ; i < triangle.length; i += 1) { for (let j = 0; j <triangle[i].length; j += 1){ triangle[i][j] += Math.max(triangle[i - 1][j - 1] || 0, triangle[i - 1][j] || 0); }; }; return Math.max(...triangle[triangle.length - 1]); }
재웅
구현
- 작은 연산으로 큰 연산을 만들 수 있는 방법을 생각해보았음
- 트리를 역으로 올라가며 두 수 중 큰 값을 상위 요소와 더하는 식으로 진행, 결국 최상단 트리 값은 최대값이 됨
코드
function solution(triangle) { const length = triangle.length for(let i=length-2;i>=0;i--){ for(let j=0;j<triangle[i].length;j++){ triangle[i][j] += Math.max(triangle[i+1][j],triangle[i+1][j+1]) } } return triangle[0][0] } // i줄에 j번째 숫자라면, i+1줄에 j와 j+1에만 접근할 수 있음 // 피보나치? 바닥부터 올라가며 둘 중 큰 수와 윗층 수를 더해감
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
DP 개념을 다시 봐야겠다!
정은
- 시행착오1 (재귀 → 시간초과)
- 시행착오 2 (한 숫자당 밑에 줄 원소를 두개씩 담는 식으로 진행 → X)
- 이렇게 하면 각 줄의 원소 개수보다 더 많아지게 되어, idx가 혼란이 됨
- 두개 담겼던 원소들의 부모(?)는 사실 같은 idx인데, 이를 처리하지 못했음 ⇒ 할 수는 있겠지만 쓸데없이 복잡해짐
- dp 개념이 나에겐 아직 모호한 것 같다.
종혁
재웅
작은 수를 이용해 어떻게 큰 수를 구할지와, 이들을 DP 배열로 어떻게 맵핑할지가 관건인 듯 하다.