일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 이젠 골드구현도 어렵네..
- 다익스트라
- java
- DFS
- 취득후기
- 네트워크플로우
- 완전탐색
- 엘라스틱서치
- QUICKSTARTGUIDE
- 자바PS
- YBMCOS
- 백준
- 재귀함수
- 세그먼트트리
- 게더타운시작
- 01BFS
- COSPRO
- GatherTown
- 구현
- 백준코딩테스트
- 다이나믹프로그래밍
- spring
- 시뮬레이션
- 알고리즘
- 우선순위큐
- deque
- dp
- COSPROJAVA1급
- PS
- BFS
- Today
- Total
목록알고리즘/Dynamic Programming (30)
공부공간
삼각형을 내려오면서 가질수 있는 최대의 값을 구하는 문제이다. 내려올때에 이전 층의 대각선 방향만 고려하면 되기때문에, DP[N][N]을 구할때 DP[N-1][N-1] + NOW , DP[N-1][N]+ NOW 의 경우중 큰값을 가지고 업데이트 해준다. 맨처음과 끝은 비교해야할 대상이 한가지이므로 이경우만 처리해주면서 진행하면 된다.
계단을 오르면서 얻을수있는 점수의 최댓값을 구하는 문제이다. 맨 마지막을 꼭 밟으면서 연속된 3개의 계단은 밟지 못하는 규칙이 있으므로 1. 두칸을 오르고 맨마지막 직전의 계단을 밟고 마지막 계단을 밟은경우, 2. 두칸을 오르고 맨마지막 직전 계단 이전을 밟고, 직전계단을 밟고 마지막 계단을 밟은 경우로 나뉜다. 즉 dp[n]값을 구하기위해서 dp[n-2] + num[n] 값과 dp[n-3] + num[n-1] + num[n-2] 값중 큰값으로 업데이트해주면서 진행하면된다.
수열에서 연속되지 않은 3개 미만의 수를 고르면서 최댓값을 출력하는 문제이다. DP로 풀기위해서 점화식을 세워보니, 조건에서 연속하는 3개의 포도주는 마실수 없다고 제시하였다. 따라서 1. 현재 포도주를 마시지 않을경우 (DP[n-1]) 2. 현재 포도주는 마시고 바로 직전 포도주는 안마신경우 즉 n-2까지는 최대인경우 ( DP[n-2] + num[n] ) 3. 현재포도주와 직전포도주까지 마시고 연속해서 3잔은 못마시기때문에 n-3까지는 최대인경우 ( DP[n-3] + num[n] + num[n-1] ) 이 3가지중에 가장 큰 값을 DP[n]으로 선택하여서 업데이트 해주면 된다. N
DP 기본형이다. DP[i][j] 번째는 직전에 이동할수있는 장소의 최댓값에 현재 장소의 값을 더해서 저장해준다.
DP와 DFS를 동시에 쓰는 문제이다. 2차원 배열의 모든 인덱스값을 DFS를 돌리면서 해당 인덱스에서 판다가 살아갈 날을 따로 저장해둔다. 인접한 인덱스에서 DFS로 검사해줄 때, 자기보다 큰 노드를 탐색하며 이전에 값 +1 값으로 갱신해주면서 최대한 살 수 있는 일수를 출력한다.
문제 읽자마자 조건대로 코딩해주었다. 어떤 정수에 대해서 3으로 나누어 떨어지면서 2로나누어 떨어지는 경우 6의 배수로 처리하였고 각각 2의배수 3의 배수로 채우고, 아닌경우 x-1로 재귀호출하여서 m배열을 채워준다음에 x번째 v가 계산되면 바로 가져오는 식으로 구현하였는데, 굳이 v를 선언하지않고 m[x]>0로 이전에 계산이 되었는지 확인하면 될 것 같았다. 맞긴했지만 뭔가 찜찜한 해결.. 좀더 효율 적으로 접근해야겠다.