시간 복잡도는 알고리즘의 성능을 나타내는 지표다. 해당 알고리즘을 실행시켰을 때, 연산 횟수에 대한 worst case적인 한계를 의미한다. 시간 복잡도는 낮으면 낮을 수록 좋다. 빅 O 표기법을 통해 알 수 있으며, 현대 컴퓨터에서 대략적으로 1초 연산이 최대 1억번의 연산 횟수를 가진다는 걸 머릿속에 넣어 놓으면 좋다. 이를 통해 우리는 조건이 1초, 1만개가 들어가는 테스트 케이스 범위가 주어졌을 때, O(n^2)은 쓰지 못한다는 걸 직감적으로 알 수 있게 된다. 시간을 측정하려면 절대 시간을 측정하는 방법도 있으나, 그런 방법은 코딩 테스트에서는 잘 활용되지 않는다. 빅오 표기법 1차원 배열에서 가장 값을 늦게 찾는 경우는 리스트의 끝까지 검색했을 때 혹은 값을 못찾았을 때. 즉, O(n)이다. ..
그래프에서 사이클이란 간단하다. 쉽게 말해서 자기 자신으로 돌아올 수 있는지를 찾는 것. 방법에는 union-find와 dfs의 백엣지 검출이 있다. 이때 정점 n개, 간선 n-1개인 그래프는 트리이기에 정점 n개, 간선 n개인 그래프가 되어야 하나의 사이클이 존재한다. 트리에서는 visited 배열 없이도 DFS 탐색의 적용이 가능하다. 직전 노드가 어디인지만 표시해주면 된다. 사이클 검출 방식 사이클에서 그래프를 찾기 위해 n-1개의 간선을 탐색 한 후, 다시 vistied한 정점을 발견한다면 그 정점에 의해 사이클이 형성된다. 사이클에 포함된 정점들이 어떻게 되어 있는 건지 알려면 정점이 어디서 부터 온 것인지를 저장해놓으면 된다. 따라서 dfs로도 사이클을 검출할 수 있다. def has_cycl..