기억해 둘 백준 문제들

1325번

• python보다 PyPy3가 더 효율적이다.
• 최댓값 또는 최솟값과 관련된 탐색을 할 때, 2개의 for문을 1개로 대체할 수 있는 방법을 찾음.
• memoization에 대해 알게 됨.
• iterative한 방식이 백준에서는 recursive한 방식보다 항상 더 유리한 줄 알았는데, memoization과 recursive한 방식을 결합하면 recursive를 보다 효율적으로 수행할 수 있음을 알게 됨.
• C++에서 시간복잡도를 줄이기 위해서 무조건적으로 unordered_map을 쓸 것이 아니라, 정해진 index를 통해서 데이터에 접근할 수 있다면 이중 vector를 사용하는 것이 더 빠를 수 있다.

28245번

• 최솟값, 최댓값 찾을 때 배열을 활용하는 것보다 크기 비교를 위한 변수를 몇 개 선언해서 이를 통해 비교하는 것이 더 효율적이다.
• 시간 초과 걱정한다고 조심스럽게 코딩하지 말고, 일단 가장 간단한 초기 아이디어부터 실현시켜본다. 그 후에 코드를 최적화해도 늦지 않다.

1238번

• 현재 구현 방식도 다익스트라 알고리즘을 연습하기에 좋다.
• 역방향 그래프를 만들어서 다익스트라 알고리즘을 2번만 실행하면 시간복잡도를 줄일 수 있으니, 그렇게 구현하는 것도 해보면 좋겠다.