일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- activity
- 코틀린
- 카카오블라인드
- 배열
- 이분탐색
- 다이나믹프로그래밍
- 완전탐색
- 알고리즘
- 문자열다루기
- 코딩
- 트리
- 동적계획법
- 백준
- 그래프
- GIT
- 분할정복
- 프로그래머스
- 스택
- BOJ
- 자바
- 세그먼트트리
- BFS
- component
- 코딩테스트
- 안드로이드
- 문자열
- dfs
- Android
- 생명주기
- 운영체제
- Today
- Total
목록Algorithm-백준/다이나믹 프로그래밍 (12)
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])이다..
문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 문제. 점화식을 세우고 bottom-up방식으로 차근차근 답을 구해가면서 풀었다. 정답률이 31퍼센트 정도인데 직관적으로 보면 3으로나누는게 숫자가 제일 작아지니까 3으로나누어떨어지면 3, 2로나누어떨어지면 2, 안되면 1을빼는 방식으로 구현했을경우가 오답률을 제일 많이 늘렸을 것 같다. 알고리즘 3과 2로 모두 나누어떨어지지 않으면 1을뺀다. 횟수+1 3으로 나누어떨어지면 dp[n/3]과 dp[n-1] 중 더작은값을 선택한후 횟수+1 2로 나누어떨어지면 dp[n/2]와 dp[n-1]중..
문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 동적 프로그래밍 실력 향상을 위해 풀어본 문제. 바로 연속 2개를 허용하지 않는 문제는 풀어봤는데 3개는 처음이라 점화식을 찾고..