Dijkstra

Duplicate keys 일반적으로 대량의 데이터에 대해 정렬을 수행하는 것은 중복되는 key를 기준으로 정렬을 적용하는 경우가 많습니다. 위처럼 '도시 - 시간' 형태의 데이터라면 도시를 기준으로 정렬하게 되는 것이죠. 원래는 중복된 key를 포함하는 데이터에 대해 퀵정렬을 수행하는 경우 quadratic(2차) 시간이 걸린다는 문제점이 있었으나, 병합 정렬을 이용하여 그 시간을 획기적으로 줄일 수 있게 되었죠. Duplicate keys: the problem 하지만 일반적인 병합 정렬 방식을 적용하게 되면, key가 모두 동일한 경우에 대해서는 quadratic 시간이 소요될 것입니다. 이를 방지하기 위해 paritioning item(기준 아이템)과 동일한 것이 확인되는 순간 작업을 멈춰서 Nl..

Java collections library java의 collections라는 라이브러리엔 유용한 툴들이 많이 들어있습니다. python에도 같은 이름의 라이브러리가 있어서 코딩테스트 문제를 풀이할 때 종종 사용됩니다. War story (from Assignment 1) 과제 1이었던 percolation 문제를 예로 들어서 라이브러리 사용에 충분한 이해가 전제되어야 함을 강조하고 있습니다. n by n 사이즈의 문제를 다룰 때, 이를 배열로 풀이한 사람은 N^2 만큼의 시간이 소요됩니다. 반면 이를 linked list로 풀이하면 N^4의 시간, 즉 제곱만큼의 시간이 소요됩니다. 이는 linked list가 탐색을 수행할 때 배열의 길이 n에 비례하는 시간 복잡도를 가지기 때문입니다. 즉, 상수(c..