말감로그

다익스트라 알고리즘과 프림 알고리즘에 대한 차이가 궁금해져 찾아봤다. 다익스트라와 프림은 모두 그래프 알고리즘 중 하나로, 그래프에서 최소 비용의 경로 또는 트리를 찾는 데 사용된다. 그러나 두 알고리즘은 목적과 적용되는 상황에서 차이가 있다. 1. 목적 - 다익스트라 알고리즘 : 주어진 출발 노드에서 다른 모든 노드까지의 최단 경로를 찾는 것이 목적이다. 주로 하나의 출발점에서 다른 모든 지점까지의 최단 경로를 찾는 데 사용된다. - 프림 알고리즘 : 주어진 그래프에서 최소 신장 트리를 찾는 것이 목적이다. 주로 그래프에서 모든 노드를 연결하는 최소 비용의 트리를 찾는 데 사용된다. 더보기 최소 신장 트리 그래프에서 모든 노드를 가장 적은 비용으로 연결하는 트리. 그래프의 모든 노드를 포함하고, 사이클..

힙 정렬이란 ? 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 이러한 두 값의 대소 관계가 일정하면 된다. 완전 이진 트리란? 노드를 삽입할 때 왼쪽부터 추가하는 이진트리(모든 노드의 차수가 2이하로 구성된 트리) 모든 부모와 자식 관계는 항상 부모의 값 >= 자식의 값 성립 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. 따라서 힙은 형제의 대소관계가 정해져 있지 않으므로 부분 순서 트리(partical ordered tree)라고도 한다. 시간복잡도 - O(n log n) 단순 선택 정렬의 시간 복잡도 O(n^2) 이러..

그래프 탐색의 목적은 모든 정점을 한 번씩 방문 하는 것이다. 어떻게 방문할 것이냐에 따라 DFS와 BFS로 나뉜다. DFS - 깊이 우선 탐색 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식. 모든 노드를 방문하고자 하는 경우에 이 방법을 사용 그래프의 구조를 파악하는데 유용 BFS에 비해 간단하지만 검색 속도가 느림 스택 또는 재귀함수로 구현 활용: 미로 찾기 DFS 구현 방법 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노..

위상정렬(Topological Sorting)? 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘. 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미 사용 사례 (ChatGPT 검색..) 작업스케줄링 컴파일러 최적화 의존성 관리 과목 수강신청 일정 계획 네트워크 토폴로지 설계 위상정렬을 알아가기 위해 진입차수와 진출차수를 알아야 한다. 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 동작 과정 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해..