코드굽는 타자기

링크 Programmers[43105] 문제설명 정수 삼각형 문제풀이 완전탐색으로 가면 시간 너무 오래걸림 DP로 제일 유리한 경로만 따라가면서 효율적으로 풀이 arr[i][j] = max(arr[i-1][j-1],arr[i-1][j]) 문제코드 import java.util.Arrays; class Solution { public static int solution(int[][] triangle) { int answer = 0; int len = triangle.length; for (int i = 1; i < len; i++) { for (int j = 0; j

링크 Programmers[43104] 문제설명 피보나치수열 문제풀이 재귀만으로 풀지말고 DP로 효율적으로 풀어야 한다. 문제코드 class Solution { public long solution(int N) { long[] answer = new long[N]; answer[0]=2; answer[1]=3; for (int i = 2; i < N; i++) { answer[i]=answer[i-2]+answer[i-1]; } return answer[N-1]*2; } }아쉬운점 Memoization, DP 구분을 잘 못하겠음 Memoization으로 푸는 방법을 모르겠음 잘한점 피보나치수열 규칙 찾음 DP로 품(효율성 통과)

링크 SWEA[3307] 문제설명 최장 증가 부분 수열[D3] 문제풀이 int[] arr = {1,3,2,5,4}일 때, int[] len = {1,1,1,1,1}에서 시작 len[n]은 n번째 수의 수열의 길이 각각의 수가 수열의 출발일 수 있으니 1로 초기화 Update방법 len[1]의 경우 arr[1]과 이전 수인 arr[0]와 비교하여 arr[0]