다이나믹프로그래밍3 [코딩테스트 대비] 동적 계획법 (DP) 정리 동적 계획법(Dynamic Programming) 정리 큰 문제를 작은 문제로 나눠서 푸는 알고리즘인데, 코딩테스트에서 자주 출제되는 알고리즘 기법입니다. DP 속성 Overlapping Subproblem (부분 문제가 겹친다.) Optimal Substructure (최적 부분 구조) Overlapping Subproblem 대표적인 예로 피보나치 수를 들 수 있다. Fn = Fn-1 + Fn-2 여기서 Fn을 큰 문제로 생각하고, 우측 항에 있는 Fn-1, Fn-2를 작은 문제로 나눈다고 생각하면 된다. Optimal Substructure 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 위의 예에서 작은 문제로 쪼갠 우측항의 Fn-1 + Fn-2로 큰 문제인 Fn의 값을 구할 수 .. 2019. 3. 30. [Java]백준 16194번 :: 카드 구매하기 2 백준 온라인 저지 16194번 - 카드 구매하기2 Java 알고리즘 문제풀이 풀이 DP(다이나믹 프로그래밍) 문제입니다. 큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘인데, 코딩테스트에 자주 출제되는 문항이다. 문제를 해석해보면 카드 N개를 구매해야한다. 카드팩에 들어있는 카드가 적은 것부터 산다. 카드 N개를 구매하는데 드는 비용의 최소를 구하는 문제이다. DP를 풀때 일반항 형태로 정의하는 것이 중요하다. 일단, 케이스 단위로 생각해보자. 카드 i개를 구매하는 방법은? 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구입한다. 카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구입한다. 카드 3개가 들어있는 카드팩을 구매하고, 카드 i-3개를 구입한다. ... 일반화 시키면 D.. 2019. 3. 13. [Java]백준 11052번 :: 카드 구매하기 백준 온라인 저지 11052번 - 카드 구매하기 Java 알고리즘 문제풀이 풀이 DP(다이나믹 프로그래밍) 문제입니다. 큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘인데, 코딩테스트에 자주 출제되는 문항이다. 문제를 해석해보면 카드 N개를 구매해야한다. 카드팩에 들어있는 카드가 적은 것부터 산다. 카드 N개를 구매하는데 드는 비용의 최대를 구하는 문제이다. DP를 풀때 일반항 형태로 정의하는 것이 중요하다. 일단, 케이스 단위로 생각해보자. 카드 i개를 구매하는 방법은? 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구입한다. 카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구입한다. 카드 3개가 들어있는 카드팩을 구매하고, 카드 i-3개를 구입한다. ... 일반화 시키면 D[.. 2019. 3. 13. 이전 1 다음