코딩하는 냄뚜

지난 시간에 풀이하였던 가장 긴 증가하는 부분 수열과 아주 유사한 문제이다. 대신에 달라지는 점은 부분 수열의 길이가 아니라 부분 수열의 합이 가장 큰 것을 찾는다는 것이다. 다이나믹 프로그래밍에서 항상 중요한 것은 dp배열에 어떤 값을 넣느냐이다. 이번 문제에서는 dp[i]는 numbers[i]가 마지막인 부분 수열의 합으로 정의한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { // ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..

자대 배치받고 나서 여유가 생기고 나서 한 전공 공부 중 그나마 가장 알고리즘 다운 알고리즘(스택, 큐 등 자료구조 적인 것은 제외하기로 한다). 다이내믹 프로그래밍. 동적 계획법이라고도 불린다. 코드 플러스에서 진행되는 강의를 듣고 나서는 강의를 따라가며 대략 열몇 문제 정도의 dp문제들을 풀어보았다. 그래도 아직까지 감이 덜 잡혀서 강의를 중단하고 현재는 dp 및 백준 알고리즘 사이트의 단계별 문제들을 풀어보는 중이다. dp를 함에 있어서 가장 주의해야 할 것들 . 배열의 인덱스 번호를 넣을때는 보통 편의를 위하여 0번을 제외하기 위해서 필요한 개수보다 길이를 1 길게 만든다. 나머지 연산이 필요한 경우 최종적으로 마지막에 한번만 하게 되면 자료형의 범위를 벗어날 수 있으므로 값을 구할 때마다 계속해..