Dynamic Programming-3 동적계획법1. 일반적으로 최적화문제(optimisation problem) 혹은 카운팅(counting) 문제에 적용된다.2. 주어진 문제에 대한 순환식(recurrence equation)을 정의한다.3. 순환식을 memoization 혹은 bottom-up 방식으로 푼다.  최적화문제는 최솟값이나 최댓값 구하는 경우 또는 최단 경로 문제.카운팅 문제는 어떤 특정한 해의 개수를 구하는 문제. subproblem들을 풀어서 원래 문제를 푸는 방식. 그런 의미에서 분할정복법과 공통성이 있음.분할정복법에서는 분활된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않음.즉 서로 overlapping하는 subproblem들을 해결함으로써 원래 문제를 해결.  ..

DP 강의 이어서 듣고 정리하기

Dynamic Programming-1*Richard Bellman이 만들었다. 피보나치 수열1 1 2 3 5 8 13f(n)=f(n-2)+f(n-2) n>2f(1)=f(2)=1 int fib(int n){ if(n==1 || n==2) return 1;else return fib(n-2)+fib(n-2);} ->순환으로 하면 매우 비효율적MemoizationMemoization으로 풀면, 1차원 배열인 cashe에 저장하기 때문에, 동일한 피보나치 수열을 중복 계산 안 해도 된다. 순환식을 bottom-up방식으로 풀면,  중복 계산을 피할 수 있다. -> Dynamic Programming  base case가 있을 때, base case가 아닌 경우에 순환을 할 때 마지막엔 base case를 꼭 ..

2주차 목표DP강의 듣고 개념정리& 문제풀기

1. 책 자바의 정석1에서 Chapter07 객체 지향 프로그래밍 II부분에서상속, 오버라이딩, 제어자, 다형성, 추상클래스, 인터페이스, 내부 클래스 등에 대하여 정리한 부분에 대하여 복습하였다. 2. Chapter09 java.lang패키지와 유용한 클래스에서 Object클래스, String 클래스, StringBuffer클래스에 대하여 공부하였다.package ch09;public class Ex9_1 { public static void main(String[] args) { Value v1 = new Value(10); Value v2 = new Value(10); if(v1.equals(v2)) System.out.println("v1과 v2는 같습니다."); else Sys..

1주차 목표책 자바의 정석1, 2 복습, 입출력, 문자열 처리, 기초수학 문제 풀기