비선형 구조(NonLinear Structure)
-
선형 구조와 달리 자료가 일렬로 나열되어 있지 않고, 자료들이 1:n 관계를 가지는 구조
-
대표적으로 그래프와 트리가 있다.
그래프(Graph)
-
정점과 정점 사이를 연결하는 간선으로 이루어져 있다
-
정점은 Node, 간선은 Edge 라고 부른다.
-
정점은 여러 개의 간선을 가질 수 있고, 간선은 가중치를 가질 수 있다.
-
그래프 탐색시 방문 여부를 확인하여 무한 루프에 빠지는 경우를 방지해야 한다.
-
인접 행렬과 인접 리스트를 이용해서 구현 가능
-
무방향 그래프와 방향 그래프로 나뉠 수 있다.
무방향 그래프(Undirected Graph)
-
간선으로 이어진 정점끼리 양방향으로 이동이 가능한 그래프
-
A와 B가 연결된 무방향 그래프는 A -> B, B -> A간 이동이 가능하다.
방향 그래프(Directed Graph)
-
간선에 방향이 존재하는 그래프, 한 방향으로만 이동이 가능하다.
-
양방향으로 갈 수 있더라도, 각 간선은 서로 다른 간선으로 취급된다.
상태에 따른 분류
-
연결 그래프(Connected Graph)
-
모든 정점이 서로 이동 가능한 상태인 그래프
-
한 정점에서 다른 정점으로 이동하는 경로가 하나 이상 존재한다.
-
-
비연결 그래프
-
간선이 연결되어 있지 않은 정점이 있는 그래프
-
특정 정점으로 이동할 수 없는 경우가 생긴다.
-
-
완전 그래프(Compolete Graph)
-
모든 정점끼리 서로 연결되어 있는 그래프
-
정점이 n개일 경우, 한 정점의 간선 수는 n-1이 된다.
-
정점이 n개일 경우, 모든 간선의 수는 그래프의 종류에 따라 다르다.
- 유방향 그래프 : n(n-1)
- 무방향 그래프 : n(n-1) / 2
-
실습
문제 출처
코드
function solution(n, edge) {
const graph = new Map();
const queue = new Queue();
let max = 0;
for(let i = 1; i <= n; i++) {
graph.set(i, { list : [], distance : 0 });
}
edge.forEach(node => {
graph.get(node[0]).list.push(node[1]);
graph.get(node[1]).list.push(node[0]);
});
queue.enqueue(1);
graph.get(1).distance = 1;
while(queue.size() !== 0) {
const node = queue.dequeue();
graph.get(node).list.forEach(nextNode => {
if(graph.get(nextNode).distance === 0) {
queue.enqueue(nextNode);
graph.get(nextNode).distance = graph.get(node).distance + 1;
max = max < graph.get(nextNode).distance ?
graph.get(nextNode).distance :
max;
}
});
}
return [...graph].filter(node => node[1].distance === max).length;
}
class Queue {
constructor() {
this.queue = [];
this.front = 0;
this.rear = 0;
}
enqueue(value) {
this.queue[this.rear++] = value;
}
dequeue() {
const value = this.queue[this.front];
delete this.queue[this.front];
this.front += 1;
return value;
}
peek() {
return this.queue[this.front];
}
size() {
return this.rear - this.front;
}
}후기
시간 초과가 나올까 Queue는 직접 구현하고, Graph는 인접 리스트로, 거리 계산에 필요한 탐색은 BFS를 이용했다.
방문에 필요한 배열을 따로 만들어서 처리할 수도 있지만, 해시테이블을 이용해서 간선의 정보와 정점까지 필요한 거리를 같이 저장하고, 거리가 0일 경우 방문하지 않은 노드로 정의해서 풀었다.
덕분에 코드가 많이 지저분해진 것 같아서, 좀 더 가독성을 고려해서 풀 수 있도록 노력해봐야겠다..😅
트리(Tree)
-
방향 그래프의 일종으로, 정점을 가리키는 간선이 하나밖에 없는 구조.
-
A 노드가 B 노드를 가리키는 경우, A를 부모 노드(Parent Node), B를 자식 노드(Child Node) 라고 한다.
-
최상위 노드를 루트 노드(Root Node), 자식이 없는 노드를 잎 노드(Leaf Node) 라고 부른다.
-
레벨(Level) 이 있으며, 루트부터 시작하여 깊이를 나타낸다.
-
하나의 노드에서 뻗어나가는 간선을 차수(Degree)라고 한다.
-
루트 노드를 제외한 모든 노드는 반드시 하나의 부모만을 가지며, 루트에서 특정 정점으로 가는 경로는 하나만 존재한다.
이진 트리(Binary Tree)
-
각 정점이 최대 2개의 자식만을 가지는 트리
-
보통 자료구조에 응용되거나 탐색 알고리즘에 자주 사용한다.
-
정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다.(편향 트리)
-
정점이 N개인 포화 또는 완전 이진 트리의 높이는 log N 이다.
-
높이가 h인 포화 이진 트리는 2^h - 1개의 정점을 가진다.(2진법을 생각하면 쉽다)
-
이진 트리는 완전 이진 트리, 포화 이진 트리, 편향 트리로 나뉜다.
-
포화 이진 트리(Perfect Binary Tree)
-
마지막 레벨까지 모든 정점이 채워져 있는 트리
-
리프 노드를 제외한 모든 노드가 2개의 자식 노드를 가진다.
-
-
완전 이진 트리(Complete Binary Tree)
-
마지막 레벨을 제외한 모든 정점이 채워져 있는 트리
-
마지막 레벨은 무조건 왼쪽에서 오른쪽으로 채워져야 한다.
-
-
편향 이진 트리(Skewed Binary Tree)
-
한 방향으로만 정점이 이어지는 트리
-
리프 노드를 제외한 모든 노드는 하나의 자식 노드만을 가진다.
-
구현 방법
-
배열과 연결 리스트를 이용해 구현이 가능
-
배열을 이용한 구현 시 왼쪽 노드는 index * 2, 오른쪽 노드는 index * 2 + 1을 이용해 구할 수 있다. 부모 노드는 index / 2의 몫이 된다.
-
연결 리스트를 이용한 구현 시 왼쪽과 오른쪽 노드를 가리키는 포인터를 이용해 구현이 가능하다.
우선순위 큐(Priority Queue)
-
FIFO(First In First Out)인 큐와 다르게, 우선순위가 높은 요소부터 먼저 나가는 큐
-
다양한 방법으로 구현할 수 있지만, 주로 힙을 이용해서 구현한다.
힙(Heap)
-
완전 이진 트리의 형태를 가지며, 요소의 삽입 및 삭제 시 바로 정렬되는 구조.
-
루트가 가장 큰 값인 최대 힙(Max Heap)과, 루트가 가장 작은 값인 최소 힙(Min Heap)이 있다.
-
완전 이진 트리의 형태를 가지기 때문에, 정점이 n개일 경우 높이는 log n이 된다.
-
요소의 추가 삭제 시, 시간 복잡도는 O(log n)이다.
힙의 추가 삭제 순서
요소 추가 시
-
새로운 요소는 트리의 마지막 레벨에 추가된다.
-
추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
-
이 과정을 계속 반복하며, 가장 우선순위가 높은 정점이 루트가 된다.
요소 삭제 시
-
요소의 제거는 루트 노드에서만 수행한다.
-
가장 마지막 정점을 루트로 한다.
-
루트의 자식 노드를 비교하여 우선순위가 더 높은 노드와 바꾼다.
-
이 과정을 계속 반복한다.
트라이(Trie)
-
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
-
문자열의 길이가 L 이라고 할 때, 탐색 및 삽입은 O(L)만큼 걸린다.
-
루트는 비어있다.
-
각 간선은 추가될 문자를 키로 가진다.
-
각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
-
해시 테이블과 연결 리스트를 이용해서 구현한다.
