일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- dfs
- 완전탐색
- 코딩
- 백준
- 세그먼트트리
- 이분탐색
- 프로그래머스
- 문자열다루기
- activity
- 코틀린
- 안드로이드
- BFS
- 문자열
- 자바
- 알고리즘
- 분할정복
- 스택
- 동적계획법
- 생명주기
- BOJ
- 코딩테스트
- 운영체제
- 다이나믹프로그래밍
- component
- Android
- GIT
- 배열
- 트리
- 그래프
- 카카오블라인드
- Today
- Total
목록동적계획법 (10)
HS_development_log
문제 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])이다..