22년 12월 2주차 회고록(회고사진)

public class SolutionLoop { private static int solution(int[][] triangle) { int[][] dp = new int[triangle.length][triangle[triangle.length - 1].length]; dp[0][0] = triangle[0][0]; for (int i = 1; i < triangle.length; i++) { for (int j = 0; j <= i; j++) { if(j > 0) dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]; dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + triangle[i][j]); } } // System.out.println(Arrays.deepToString(dp)); int r = dp[triangle.length - 1][0]; for (int i = 1; i < triangle[triangle.length -1].length; ++i) { r = Math.max(r, dp[triangle.length - 1][i]); } System.out.println(Arrays.deepToString(dp)); return r; } public static void main(String[] args) { /* * 7 * 3, 8 * 8, 1, 0 * 2, 7, 4, 4 * 4, 5, 2 ,6, 5 * */ int[][] triangle = new int[][]{{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}}; int result = solution(triangle); System.out.println(result); } }

def calculate_max_value(row, col, triangle): if row == len(triangle)-1: # depth가 1이라는 것은 가장 마지막 숫자들을 본다는 것 return triangle[row][col] else: num1 = calculate_max_value(row+1, col, triangle) + triangle[row][col] num2 = calculate_max_value(row+1, col+1, triangle) + triangle[row][col] return max(num1, num2) # depth가 2 이상이면 col이 자기랑 같거나 자기보다 1 큰 경우 중에서 최댓값 def solution(triangle): answer = calculate_max_value(0, 0, triangle) return answer print(solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]))

import copy def solution(triangle): # 층의 개수 = 숫자 개수 max_nums = [0]*len(triangle) print(max_nums) max_nums[0] = triangle[0][0] print(max_nums) for i in range(1,len(triangle)): # 값을 업데이트하면서 N-1번째의 값이 소실될 수 있으므로 복사해둔다. max_nums1 = copy.copy(max_nums) # 삼각형의 왼쪽 변과 오른쪽 변 max_nums[0] = max_nums1[0] + triangle[i][0] max_nums[i] = max_nums1[i-1] + triangle[i][i] # 나머지 for j in range(1, i): max_nums[j] = triangle[i][j] + max(max_nums1[j-1], max_nums1[j]) print(max_nums) return max(max_nums) print(solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]))

def solution(triangle): for i in range(1,len(triangle)): for j in range(len(triangle[i])): left = triangle[i-1][j-1] if j-1 >= 0 else 0 right = triangle[i-1][j] if j < len(triangle[i-1]) else 0 triangle[i][j] += max(left,right) return max(triangle[-1])

점화식은 구현하였지만 코드로 풀어내는데 많이 고생했다. 생각에는 중복을 잘 제거한거같은데 자꾸 시간초과나 효율성 테스트에서 통과를 못했다.

재귀 함수를 이용하는 경우는 시간 초과가 뜨는 경우가 많은 것 같고, 재귀 함수를 이용하지 않는(리스트에 기록하는) DP 기법이 문제 해결에 효과적이라는 것을 느꼈다 문제를 보고 Dynamic Programming이라는 생각이 든다면 어떻게 기록을 할 수 있을지를 생각해보는 것이 좋을 것 같다.

어떤 값을 저장해야 하는지에 있어서 고민을 해야했다. 또한 dp 문제라는 걸 모르고 풀었을 때 풀 수 있을 지에 대한 자신은 조금 없는 것 같다.

DP문제를 풀때는 어떻게 한번 구했던 값을 더 구하지 않을까라는 생각으로 접근하자

문제를 보고 어떤 조건을 고려해야할 지 쉽게 떠오르지 않는다면 그림을 그려서 흐름이 어떻게 흘러가는지 알아보는 것도 좋은 것 같다.

DP에서 어떤 값을 배열에 저장해 나갈지를 처음에 잘 정하는 게 중요한 것 같다.

풀었던 코드를 다시한번 리펙토링해보는 시간은 갖자

수업시간에 비슷한 문제를 풀어보아서 2번째 방법을 좀 더 쉽게 떠올릴 수 있었던 것 같다. 수업 시간에 배웠던 알고리즘 복습을 한 번 해보는 것도 좋지 않을까

이름만 보고 가장 어려울 줄 알았는데 재귀가 들어간 dfs/bfs 이런 것 보다는 수월한 것 같다!