우주수첩의 우주먼지

https://www.acmicpc.net/problem/1463  package BKD_0x10_DP;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class BOJ_1463 { static Integer[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); dp ..

배열이 주어졌을때 maximum subarray 를 찾고자 한다. 본인의 경우 배열 내에서 가장 큰 값이 지속되는 구간을 찾아아 시작 인덱스와 종료 인덱스를 추출해야 했다. 시간 복잡도 O(N) 개념 각각의 최대 부분 합은 이전 최대 부분 합이 반영된 결과이다. 이전 인덱스가 가질 수 있는 최대 부분 합에 현재 인덱스 값을 더하면 현재 인덱스가 가질 수 있는 최대 부분 합을 구할 수 있음을 의미한다. 방법 각각의 인덱스 값은 이전 인덱스가 갖고 있는 최대 부분 합을 연장할지 아니면 자신의 값으로 초기화 할지 선택한다. 연장 이전 인덱스의 최대 부분합 + 현재 인덱스의 최대 부분 합 > 현재 인덱스 값 Math.max(A[i],A[i] + A[i-1]) 적용 코드 public AvailableSchedul..

Dynamic Programing recursion + Memoization 단순 테이블 채우기가 아니라 memoization을 이용해서 recursion을 smart하게 하는 기법. # 문제해결 절차 문제를 정확하게 정의하기. 정의된 문제에 대한 subproblem을 생각한 뒤 이를 이용해 reccurence relation을 세운다. A(i)를 해결하기 위해서 이전단위의 subproblem의 solution으로 현재 해결하고자하는 식을 논리적으로 구한다. memoization을 이용하여 recurrence relation 계산 중간 결과물들을 저장할 data structure을 고른다. 대개 n차원 array 사용. Subproblem들간의 dependency를 확인한다. (보통 top-down | ..