본문 바로가기

자료구조5

[자료구조] 진입차수란? 진입차수(Indegree)란? 그래프 이론(Graph Theory)은 네트워크 구조를 모델링하고 분석하는 데 사용되는 수학적 도구입니다. 그 중에서도 "진입차수(Indegree)"는 방향 그래프(Directed Graph)에서 매우 중요한 개념 중 하나입니다. 이 개념은 어떤 정점으로 들어오는 간선의 수를 나타내며, 그래프 내의 연결 관계를 이해하는 데 도움이 됩니다. 그래프에 대한 개념을 다시 잡고 싶으시면 아래의 링크로 이동하시면됩니다. https://sonlife97.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84%EB%9E%80 [자료구조] 그래프란? 오늘은 수학과 컴퓨터 과학에서 매우 중요한 개념.. 2024. 1. 21.
[자료구조] 그래프란? 오늘은 수학과 컴퓨터 과학에서 매우 중요한 개념인 '그래프(Graph)'에 대해 자세히 알아보겠습니다. 그래프는 객체들 간의 관계를 나타내는 추상적인 모델로, 네트워크를 구성하는 핵심적인 요소입니다. 이 구조는 데이터 구조와 알고리즘, 복잡한 시스템의 분석에 광범위하게 사용됩니다. 그래프의 기본 개념, 구성 요소, 그리고 다양한 유형과 이들의 활용 방법에 대해 구체적으로 살펴보겠습니다. 1. 노드(정점, Vertex) 그래프의 기본 단위인 노드는 네트워크 내의 개별적인 객체를 나타냅니다. 이는 도시, 컴퓨터, 사람 등 다양한 형태일 수 있습니다. 2. 간선(Edge) 노드들을 연결하는 선으로, 두 객체 사이의 관계를 나타냅니다. 간선은 친구 관계, 도로 연결, 데이터 전송 등을 표현할 수 있습니다. 3... 2024. 1. 21.
최단경로 - 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘이란? 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘입니다. 이번에 설명하는 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘입니다. 다이나믹 프로그래밍을 기반으로 하며, 특히 밀집 그래프(dense graph)에서 효과적입니다. 플로이드 워셜 알고리즘의 개념 초기화 먼저, 최단 거리를 저장할 테이블(2차원 배열)을 초기화합니다. 이 테이블의 각 항목 dist[i][j]는 정점 i에서 j로 가는 최단 거리를 나타냅니다. 자기 자신으로의 거리는 0으로, 직접 연결된 정점 사이의 거리는 해당 가중치로, 그렇지 않은 경우에는 무한대(또.. 2024. 1. 17.
최단경로 - 다익스트라 알고리즘 구체적인 설명(2) - 우선순위큐 활용 이전의 간단한 다이스트라 알고리즘 https://sonlife97.tistory.com/entry/%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%EC%B2%B4%EC%A0%81%EC%9D%B8-%EC%84%A4%EB%AA%85 최단경로 - 다익스트라 알고리즘 구체적인 설명 다익스트라 알고리즘은 하나의 출발 노드로부터 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 알고리즘의 원리를 간략히 설명하면 다음과 같습니다. 1. 출발 노드를 설정한다. 2. 최단 거 sonlife97.tistory.com 해당 알고리즘의 시간 복.. 2024. 1. 16.
자료구조 - 힙(Heap) 힙(Heap) 이란 힙은 특별한 종류의 이진트리인데, 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다. 힙은 다음과 같은 특성을 가지고 있습니다. 1. 부모 노드의 값이 항상 자식 노드의 값보다 크거나 작음(최대 힙 또는 최소 힙). 2. 완전 이진 트리(Complete Binary Tree) 구조를 가짐. 이는 트리의 모든 레벨이 완전히 채워져 있고, 가장 아래 레벨은 왼쪽부터 채워져야 함을 의미합니다. 힙은 주로 다음과 같은 작업에 사용됩니다. 최댓값 또는 최솟값을 빠르게 찾아내는 작업 (O(1) 시간 복잡도로 가능). 데이터의 삽입과 삭제(최대 또는 최소 요소에 대한)를 빠르게 수행하는데 효율적. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 가지며, 최소 힙은 부모.. 2024. 1. 16.

티스토리툴바