아무것도 안 하는 abra/짧은 메모
-
다익스트라 문제를 푸는 두가지 방법?아무것도 안 하는 abra/짧은 메모 2022. 1. 22. 20:46
(조금 특수하게 최단경로를 구해달라고 할 때) 1. 다익스트라를 문제에 맞게 구현 2. 문제에 맞게 그래프를 잘 변형한 뒤 전형적인 다익스트라 돌리기 1은 그냥 구현하면 되는데 문제에 따라서는 시간초과 내지는 메모리초과 뜰 수 있음 문제예시: 뱀이 된 경곽이? 2는 특정 동작과 동일한 역할을 하는 노드나 엣지를 추가함으로써 구현을 깔끔하게 하거나 시간, 메모리를 개선할 수 있지만 생각하기가 1에 비해 어려움 문제예시: boj 20987
-
다익스트라와 메모이제이션아무것도 안 하는 abra/짧은 메모 2021. 9. 20. 11:12
https://www.acmicpc.net/problem/11953 11953번: 쇼핑 첫 번째 줄에는 도시의 행과 열을 나타내는 정수 H, W가 공백으로 구분되어 입력된다. (3 ≦ H ≦ 1000, 3 ≦ W ≦ 1000) 다음 줄부터 H줄에 걸쳐서 W개로 이루어진 문자열이 입력된다. 이 값들은 상점 www.acmicpc.net 처음에 격자를 그래프로 바꿔서 다익스트라를 돌리는 상상을 했었다. 물론 근처 4점의 쇼핑 상태 정보를 들고 다니는 형태로. 그런데 그러면 시간복잡도가 너무 아슬아슬해보인다. H*W*2^4에 로그가 붙으니까 시간제한이 2초라 고민되긴 하지만 좀 더 좋은 방법이 있을것 같았다. 그런데 사실 다익스트라가 필요없었다. 다익스트라 방법처럼 주변점 상태도 고려하면서 메모이제이션을 돌려주..