컴퓨터공학 💻 도서관📚

사이클이 없는 방향 그래프를 DAG 라고 한다   위상정렬 알고리즘은 DFS, 큐를 이용해서 구현할 수 있다   사이클이 존재하는 방향 그래프라면 사이클에 포함되어 있는 모든 노드는 진입 차수가 1이상이기에 지금과 같이 설계한 경우 사이클에 포함되어 있는 모든 노드는 큐에 들어갈 수 없기 때문에 위상 정렬을 수행할 수 없다    (여러 개의 노드가 한꺼번에 큐에 들어갈 때는 어떤 순서로 들어가도 상관 없지만 예제에서는  더 작은 번호의 노드가 먼저 들어가게 설정했다)  (중간 과정 생략)       C++ 코드  자바 코드

싸이클(Cylce)은 '순환'을 의미한다.  일반적으로 싸이클은 좋지 못한 현상이다.   자칫 무한 루프에 빠질 수 있고 순환을 이루는 개체간의 종속성이 올라간다.  간선을 의존관계라고 생각해보면 A는 C에 의존하고 C는 B에 의존하고 B는 A에 의존한다. 종속성이 커질수록 결합도가 올라가 유지보수가 어려워진다.  원본 그래프에 존재하는 모든 간선을 활용하진 않고 일부 간선을 활용해서 모든 노드가 포함되어 있는 부분 그래프를 만든 것이 신장 트리이다.   최소 신장 트리 (MST, Minimum Spanning Tree)   크루스칼 알고리즘은 간선을 하나씩 확인하면서 최소 신장 트리에 포함을 시킬지, 시키지 않을지를 결정하는 방식으로 동작한다   (원래는 비용에 따라 오름차순 정렬을 해야 하는데 여기에..

(밑에 있는 예시를 보고 이해하기)    노드3과 노드4의 부모 노드는 다르다 여기서 두 노드가 같은 집합에 포함되어 있는지 확인하기 위해서는 각 노드의 루트노드를 찾아야 한다 노드3 : 3 --> 2 --> 1 노드4 : 4 --> 1 두 노드의 부모 노드를 따라가보니 두 노드의 루트 노드가 같으므로 두 노드는 같은 집합에 포함되어 있음을 확인할 수 있다.   서로소 집합 자료구조에서는 대부분 루트 노드에 바로, 즉시 접근할 수 없다 대부분 루트 노드를 찾기 위해 부모 태이블을 확인하며 계속 거슬러 올라가야 한다    find 함수는 특정 원소가 속한 집합을 찾기 위해 루트 노드를 반환한다 find 함수는 그 이름을 관행적으로 find_parent 라는 이름으로 짓는다   C++ 코드  자바 코드   ..

N의 크기가 500 이하이므로 플로이드 워셜 알고리즘을 사용할 수 있다 플로이드 워셜 알고리즘으로 모든 노드에서부터 다른 모든 노드까지의 최단거리를 다 구한 다음에 (1번 -- X 최단 거리 + X -- K 최단 거리) 를 계산하면 된다   C++ 코드   자바 코드

주어진 N, M의 범위를 보니 플로이드 워셜 알고리즘은 500개 이상이므로 안 되고 기본 다익스트라 알고리즘도 시간복잡도가 O(N^^2)이므로 시간초과가 나올 수 있기 때문에 우선순위 힙을 이용한 다익스트라 알고리즘으로 구현하면 된다  도시 C에서 출발해서 각각의 노드로 도달하기 위한 최단 거리 값을 구한 뒤에 C에서 도달이 가능한 도시의 개수를 구할 수 있을 것이고 또한, 도시들이 모두 메시지를 받는 데까지 걸리는 시간을 구하기 위해서 도달이 가능한 도시 중에서 가장 큰 비용을 가지는 즉, 가장 거리가 먼 도시에 대한 정보를 출력하면 된다    C++ 코드   자바 코드

플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다는 점에서 점화식에 맞게  3중 반복문을 이용해서 2차원 테이블을 갱신한다 3중 반복문을 이용하기 때문에 시간복잡도가 O(N^^3) 이기에 노드의 개수가 적은 상황에서 효과적으로 사용할 수 있고 노드의 개수, 간선의 개수가 많은 경우에는 일반적으로 다익스트라 알고리즘을 사용해야 해결할 수 있는 경우가 많다   플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형이기 때문에 점화식을 동반한다     (중간 생략)      플로이드 워셜 알고리즘을 사용해야 하는 경우 노드의 개수가 500개 이상으로는 주어지지 않는 경우가 많다.  3중 반복문을 사용해서 시간복잡도가 O..

V 는 노드의 개수를 의미한다O(V) 번에 걸쳐서 최단 거리가 가장 짧은 노드를 찾기 위해 O(V) 번 선형 탐색을 해야 하므로 전체 시간 복잡도는 O(V^^2) 이다더욱 효율적으로 동작하는 알고리즘을 설계할 필요가 있다.     최소 힙은 값이 낮은 데이터부터 꺼내는 방식으로 동작하고 (오름차순)최대 힙은 값이 높은 데이터부터 꺼내는 방식으로 동작한다 (내림차순) 단순히 리스트로 우선순위 큐를 구현했을 때,  데이터를 삽입할 때는 단순히 데이터를 맨 뒤에 차례대로 넣으면 되기 때문에 O(1)(상수 시간) 이 걸리지만 데이터를 삭제할 때는 전체 데이터를 순회하며 우선순위가 가장 높은 데이터가 무엇인지 확인해야 하기 때문에 O(N)(선형 시간) 이 걸린다 힙은 내부적으로 트리 구조를 이용하여 데이터의 삽입..

다익스트라 최단 경로 알고리즘은 현실 세계의 길찾기 문제에서 사용될 수 있는 알고리즘이다. 네덜란드의 컴퓨터 과학자 '에츠허르 다익스트라'가 고안한 알고리즘 길찾기 문제 자체는 다이나믹 프로그래밍의 원리가 적용된 문제라고 할 수 있다. 다익스트라 최단 경로 알고리즘은 길찾기 문제 중에서도 탐욕적인 원리를 이용한다는 점에서 그리디 알고리즘으로 분류한다   최단 거리 테이블을 초기화할 때 다른 모든 노드까지 가는 비용은 무한으로 설정하고 자기자신에 대한 노드는 0으로 설정한다  자기자신에서 자기자신으로 가는 비용은 0이라고 볼 수 있기 때문이다     다음 단계로 넘어갈 때 아직 방문하지 않은 노드 중에서 최단 거리 비용이 가장 작은 노드를 선택해야 한다 이때 2번 노드와 5번 노드가 모두 같은 비용을 가지..