일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- network
- git
- react
- db
- 프로그래머스
- Graph
- 백준
- vscode
- BFS
- DFS
- Algorithm
- 자바
- Javascript
- DP
- TypeScript
- java
- Database
- Redux
- Python
- 리트코드
- CS
- frontend
- 그레이들
- LeetCode
- Data Structure
- VIM
- 다이나믹 프로그래밍
- 동적 계획법
- 안드로이드
- 알고리즘
- Today
- Total
목록알고리즘 (30)
늘 겸손하게
안녕하세요 besforyou입니다 문제 풀이 dp 알고리즘으로 해결해야하는 문제입니다. 그러니 2차원 배열을 하나 선언합시다. int dp[101][100001]; 여기서 dp[a][b] = v 가 의미하는것은 a번째 물건까지 참조했고, 현재 가방에 담긴 물건들의 무게는 b일때 최대 가치가 v 라는 의미입니다. 이를 이용해서 문제를 해결해야합니다. 선형 순차 탐색으로 물건을 하나하나씩 참조해가며 담을 수 있는 최대 가치를 찾을것인데, 고려해야할점이 있습니다. 첫번째로, 물건을 담을 수 있느냐 없느냐 입니다. 현재 참조하는 물건의 무게 + 가방에 담긴 무게가 K를 넘어버리면 담을 수 없겠죠? 두번째로, 가방에 물건을 담는것이 유리한가, 유리하지 않는가 입니다. 현재 참조하는 물건을 가방에 담을 수 있는데 ..
안녕하세요 besforyou입니다 문제 풀이 구간합을 새로운 좌표를 읽어들일때마다 새로 만들면 시간 초과가 생긴다. 그러니 누적합을 구해서 2차원 배열에 누적합을 저장해놓고, x1,y1 / x2, y2 좌표를 입력받을때마다 알맞은 누적합을 출력하면 된다. 1. 2차원 배열에 누적합을 저장 1 n >> m; for (int i = 0; i x; sum[i+1][j+1] = x + sum[i+1][j] + sum[i][j+1] - sum[i][j]; } } for (int i = 0; i > x1 >> y1 >> x2 >> y2; cout
처음으로 한방에 풀어버린 dp 문제네요 문제 풀이 numRows의 범위가 1 이상 30 이하이므로 파스칼의 삼각형을 미리 만들어버리고 numRows값에 따라 알맞은 vector
문제 풀이 dp를 이용하여 오름차순으로 증가하는 부분 수열 중 가장 긴 수열의 길이를 찾고, 내림차순으로 감소하는 부분 수열 중 가장 긴 수열의 길이를 찾은 뒤 두 값을 합하고, -1을 해서 출력하면 풀 수 있는 문제이다. 1. 입력 받기 그냥 받아도 상관없지만 속도를 증가시키면서 입력을 받아보자 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 세 줄로 입력을 조금이라도 빠르게 받을 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int main (void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n;..