처음엔 플로이드 워셜로 시도했다. 플로이드 워셜이 N^3 인데 N 이 1000 이고 대충 1초 정도를 예상했음. 그런데 시간초과가 나서 다익스트라로 AC 를 받았다. (32ms) 그런데 0ms 가 기록에 있는 걸 보고 풀이를 봤는데, 다익스트라로 생각지 못한 풀이가 있어서 남겨봄.* 참고로 플로이드워셜로도 최적화하면 풀리긴 함. 가장 먼저 떠오른건 플로이드 워셜 알고리즘이었다. 왜냐하면 다익스트라는 한점에서 다른 모든 점까지의 최단거리를 구하는 알고리즘인데, 이번 문제의 조건은 모든 점에서 특정 점까지의 최단거리를 구해야하니까 적절하지 않다고 생각했음. 그런데 다익스트라는 한점에서 다른 모든 지점으로의 최단거리 뿐만 아니라 한 점으로 도착하는 다른 모든 점에서부터의 최단거리 또한 구할 수 있다. !!..
전체 글
이전에 진행한 내잔고를 부탁해 프로젝트에서는 Redis 를 활용한 캐싱 처리를 제대로 사용하지 못한 느낌이 있었다. 그때는 어떤 데이터를 캐싱해야할지 잘 감이 안와서 그냥 남들 하는대로 Refresh 토큰을 저장해두는 정도로만 활용하였다. 대신 채팅 기능을 구현할 때 사용자의 구독 정보 관리와 서버간 메세지 브로커로 활용한 바 있다. 물론 대규모의 트래픽 처리를 하는 경우에는 메세지 브로커로 Kafka 를 쓰겠지만, 그래도 알차게 Redis 를 활용했다고 생각한다. 이번 프로젝트에서는 Redis 의 캐싱 기능을 더 야무지게 활용하여 api 응답 시간을 줄이고자 하였다. 사실 기술적으로 별 내용은 아닌데 나름 참고할만한 유즈케이스 같아서 기록해 둔다.1. 캐싱 데이터캐싱 처리는 데이터를 가지고 올때 DB ..
https://www.acmicpc.net/problem/11049 그리디와 dp 를 두고 세시간 넘게 고민하다가 뇌가 안되는거 같아서 포기하고 풀이방향을 보고 풀었다. dp 는 어느정도 익숙해졌다 싶었는데, 이렇게 과감하게도 풀 수 있구나 싶어서 꼭 기억을 해두려고 한다. 너무 분해.dp 라는 생각이 가장 직관적으로 다가왔는데, 점화식을 어떻게 잡아야 할지 감이 안왔다. 기본적으로 dp[start][end] = start 부터 end 까지 연산의 최소값 으로 메모이제이션을 하는 쉽게 알 수 있다. 그런데 여기서dp[start][end] 와 dp[start][end + 1] 사이의 관계식(점화식)은 어떻게 만들까? 둘에 관계가 보이지 않았다.start ~ end 에서 start ~ end + 1 한개만 ..