Algorithm/Tree & Graph5

• 

  [알고리즘] 세그먼트 트리(Segment Tree) 알고리즘 동작 원리 및 구현하기 세그먼트 트리 알고리즘 개요 세그먼트 트리 알고리즘은 트리 형태의 자료구조를 사용한다. 특정 구간 내 데이터에 대한 연산(쿼리)을 빠르게 구할 수 있는 트리 알고리즘이다. 키워드 구간 범위 시간복잡도 데이터 변경 : O(logN) 연산 : O(logN) 데이터 변경 시마다 M번 연산 : O((logN + logN) * M) = O(MlogN) 특징 누적 합을 담은 트리라고 가정하자. N = 10 (노드의 개수 : 10) 인 그림에서 노드안에 적힌 순서는 값이 아닌 각 노드의 고유 번호라고 했을 때, 각 노드가 저장하고 있는 합의 범위(구간)를 나타낸 것이다. 각 노드는 다음과 같은 의미를 가진다. 리프 노드 : 해당 노드의 값 자체 리프 노드가 아닌 노드 : 왼쪽 자식과 오른쪽 자식의 합(누적 합 예시).. Algorithm/Tree & Graph 2022. 10. 26.

• 

  [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 동작 원리 및 구현하기 다익스트라 알고리즘 개요 다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점(노드) 뿐만 아닌, 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복한다. 그래프 알고리즘 중 최단 거리, 최소 비용을 구하는 알고리즘은 다익스트라 외에 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다. 동작 단계 출발 노드와 도착 노드를 설정한다. '최단 거리 테이블' 을 초기화한다. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. (선택한 노드는 방문 처리한다.) 해당 .. Algorithm/Tree & Graph 2022. 7. 7.

• 

  [자료구조] Binary Heaps (Min-Heap and Max-Heap) 간단하게 알아보기 Heap ? 힙(Heap)은 이진 힙(Binary Heap)이라고도 하며, 최대 값이나 최소 값을 빠르게 구하기 위해 구현된 완전이진트리(Complete Binary Tree)를 기본으로 한 자료구조 힙(Heap)의 속성 - 완전 이진트리 (Complete Binary Tree) - 부모 노드와 자식노드의 값 사이에 대소관계 성립 (형제노드사에의 대소관계는 정해지지 않음) 힙(Heap)의 종류 - 최소힙 (Min Heap) : 부모 노드가 자식 노드보다 항상 작은 값을 가지고 있고, 가장 작은 값이 루트(root)인 트리구조 - 최대힙 (Max Heap) : 부모 노드가 자식 노드보다 항상 큰 값을 가지고 있고, 가장 큰 값이 루트(root)인 트리구조 최소 힙의 노드 삽입하기 1. 완전이진트리에 맨 끝.. Algorithm/Tree & Graph 2022. 6. 5.

• 

  [자료구조] Tree의 종류 및 Binary Tree의 3가지 순회 방법 간단하게 알아보기 목차 Tree ? Tree의 종류 Binary Tree Binary Search Tree Complete Binary Tree Full Binary Tree Perfect Binary Tree Binary Tree 3가지 순회방법 Inorder (Left, Root, Right) Preorder (Root, Left, Right) Postorder (Left, Right, Root) Tree ? 그 동안 많이 접해왔던 Array, LinkedList, Stack, Queue 와 같이 라인처럼 생긴 일직선 데이터들이 있다면, 트리(Tree)는 부모 자식 관계를 가지는 구조이며, 계층과 그룹이 있다. 각 노드(Node)는 하나 이상의 자식을 갖고 있다. 트리(Tree) 노드(Node) 중에는 부모를 아는 경.. Algorithm/Tree & Graph 2022. 6. 3.

• 

  [자료구조] 그래프(Graph)의 개념 및 탐색 간단하게 알아보기 그래프(Graph)의 용어 트리(Tree)와 그래프(Graph)의 차이 그래프(Graph)의 특징 : Directed, Undirected, Cyclic, Acyclic 그래프(Graph)를 표현하는 방법 : Adjacency Matrix, Adjacency List 그래프(Graph)의 탐색 : DFS(깊이 우선탐색), BFS(넓이 우선탐색) 그래프(Graph)의 용어 정점(vertice) : 노드(node)라고도 하며 정점에는 데이터가 저장됩니다. (0, 1, 2, 3) 간선(edge): 링크(arcs)라고도 하며 노드간의 관계를 나타냅니다. 인접 정점(adjacent vertex) : 간선에 의해 연결된 정점으로 위에서 (정점0과 정점1은 인접 정점) 단순 경로(simple-path): 경로 중 반.. Algorithm/Tree & Graph 2022. 5. 23.