홍시홍의 프로그래밍

시간 복잡도 행렬을 사용하였을 경우는 O(n^2) 힙을 사용하였을 경우는 O(nlogn) 구현방법 프림 알고리즘은 현재 정점에서 다른 정점에 갈 수 있다면 가는 알고리즘? 이다 거리가 갱신된다면 그 정점으로의 이동이 가능하다 큐에 있는 정점 중 이동 거리가 제일 작은 것의 작은거??로 이동하는 알고리즘 pq에 시작 노드를 넣고 거리를 0으로 초기화 노드를 꺼내서 방문한 노드라면 pass 방문하지 않은 노드이고 연결된 노드라면 큐에 넣는다 모든 노드가 연결될때까지 n-1개의 간선이 생길때까지 연결한다 특징 노드의 수보다 간선이 더 많을때 사용한다 아래 블로그에 이해하기 쉽게 설명되어 있다 https://makefortune2.tistory.com/37 22. 최소신장트리(MST) 프림(Prim) 알고리즘 ..

코사라주 알고리즘 강한 연결 요소(SCC)를 구하는 것이다 SCC란 사이클을 가지는 정점의 집합이다ㅣ 시간복잡도 코사라주 알고리즘은 dfs를 기반으로 한다 인접리스트의 경우 O(V+E)로 가능하다 준비 사항 코사라주 알고리즘을 실행하기 위해서는 그래프 역방향 그래프 stack 세가지가 필요하다 구현 방법 1. 역방향 그래프를 구한다 2. 원래 그래프에서 dfs를 실시한다 3. dfs가 끝나는 대로 stack에 정점을 넣을 수 있도록 한다. 4. stack에 끝에서 부터 역방향 그래프로 dfs를 실시한다 5. 종료 되거나 방문되지 않는 것들끼리 엮어져 있는것이 SCC가 된다 아래 글이 도움이 되었다 https://wondy1128.tistory.com/130 SCC-코사라주 알고리즘(Kosaraju's A..

사용하는 이유 주어진 그래프에서의 진입차수를 이용한 순서를 구하기 위하여 특징 여러가지 위상 정렬 그래프가 나올 수 있다. 구현 위상 정렬을 정렬한 리스트와 진입 차수가 0이 되면 삽입할 큐 2개를 이용하여 구현다 현재 노드와 연결된 간선을 하나하나 제거해주면 진입되는 노드의 진입 차수가 0이 되면 큐에 넣으면서 정렬할 수 있도록 한다. 시간 복잡도 시간 복잡도는 O(V+E) 모든 노드에 대해 모든 간선을 탐색하여야 한다.

셸 정렬 정의 삽입정렬을 활용한 정렬이다 구간을 만들어서 정렬하고 이러한 구간을 합쳐 완성된 정렬을 만드는 방법 구현방법 1. 맨처음은 크기/2 구간의 리스트를 만들어 그 리스트를 정렬할 수 있도록한다. 2. 정렬 된 것을 다시 나누기 2 구간으로 만들어 리스트를 정렬한다 3. 크기가 1이 되면 정렬이 종료된 것이다 장점 삽입 정렬에 비해 교환 횟수가 적어 빠르다 시간 복잡도 n^2이나 평균적으로 n^1.5