시간 복잡도는 알고리즘의 성능을 나타내는 지표다. 해당 알고리즘을 실행시켰을 때, 연산 횟수에 대한 worst case적인 한계를 의미한다. 시간 복잡도는 낮으면 낮을 수록 좋다. 빅 O 표기법을 통해 알 수 있으며, 현대 컴퓨터에서 대략적으로 1초 연산이 최대 1억번의 연산 횟수를 가진다는 걸 머릿속에 넣어 놓으면 좋다. 이를 통해 우리는 조건이 1초, 1만개가 들어가는 테스트 케이스 범위가 주어졌을 때, O(n^2)은 쓰지 못한다는 걸 직감적으로 알 수 있게 된다. 시간을 측정하려면 절대 시간을 측정하는 방법도 있으나, 그런 방법은 코딩 테스트에서는 잘 활용되지 않는다. 빅오 표기법 1차원 배열에서 가장 값을 늦게 찾는 경우는 리스트의 끝까지 검색했을 때 혹은 값을 못찾았을 때. 즉, O(n)이다. ..
[그래프] 다익스트라 알고리즘
다익스트라 알고리즘은 하나의 정점에서 다른 정점으로 갈 때, 최단 경로를 알려주는 알고리즘이다. 여러개의 정점이 존재하는 그래프에서, 간선에 다음 노드로 가는 거리가 표시된다. 그 이후, 각 상황마다 갈 수 있는 짧은 경로를 선택한 뒤, 전에 있던 경로와 비교 갱신하여 최단 거리를 찾는다. 정확한 순서는 다음과 같다. 1. 출발 노드 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장(위에서는 P와 U. 나머지는 inf 처리하는데 그냥 충분히 높은 값을 주면 된다.) 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택(여기서는 P) 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신(즉, P에서는 X,Q로 갈 수 있는데 X로 가는 방식이 3+1과 2+4가 있..
그래프에서 사이클이란 간단하다. 쉽게 말해서 자기 자신으로 돌아올 수 있는지를 찾는 것. 방법에는 union-find와 dfs의 백엣지 검출이 있다. 이때 정점 n개, 간선 n-1개인 그래프는 트리이기에 정점 n개, 간선 n개인 그래프가 되어야 하나의 사이클이 존재한다. 트리에서는 visited 배열 없이도 DFS 탐색의 적용이 가능하다. 직전 노드가 어디인지만 표시해주면 된다. 사이클 검출 방식 사이클에서 그래프를 찾기 위해 n-1개의 간선을 탐색 한 후, 다시 vistied한 정점을 발견한다면 그 정점에 의해 사이클이 형성된다. 사이클에 포함된 정점들이 어떻게 되어 있는 건지 알려면 정점이 어디서 부터 온 것인지를 저장해놓으면 된다. 따라서 dfs로도 사이클을 검출할 수 있다. def has_cycl..
최소 신장 트리 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘. 그 중에서 대표적인 최소 신장 트리 알고리즘이 크루스칼 알고리즘 그리디 알고리즘으로 분류 신장 트리의 개념 하나의 그래프가 있을 때 모든 노드를 포함하고, 연결되며 사이클이 존재하지 않는(tree) 그래프 신장 트리는 구글에 치기만 해도 예시가 나온다. 연결 관계에서 사이클을 형성하지 않으므로, 정점의 개수가 n개일 때, 간선이 n-1개가 된다. 최소 신장 트리 해당 신장 트리들 중에서 간선에 부여된 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라 한다. 신장 트리의 조건을 만족하면서 최소 가중치(비용)을 들이는 신장 트리가 최소 신장 트리이다. 크루스칼 알고리즘 크루스칼 알고리즘의 구체적인 동작..