dp

풀이 방법을 떠올리다가 처음에는 배열을 사용한 DP로 시도했는데, N이 10^18까지 가능해 배열로는 풀 수가 없는 문제였다. N이 워낙 크다보니 BFS로도 풀지 못할 것이라 생각해 시도조차 하지 않았었고 도저히 모르겠어서 알고리즘을 확인했는데 BFS가 있어서 놀랐다. 결국 BFS가 돌아갈 수 있었던 이유는 메모리가 1024byte로 모든 수를 메모이제이션 하기에는 부족하지만, BFS 큐 사이즈를 감당하기에는 충분했기 때문인 것 같다. BFS 특성상 모든 수를 다 돌아보지 않고 가장 빨리 도달하는 경우만 살펴보기 때문이다. 관건은 "-1연산을 최소화할 수 있는가?"인 것 같다.BFS 풀이추가적으로 새로 알았던 점은 defaultdict를 사용할 때 그동안 관습적으로 int를 넣어줬었는데 여기에 커스텀 메..

14728 : 벼락치기배낭문제로 풀 수 있는 문제인데 배낭문제를 풀 때마다 헷갈리는 부분이 있어 기록으로 남기려고 한다.for j in range(time, T + 1): dp[i][j] = max(dp[i - 1][j - time] + score, dp[i - 1][j])이 부분의 max(dp[i - 1][j - time] + score, dp[i- 1][j])를 매번 max(dp[i - 1][j - time] + score, dp[i][j]로 작성해서 틀리는 일이 잦았다. 비교의 목적을 제대로 상기할 필요가 있다. 만약 내가 헷갈렸던 코드 그대로 사용하게 되면 현재 선택된 물건을 가방에 넣는 것과 넣지 않는 것을 비교하는 것이기 때문에 무조건 물건을 넣는 쪽이 가치가 더 높다. 하지만, 현재 선..

2253 : 점프 처음에는 갈 수 있는 가지수인줄 알았는데 최소 움직임 횟수였다. 명심할 것 문제 잘 꼼꼼히 읽기 경계값 체크하기기존 코드에서는 2번째 칸을 무조건 이동가능하게 해뒀는데 2번째 칸 역시 작아서 밟지 못할 수 있다. 이 부분에서 문제가 생겨서 계속 오류가 났다. 예제와 같이 6, 11, 16번 칸을 못 밟는 경우 아래와 같다. 1번째 칸에서 한칸만 이동 가능하다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 0 1 2 3 4 5 6 7 2번째 칸에서는 1의 속도로 점프했으므로 다시 1의 속도로 점프하거나, 가속해서 2의 속도로 점프할 수 있다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 0 1..