푸으름

Algorithm 공부 #19 - 트리 트리(tree) ● 노드와 에지로 연결된 그래프 ● 순환(cycle)구조를 가지고 있고, 1개의 루트 노드가 존재 ● 루트 노드를 제외한 모든 노드들은 단 1개의 부모 노드를 가짐 ● 트리의 부분 트리(서브 트리)역시 트리의 특징을 따름 ● 트리의 구성 요소 1. 루트 노드 : 트리에서 가장 최상단에 위치하는 노드 2. 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 위치하는 노드 3. 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 위치하는 노드 4. 리프 노드 : 자식 노드가 없는 가장 하위에 위치하는 노드 5. 노드 : 데이터의 index와 value를 표현하는 요소 6. 에지 : 노드와 노드의 연결 관계를 나타내는 선 7. 서브 트리 : 전체 트리에 ..

Algorithm 공부 #13 - 그래프(그래프의 표현) 에지 리스트(edge list) ● 에지를 중심으로 그래프를 표현 ● 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현 ● 배열에 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현 인접 행렬(adjacency matrix) ● 2차원 배열을 자료구조를 이용하여 그래프를 표현 ● 노드를 중심으로 그래프를 표현 ● 노드와 관련되어 있는 에지를 탐색하기 위해서는 N번 접근해야 하므로 시간복잡도가 인접 리스트에 비해 느림 ● 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐 인접 리스트(adjacency list) ● 2차원 벡터로 그래프를 표현 ● 구현은 복잡하나 노드와 연결된 에지를 탐색하는 시간이 뛰어나며, 노드 개수가..