일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 크루스칼
- 큐
- 빠른 입출력
- 백트래킹
- MST
- Knapsack
- 문자열
- lis
- 스택
- 완전 탐색
- 조합
- dfs
- 순열
- 이분 탐색
- 비트마스크
- 시뮬레이션
- DP
- 그리디
- 중복 순열
- SSAFY
- BeautifulSoup
- 분할 정복
- BFS
- 클래스
- 세그먼트 트리
- 메모리풀
- 재귀
- 우선순위 큐
- 피보나치 수
- 링크드리스트
- Today
- Total
목록DP (31)
작심 24/7
11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에 www.acmicpc.net 그냥 cin cout 쓰면 무조건 시간 초과 난다. ios_base::sync_with_stdio(false); cin.tie(NULL); 를 적어주거나 scanf printf를 써야 한다. DP와 세그먼트 트리, 두 가지 방식으로 풀어 보았다. 1. DP i번째 칸에 1번째 수부터 i번째 수까지 더한 값을 저장해놓고 a부터 b까지의 합을 출력할 때는 b번째 값에서 a - 1번째 값을 빼서 출력한다. #incl..
2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 최소 점수를 구하는 과정을 예로 들자면 현재의 첫 번째 칸의 최솟값은 그림에 나와있는 대로 min(이전의 첫 번째 칸의 최솟값 or 이전의 두 번째 칸의 최솟값) + 현재의 첫 번째 칸의 숫자 이다. 현재의 두 번째 칸의 최솟값은 그림에 나와있는 대로 min(이전의 첫 번째 칸의 최솟값 or 이전의 두 번째 칸의 최솟값 or 이전의 세 번째 칸의 최솟값) + 현재의 두 번째 칸의 숫자 이다. 현재의 세 번째 칸의 최솟값은 그림에 나와있는 대로 min(이전의 두 번째 칸의 최솟..
14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 완전 탐색, DP 두 가지 방법으로 풀 수 있다. 완전 탐색은 1일부터 차근차근 가능한 날을 모두 골라 최댓값을 구해주면 되고 DP는 i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 최대 이익, i 일을 선택하지 않을 때 얻는 최대 이익) → i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 이익 + i+T[i]일에 얻는 최대 이익, i+1일에 얻는 최대 이익) → DP[i] = max(P[i] + DP[i + T[i]], DP[i + 1]) 라는 점화식을 세워주고 재귀로 구현하면 된다. 1. 완전 탐색 #include #include using namespace std; int N, M..
1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 처음에 재귀로 그냥 DFS를 구현하니까 시간 초과 걸렸었다. 중복되는 연산이 있기 때문에 DP로 최댓값을 저장해주면서 돌려야 했다. DP [i][j] = i, j에서 상 하 좌 우로 갈 때 얻는 최댓값 이라 지정하고 범위를 벗어나거나 구멍을 만나는 경우는 게임 종료 -> 어딜 더 움직일 수 없으므로 0 반환 방문했던 곳을 다시 방문하는 경우는 사이클이 생겨 무한 번 움직일 수 있는 경우이므로 -> -1을 출력하고 아예 종료 DP에 값이 있는 경우 -> 이미 최댓..
10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오�� www.acmicpc.net 처음엔 완전 탐색으로 풀었었는데 경우의 수가 너무 많기 때문에 당연히 시간 초과됐었다. 그래서 다른 방법들도 시도하다 안 돼서 검색해보니 Top-Down 방식으로 푸는 DP 문제였다. 문제의 나와 있는 규칙을 정리해보면 1. 왼쪽 카드의 값 > 오른쪽 카드의 값 인 경우 1) 오른쪽 카드만 버릴 수 있다 2) 왼쪽 카드만 버릴 수 있다 3) 양쪽 카드를 모두 버릴 수 있다 2. 왼쪽 카드의 값 오른쪽 카드의 값 인 경우 1) 현재 오..
11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net LIS 변형 문제이다. LIS는 DP 배열에 증가 부분 수열의 길이를 갱신하는 반면 이 문제는 같은 증가 부분 수열 내의 원소들의 합을 갱신시키고 각 증가 수열이 끝날 때마다 최댓값을 갱신시켜준 뒤 최종 최댓값을 출력시키면 된다. #include #include using namespace std; int main() { int N, Max = -1; int A[1001], dp[1001]; cin >>..
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 주어진 무게들과 그에 따른 가치들을 pair로 벡터에 넣고 오름차순으로 정렬한다. 이차원 배열 DP를 만들어 0/1 Knapsack 원리로 구현한다. 평범한 배낭과 동전 문제와 비슷한 개념인데 차이점은 동전은 같은 동전을 여러 개 쓸 수 있다는 것이고 평범한 배낭은 이 물건을 가져가거나, 가져가지 않거나. 이 두가지 선택지밖에 없다는 것이다. 그래서 문제에 있는 예제로 표를 채워보면 가치 무게 1 ..
11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 파스칼의 삼각형에서 도출해낼 수 있는 이항 계수의 공식은 이다. 그런데 이대로 구현하면 nCr=nCn-r 이라는 성질 때문에 예를 들면 5C1 5C2를 구했는데 같은 값인 5C4, 5C3도 구하게 되는 불필요한 계산을 하게 된다. 그래서 삼각형을 반으로 나누어 중복되는 값을 없애보았다. 이렇게 반으로 나누면 짝수일 때 마지막 숫자만 이렇게 되고 나머지는 이 공식이 똑같이 적용된다. 이대로 구현해주면 끝 #include using namespace std; int main() { int N, K; cin >> N >> K; int dp..