일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 운영체제
- BOJ
- BFS
- 백준
- 코틀린
- 안드로이드
- 코딩
- 분할정복
- GIT
- 프로그래머스
- 세그먼트트리
- 카카오블라인드
- 다이나믹프로그래밍
- 알고리즘
- 문자열
- 생명주기
- component
- Android
- 이분탐색
- 스택
- 자바
- 동적계획법
- 배열
- 문자열다루기
- 코딩테스트
- 완전탐색
- 그래프
- dfs
- 트리
- activity
- Today
- Total
목록다이나믹프로그래밍 (12)
HS_development_log
문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1,2,3 더하기 5와 같은 2차원배열에 연속개념이 들어간문제. 점화식만 잘세우면 어렵지않다. 알고리즘 연속된수가 와야되므로 마지막에 a라는 숫자가왔다면 앞자리에 올수있는 수는 a-1 또는 a+1 dp[n][a] = dp[n-1][a-1]+dp[n-1][a+1] 이다 a-1이 0보다 작아질경우와 a+1이 9보다 커질경우에 대한 예외를 처리한다 소스 코드 12345678910111213141516171819202122232425262728293031323334353637383940/* * BOJ10844 *..
문제 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1,2,3 더하기에서 연속으로 사용하면 안 된다는 조건이 추가된 문제. 2차원 배열을 사용해서 풀었는데 마지막 출력 과정에서 나머지 연산을 실수해서 시간이 좀 걸렸다. 알고리즘 1을 사용해서 n이라는 수를 만들려면 앞에서 2,3 만사용해야 한다 2를 사용해서 n이라는 수를 만들려면 앞에서 1,3 만사용해야 한다 3을 사용해서 n이라는 수를 만들려면 앞에서 1,2 만사용해야한다 따라서 점화식을 세우면 dp[n][1(1을 사용한다는 뜻)] = d..
문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 다이나믹 프로그래밍 문제. 카드를 N개 사는 경우, 최대 금액으로 구매하는 문제이다. 어렵지 않은 문제 알고리즘 카드팩의 종류는 총 N개이다 카드를 N개 살 때의 최대 금액을 dp [N]이라고 하고 카드가 N개 들어있는 카드팩의 가격을 p [N]이라고 한다 이때 dp [n] = max(dp [0]+p [n], dp [1]+p [n-1], dp [2]+p [n-2] ··· dp [n]+p [0])이다..
문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 동적 프로그래밍 실력 향상을 위해 풀어본 문제. 바로 연속 2개를 허용하지 않는 문제는 풀어봤는데 3개는 처음이라 점화식을 찾고..