공부하는 블로그

9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 동적 프로그래밍을 활용하여 점화식을 해결하는 문제이다. import java.util.Scanner; public class Main { static long[] memory; public static void main(String[] args) { Scanner sc = new Scanner(System.in); StringBuilder sb = new StringBuilder(); int t = sc.nextInt(); for (int i = 0; i < t;..

동적 프로그래밍과 탐욕법은 문제를 해결하여 최적의 해를 구하는 방법이다. Dynamic Programming? 동적 프로그래밍(Dynamic Programming)은 큰 문제를 하위의 작은 문제들로 나누어 풀어 최적의 해를 구하는 기법이다. 이러면 분할정복 기법과 다를게 없어 보인다. 하지만 분할정복 기법은 작은 문제들을 풀다보면 같은 작은 문제를 반복해서 푸는 경우가 생기게 된다. 이 때, 작은 문제를 매번 다시 계산하지 않고 값을 배열에 저장(Memoization)해두었다가 재사용하는 것이 동적 프로그래밍이다. 동적 프로그래밍을 이용하여 풀 수 있는 대표적인 문제는 피보나치 수열, 최장 공통부분 수열문제, 배낭 문제 등이 있다. 간단하게 피보나치수열 문제를 풀어보자. package fibonacci;..